물 위의 작품 배치

산업디자인을 공부하는 학생들이 자기 작품을 에이설미어 호수 위에 띄워 전시하기로 했다. 작품은 혼자서는 물에 뜨지 못하기 때문에, 학생들은 보트 몇 척을 가져와 작품을 서로 묶었다.

보트는 왼쪽과 오른쪽에 밧줄 고리가 하나씩 있어서 작품을 최대 두 개까지 묶는다. 보트 두 척 이상에 묶인 작품은 계속 물에 떠 있다. 보트 한 척에만 묶인 작품은 제대로 뜨지 못한다. 보트에서 가장 먼 부분이 물에 잠겨 물을 먹고, 작품이 무거워져서 결국 가라앉는다. 가라앉은 작품에 묶여 있던 보트는 반대쪽 작품에서 밧줄을 풀고 물 먹은 작품을 해변으로 끌고 간다. 학생들은 작품을 끌고 온 보트를 그대로 묶어 두고 싶어 하므로, 그 보트는 물 위로 돌아오지 않는다. 밧줄이 풀린 작품은 받쳐 주던 보트를 한 척 잃고, 같은 이유로 가라앉기 시작할 수 있다. 정리하면 작품은 자신에게 묶인 보트가 두 척 이상 남아 있는 동안에만 떠 있다.

작품이 하나도 가라앉지 않게 묶는 방법은 간단한 것부터 여럿 있다. 예를 들어 작품과 보트를 하나의 원으로 잇는 방법이 있다. 학생들은 그 방법을 쓰지 않았다. 완성된 배치는 전체가 하나로 연결되어 있지만 보트 한 척에만 묶인 작품이 많아서 가라앉을 위험이 크다. 학생들은 이미 쓴 보트를 항상 서로 다른 작품 두 개에 묶었고, 작품 하나에만 묶은 보트는 없다.

학생들은 실수를 인정하고, 남은 여분 보트로 작품을 최대한 많이 살려 달라고 부탁했다. 지금 묶여 있는 배치는 그대로 두어야 한다. 게다가 보트가 놓인 순서가 바뀌지 않도록 여분 보트는 왼쪽 고리만 쓸 수 있다. 즉 여분 보트 한 척은 작품 하나에만 묶인다. 여분 보트를 모두 쓸 필요는 없고, 같은 작품에 여러 척을 묶어도 된다.

여분 보트를 가장 잘 썼을 때 결국 가라앉는 작품이 몇 개인지 구하라.

첫 줄에 테스트 케이스의 개수가 주어진다. 100 이하의 양의 정수다. 이어서 각 테스트 케이스마다 다음이 주어진다.

공백으로 구분된 세 정수 $n$ , $m$ , $k$ ( $1 \le n, m, k \le 10000$ )가 한 줄에 주어진다. 각각 작품 수, 이미 쓴 보트 수, 여분 보트 수다.
다음 $m$ 개의 줄에 공백으로 구분된 두 정수 $a$ 와 $b$ ( $1 \le a, b \le n$ , $a \ne b$ )가 주어진다. 보트 한 척이 왼쪽으로 작품 $a$ 에, 오른쪽으로 작품 $b$ 에 묶여 있다는 뜻이다.

같은 작품 쌍을 묶는 보트는 두 척 이상 없다. 작품과 보트는 전체가 하나로 연결되어 있고, 배치가 평면 위에 그려진다는 보장은 없다. 여분 보트를 한 척도 쓰지 않아도 작품 하나 이상은 물에 떠 있다.

물 위의 작품 배치

문제

입력

출력