용의자와 목격자

Ada는 생일 파티를 위해 쿠키를 구웠고, $1$부터 $\mathbf{N}$까지의 번호가 붙은 손님 $\mathbf{N}$명을 초대했다. 모든 손님이 도착하고 파티가 막 시작되려던 순간, 끔찍한 일이 벌어졌다. 누군가 쿠키를 훔친 것이다!

Ada는 탐정 모자를 쓰고 손님들을 심문하기 시작한다. Ada는 다음과 같은 형식의 목격자 진술 $\mathbf{M}$개를 모았다. 손님 x: "손님 y는 쿠키를 훔치지 않았다."

Ada는 어떤 손님이 무고하다면(쿠키를 훔치지 않았다면), 그 손님의 모든 목격자 진술이 참이어야 한다는 것을 알고 있다. 쿠키를 훔친 사람이 한 진술이 맞는지는 Ada도 알지 못한다는 점에 유의하라.

마지막으로, Ada의 정보원은 쿠키를 훔친 사람이 최대 $\mathbf{K}$명일 수 있다고 알려 주었다. 이 정보를 이용해 무고하다고 증명할 수 있는 손님의 수를 Ada가 알아내도록 도와줄 수 있는가?

실제로는 어떤 손님도 쿠키를 훔치지 않았고, Ada가 자신이 쿠키를 몇 개 구웠는지 잊었을 가능성도 있다는 점에 유의하라.

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $2 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{M} \le 10^5$. 모든 $i$에 대해, $1 \le \mathbf{A_i} \le \mathbf{N}$. 모든 $i$에 대해, $1 \le \mathbf{B_i} \le \mathbf{N}$. 모든 $i$에 대해, $\mathbf{A_i} \neq \mathbf{B_i}$. 모든 $i \neq j$에 대해, $(\mathbf{A_i}, \mathbf{B_i}) \neq (\mathbf{A_j}, \mathbf{B_j})$.

테스트 세트 1

$\mathbf{K} = 1$.

테스트 세트 2

$1 \le \mathbf{K} \le 20$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{K}$가 주어지며, 각각 손님의 수, 목격자 진술의 수, 쿠키를 훔친 사람의 최대 수를 나타낸다. 다음 $\mathbf{M}$개의 줄은 목격자 진술을 설명한다. $i$번째 줄에는 두 정수 $\mathbf{A_i}$와 $\mathbf{B_i}$가 주어지며, 이는 다음 목격자 진술을 의미한다. 손님 $\mathbf{A_i}$: "Guest $\mathbf{B_i}$ did not steal the cookies."

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$는 무고하다고 증명할 수 있는 손님의 수이다.

예제 케이스 #1에는 손님 $\mathbf{N}=3$명과 목격자 진술 $\mathbf{M}=2$개가 있으며, 쿠키를 훔친 사람은 최대 $\mathbf{K}=1$명이다. 목격자 진술은 다음과 같다.

• 손님 $1$: 손님 $2$는 쿠키를 훔치지 않았다.

• 손님 $2$: 손님 $3$는 쿠키를 훔치지 않았다.

이제 각 손님이 쿠키를 훔친 사람인지 아닌지에 대한 가능한 모든 경우를 살펴보자.

이는 쿠키를 훔친 사람이 최대 $\mathbf{K}=1$명인 모든 시나리오이다(CS). 시나리오 #3에서는 손님 1가 무고하며 손님 2가 무고하다고 진술하지만, 실제로는 손님 2가 쿠키를 훔친 사람이므로 불가능하다. 시나리오 #4도 같은 이유로 불가능하다.

남은 시나리오를 보면 손님 2와 3는 항상 무고하므로, 답은 $2$이다.

추가 예제 - 테스트 세트 2