용의자와 목격자

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

Ada는 탐정 모자를 쓰고 손님들에게 질문한다. 그녀는 "손님 $\mathbf{y}$는 쿠키를 훔치지 않았다."라는 형식의 목격 진술을 $\mathbf{M}$개 모았다. 진술자는 손님 x이다.

Ada는 손님이 무죄(쿠키를 훔치지 않은 경우)라면 그 손님의 모든 진술이 참이어야 한다는 것을 안다. 다만 쿠키를 훔친 손님의 진술이 맞는지는 Ada가 알 수 없다.

제보자는 쿠키를 훔친 사람이 많아야 $\mathbf{K}$명이라고 알려 주었다. 이 정보를 바탕으로 무죄임을 증명할 수 있는 손님이 몇 명인지 구하라.

쿠키를 실제로 훔친 손님이 없을 수도 있다. 그저 Ada가 구운 쿠키의 개수를 잊어버렸을 뿐일 수도 있다.

입력의 첫 줄에는 테스트 케이스의 개수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $\mathbf{N}$, $\mathbf{M}$, $\mathbf{K}$가 주어진다. 각각 손님 수, 진술 수, 쿠키를 훔친 사람의 최대 수이다.

다음 $\mathbf{M}$개의 줄은 진술을 나타낸다. $i$번째 줄에는 두 정수 $\mathbf{A\_i}$와 $\mathbf{B\_i}$가 주어지며, 이는 손님 $\mathbf{A\_i}$의 진술 "손님 $\mathbf{B\_i}$는 쿠키를 훔치지 않았다."를 뜻한다.

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

• $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})$.