공평한 분배

$N$개의 프로세서와 $M$개의 작업이 주어진다. 각 작업은 지정된 두 프로세서 중 정확히 하나에서만 실행할 수 있다. 작업 하나를 처리하는 데는 1단위 시간이 걸리며, 어떤 프로세서에 $K$개의 작업이 배정되면 그 프로세서가 배정된 모든 작업을 끝내는 데 $K$단위 시간이 걸린다.

모든 작업을 최대한 빨리 끝내려면 작업을 프로세서들에 최대한 고르게 나누어야 한다. 정확히 말하면, 각 작업을 자신이 실행될 수 있는 두 프로세서 중 하나에 배정하되, 한 프로세서에 배정되는 작업 수의 최댓값이 가능한 한 작아지도록 해야 한다. 이렇게 얻을 수 있는 "최댓값의 최솟값"을 공평한 분배(fair share)라고 부른다.

예를 들어 프로세서가 5개, 작업이 6개이고, 각 작업이 아래 표의 두 프로세서 중 하나에 배정될 수 있다고 하자.

작업 1을 프로세서 1, 작업 2를 프로세서 2, 작업 3을 프로세서 3, 작업 4를 프로세서 4, 작업 5를 프로세서 5, 작업 6을 프로세서 1에 배정하면 어떤 프로세서도 작업을 두 개보다 많이 갖지 않는다. 작업 수가 프로세서 수보다 많으므로 적어도 한 프로세서는 작업을 두 개 가질 수밖에 없고, 따라서 이 경우 공평한 분배는 2이다.

$N$, $M$, 그리고 각 작업이 배정될 수 있는 두 프로세서의 쌍이 주어질 때 공평한 분배를 구하는 프로그램을 작성하라. 프로세서에는 $1$번부터 $N$번까지, 작업에는 $1$번부터 $M$번까지 번호가 매겨진다. 각 작업의 두 프로세서로 이루어진 집합은 작업마다 서로 다르다. 즉, 작업 $J_1$이 프로세서 $\{P_1, P_2\}$를 쓸 수 있고 다른 작업 $J_2$가 $\{P_3, P_4\}$를 쓸 수 있다면 $\{P_1, P_2\} \neq \{P_3, P_4\}$이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 프로세서의 수를 나타내는 정수 $N$ ($1 \le N \le 1{,}000$)이 주어진다. 다음 줄에는 작업의 수를 나타내는 정수 $M$ ($1 \le M \le 10{,}000$)이 주어진다. 이어지는 $M$개의 줄 중 $K$번째 줄에는 작업 $K$가 실행될 수 있는 서로 다른 두 프로세서가 공백으로 구분되어 주어진다.

나머지 테스트 케이스도 같은 형식으로 이어서 주어진다.

각 테스트 케이스마다 그 테스트 케이스의 공평한 분배를 한 줄에 하나씩 출력한다.