You Shall Not Pass!!

Ahmed Aly builds the problem set for this year's regional contest, and he knows the participating teams and their coaches well. Every participating university has one coach who coaches some seniors, each senior may coach some juniors, and each junior may coach another junior, and so on. The relations form a hierarchy in which every team coaches the teams directly beneath it. Ahmed knows exactly who coaches whom.

For any one team, Ahmed can write a problem that this team, the teams it coaches, and everyone further down the hierarchy will fail to solve, while every other team solves it. The number of problems he can put in the problem set is limited, and he wants to spend all of them on a single goal: making the number of teams that fail to solve at least one problem as large as possible.

Given the number of problems Ahmed can write and the coaching relations between the teams, print the largest number of teams that can fail to solve at least one problem.

A team can be coached by at most one other team.

The first line contains an integer $T$, the number of test cases. $T$ test cases follow.

The first line of each test case contains three integers $A$, $B$ and $C$: the number of teams, the number of coaching relations, and the number of problems available for the problem set. Then follow $B$ lines, each containing two integers $u$ and $v$, meaning that team $u$ coaches team $v$. Teams are numbered from $0$ to $A-1$.

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

For each test case, print on its own line the largest number of teams that can fail to solve at least one problem.