중앙값 무게 구슬

모양과 크기는 같지만 무게가 서로 다른 구슬이 $N$개 있다. $N$은 홀수이며, 구슬에는 $1, 2, \dots, N$의 번호가 매겨져 있다. 이 가운데 무게가 중앙값인 구슬, 즉 전체 $N$개 중에서 $\frac{N+1}{2}$번째로 가벼운 구슬을 찾는 것이 목표이다.

저울을 이용하면 두 구슬의 무게를 비교하여 어느 쪽이 더 무거운지 알 수 있다. $M$번의 비교를 마치면 어떤 구슬이 다른 구슬보다 무겁다는 사실들을 알게 되며, 이 관계는 추이적이다. 즉 구슬 $A$가 구슬 $B$보다 무겁고 구슬 $B$가 구슬 $C$보다 무거우면, $A$는 $C$보다 무겁다. 이 정보만으로 중앙값이 될 수 없는 구슬을 모두 골라내려고 한다.

어떤 구슬보다 무겁다고 알려진 구슬이 $\frac{N+1}{2}$개 이상이거나, 그 구슬보다 가볍다고 알려진 구슬이 $\frac{N+1}{2}$개 이상이면, 그 구슬은 절대로 중앙값이 될 수 없다.

예를 들어 $N = 5$이고 다음과 같은 $M = 4$개의 결과가 주어졌다고 하자.

1. 구슬 2는 구슬 1보다 무겁다.
2. 구슬 4는 구슬 3보다 무겁다.
3. 구슬 5는 구슬 1보다 무겁다.
4. 구슬 4는 구슬 2보다 무겁다.

정확히 어떤 구슬이 중앙값인지는 알 수 없지만, 구슬 1과 구슬 4는 결코 중앙값이 될 수 없다. 구슬 2, 4, 5는 모두 구슬 1보다 무겁고, 구슬 1, 2, 3은 모두 구슬 4보다 가볍기 때문이다. $\frac{N+1}{2} = 3$이므로 두 구슬 모두 제거 조건을 만족한다.

중앙값이 될 수 없는 구슬이 몇 개인지 세는 프로그램을 작성하여라.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 11$)가 주어진다. 이어서 각 테스트 케이스의 데이터가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $N$ ($1 \le N \le 99$)과 $M$이 주어지며, $N$은 구슬의 개수, $M$은 비교 횟수이다. 다음 $M$개의 줄에는 각각 두 정수 $a$와 $b$가 주어지며, 이는 구슬 $a$가 구슬 $b$보다 무겁다는 뜻이다.

각 테스트 케이스마다 중앙값이 될 수 없는 구슬의 개수를 한 줄에 하나씩 출력한다.