죄수 재배치

서로 가까이 있는 두 교도소는 수용 인원이 같다. 폭동과 탈옥 위험을 줄이기 위해, 두 교도소의 관리자는 한 교도소의 죄수 절반을 다른 교도소의 죄수 절반과 맞바꾸어 죄수를 재배치하기로 했다.

그런데 죄수들의 범죄 기록에 따르면, 어떤 죄수 쌍은 같은 교도소에 두면 위험하다고 알려져 있다. 그래서 이런 위험한 쌍은 현재 서로 다른 교도소에 나뉘어 수감되어 있다. 즉, 위험한 쌍마다 한 명은 첫 번째 교도소에, 다른 한 명은 두 번째 교도소에 있다. 재배치 후에도 모든 위험한 쌍은 반드시 서로 다른 교도소에 나뉘어 있어야 한다.

이 제약 때문에 죄수의 정확히 절반을 맞바꾸는 것이 불가능한 경우가 있다. 그런 경우에는 절반을 넘지 않는 선에서 최대한 많은 죄수를 맞바꾸어야 한다.

각 교도소의 죄수 수 $m$과 위험한 쌍 목록이 주어질 때, 어떤 위험한 쌍도 같은 교도소에 놓이지 않도록 하면서 맞바꿀 수 있는 죄수 수 $k \le m/2$ 중 가장 큰 값을 구하여라.

첫째 줄에 테스트 시나리오의 개수를 나타내는 양의 정수 $n$이 주어진다.

각 시나리오의 첫째 줄에는 두 정수 $m$과 $r$이 주어진다. $m$($1 < m < 200$)은 두 교도소 각각의 죄수 수이고, $r$은 위험한 쌍의 개수이다.

이어지는 $r$개의 줄에는 각각 두 정수 $x_i$와 $y_i$($1 \le x_i, y_i \le m$)가 주어진다. 이는 첫 번째 교도소의 죄수 $x_i$와 두 번째 교도소의 죄수 $y_i$를 같은 교도소에 두어서는 안 된다는 뜻이다.

각 시나리오마다, 어떤 위험한 쌍도 같은 교도소에 놓이지 않도록 하면서 첫 번째 교도소의 죄수 $k$명과 두 번째 교도소의 죄수 $k$명을 맞바꿀 수 있는, $k \le m/2$를 만족하는 가장 큰 정수 $k$를 한 줄에 출력한다.