Suspects and Witnesses

Ada baked some cookies for her birthday party, where she invited $\mathbf{N}$ guests, labeled $1$ to $\mathbf{N}$. When all the guests have arrived and the party is about to start, something terrible has happened. Someone stole the cookies!

Ada puts on her detective hat and questions her guests. She gathered $\mathbf{M}$ witness statements of the form: Guest x: "Guest y did not steal the cookies."

Ada knows that if a guest is innocent (did not steal a cookie), then all their witness statements must be true. Ada does not know whether any statement made by a cookie stealer is correct.

An informant told her there are at most $\mathbf{K}$ cookie stealers. Using this information, find the number of guests who can be proved to be innocent.

It is possible that no guest actually stole the cookies, and Ada simply forgot how many cookies she baked.

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains three integers $\mathbf{N}$, $\mathbf{M}$, and $\mathbf{K}$: the number of guests, the number of witness statements, and the maximum number of cookie stealers, respectively.

The next $\mathbf{M}$ lines describe the witness statements. The $i$-th line contains two integers $\mathbf{A\_i}$ and $\mathbf{B\_i}$, which means the witness statement Guest $\mathbf{A\_i}$: "Guest $\mathbf{B\_i}$ did not steal the cookies."

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from 1) and $y$ is the number of guests that can be proved to be innocent.

• $1 \le \mathbf{T} \le 100$.
• $2 \le \mathbf{N} \le 10^5$.
• $1 \le \mathbf{M} \le 10^5$.
• $1 \le \mathbf{A\_i} \le \mathbf{N}$, for all $i$.
• $1 \le \mathbf{B\_i} \le \mathbf{N}$, for all $i$.
• $\mathbf{A\_i} \neq \mathbf{B\_i}$, for all $i$.
• $(\mathbf{A\_i}, \mathbf{B\_i}) \neq (\mathbf{A\_j}, \mathbf{B\_j})$, for all $i \neq j$.