You Shall Not Pass!!

Ahmed Aly는 올해 지역 대회의 출제 책임자이고, 참가 팀과 코치 관계를 훤히 알고 있다. 참가 대학마다 코치가 한 명 있고, 그 코치는 몇몇 상급생을 지도한다. 상급생은 다시 후배를 지도할 수 있고, 그 후배가 또 다른 후배를 지도할 수도 있다. 이렇게 만들어진 계층 구조에서 각 팀은 자기 바로 아래에 있는 팀을 지도한다. Ahmed는 누가 누구를 지도하는지 정확히 안다.

Ahmed는 팀 하나를 고르면, 그 팀과 그 팀이 지도하는 팀, 그리고 계층 구조에서 그 아래에 있는 모든 팀은 풀지 못하고 나머지 팀은 전부 푸는 문제를 만들 수 있다. 다만 문제 세트에 넣을 수 있는 문제 수는 정해져 있다. Ahmed는 그 문제를 모두 써서 한 문제 이상 풀지 못하는 팀의 수를 최대로 만들려고 한다.

문제 세트에 넣을 수 있는 문제 수와 팀 사이의 지도 관계가 주어질 때, 한 문제 이상 풀지 못하는 팀 수의 최댓값을 구하는 프로그램을 작성하시오.

한 팀을 지도하는 팀은 많아야 한 팀이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 팀의 수 $A$, 지도 관계의 수 $B$, 문제 세트에 넣을 수 있는 문제 수 $C$가 공백으로 구분되어 주어진다. 다음 $B$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지며, 팀 $u$가 팀 $v$를 지도한다는 뜻이다. 팀 번호는 $0$번부터 $A-1$번까지다.

• $0 < T \le 100$
• $0 < A \le 10000$
• $0 \le B < A$
• $0 \le C \le A$
• $0 \le u, v < A$

각 테스트 케이스마다 한 문제 이상 풀지 못하는 팀 수의 최댓값을 한 줄에 하나씩 출력한다.