26423번 - 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 starts questioning 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. Note that Ada does not know whether any statement made by a cookie stealer is correct.

Lastly, Ada has an informant who told her there can be at most $\mathbf{K}$ cookie stealers. With this information, can you help Ada find out the number of guests who can be proved to be innocent?

Note that 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$.

• $\mathbf{K} = 1$.

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