동치 증명

위대한 수학자 김선영은 선형대수학 교과서를 집필하다가 다음 문제를 만들었다.

$N \times N$ 행렬 $A$에 대하여 다음 명제들이 서로 동치임을 증명하여라.

1. $A$의 역행렬이 존재한다.
2. 임의의 $N \times 1$ 행렬 $b$에 대하여 $Ax = b$는 유일한 해를 가진다.
3. 임의의 $N \times 1$ 행렬 $b$에 대하여 $Ax = b$는 해를 가진다.
4. $Ax = 0$의 해는 $x = 0$ 하나뿐이다.

이런 문제를 푸는 일반적인 방법은 함축(implication)의 사슬을 이용하는 것이다. 예를 들어 다음과 같이 증명할 수 있다.

(1)이면 (2)이고, (2)이면 (3)이며, (3)이면 (4)이고, 마지막으로 (4)이면 (1)이다. 이 네 개의 함축은 네 명제가 모두 동치임을 보여준다.

또 다른 방법은 (1)이면 (2)이고 (2)이면 (1)임을 보여 (1)과 (2)가 동치임을 증명하고, 같은 방식으로 (2)와 (3), (3)과 (4)가 각각 동치임을 증명하는 것이다. 하지만 이 방법은 무려 여섯 번의 함축을 필요로 한다.

김선영은 교과서를 쓰면서 수많은 명제가 동치임을 증명해야 하므로 이러한 비효율은 치명적이다. 되도록 적은 수의 함축만으로 명제들이 동치임을 증명할 수 있도록 도와주자.

일반적으로 $n$개의 명제와 이미 증명된 $m$개의 함축이 주어진다. 각 함축은 "명제 $s_1$이 참이면 명제 $s_2$도 참이다"를 뜻한다. 주어진 모든 명제가 서로 동치임을(즉, 어느 하나가 참이면 나머지도 모두 참임을) 증명하기 위해 추가로 증명해야 하는 함축의 최소 개수를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 명제의 개수 $n$ ($1 \le n \le 20000$)과 이미 증명된 함축의 개수 $m$ ($0 \le m \le 50000$)이 공백으로 구분되어 주어진다.
• 이어지는 $m$개의 줄에 각각 두 정수 $s_1$, $s_2$ ($1 \le s_1, s_2 \le n$, $s_1 \ne s_2$)가 주어진다. 이는 "명제 $s_1$이 참이면 명제 $s_2$도 참이다"라는 이미 증명된 함축을 뜻한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다.

주어진 모든 명제가 서로 동치임을 증명하기 위해 추가로 증명해야 하는 함축의 최소 개수를 출력한다.