동치 증명

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

\(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)을 이용하는 것이다.

예를 들어, 선영이의 예시 답안은

(a)이면 (b)이고, (b)이면 (c)이며 (c)이면 (d)이고, 마지막으로 (d)이면 (a)이다. 이 네 함축은 네 가지 명제가 동치임을 보여준다.

라고 되어있다.

다른 방법으로는 (a)이면 (b)이고, (b)이면 (a)이므로 (a)와 (b)가 동치라고 증명한 다음,

같은 방식으로 (b)와 (c)가 동치임을 증명하고, 마지막으로 (c)와 (d)가 동치임을 증명하는 방법이 있다.

하지만 이건 무려 여섯 번의 함축을 필요로 한다.

선영이는 선형대수학 책을 집필하는 과정에서 수없이 많은 명제가 동치임을 증명해야 하기 때문에 이러한 비효율성은 치명적이다.

선영이가 다음 학기 시작 전에 교재를 모두 집필할 수 있도록 되도록이면 적은 수의 함축을 이용해서 명제가 동치임을 증명할 수 있도록 도와주자.

첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어지고,

각 테스트 케이스에 대해서는 다음과 같은 입력이 주어진다:

• 명제의 수 n(1 ≤ n ≤ 20,000)와 이미 증명된 함축의 수 m(0 ≤ m ≤ 50,000)이 첫 번째 줄에 주어진다.
• m개의 줄에 "s1이면 s2이다." 를 나타내는 s1과 s2(1 ≤ s1,s2 ≤ n이고 s1 ≠ s2)가 주어진다.

각 테스트 케이스마다 한 줄을 출력한다:

• 위대한 수학자 김선영이 주어진 명제들이 동치임을 증명하기 위해 사용해야 하는 함축의 수의 최솟값.