题目描述

Ada 为她的生日派对烤了一些饼干，她邀请了 $N$ 位客人，编号为 $1$ 到 $N$。当所有客人都到达，派对即将开始时，可怕的事情发生了——有人偷了饼干！

Ada 戴上侦探帽，开始询问她的客人。她收集了 $M$ 条证人证言，每条形式为：客人 $x$：“客人 $y$ 没有偷饼干。”

Ada 知道，如果一位客人是无辜的（没有偷饼干），那么他所说的所有证言都必须是真实的。注意，Ada 不知道偷饼干者所说的任何证言是否正确。

最后，Ada 从线人那里得知，偷饼干者的人数最多为 $K$。根据这些信息，你能帮助 Ada 找出可以证明是无辜的客人数量吗？

注意，可能实际上没有客人偷饼干，只是 Ada 忘记了自己烤了多少饼干。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个整数 $N$、$M$ 和 $K$：分别表示客人的数量、证人证言的数量以及偷饼干者的最大可能人数。

接下来的 $M$ 行描述每条证人证言。第 $i$ 行包含两个整数 $A_i$ 和 $B_i$，表示证人证言：客人 $A_i$ 说：“客人 $B_i$ 没有偷饼干。”

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是可以证明是无辜的客人数量。

2
3 2 1
1 2
2 3
3 3 1
1 2
2 3
3 1

Case #1: 2
Case #2: 3

2
3 2 2
1 2
2 3
3 3 2
1 2
2 3
3 2

Case #1: 1
Case #2: 2

提示

在样例 #1 中，有 $N = 3$ 位客人，$M = 2$ 条证人证言，最多有 $K = 1$ 个偷饼干者。

证人证言如下：

• 客人 $1$：客人 $2$ 没有偷饼干。
• 客人 $2$：客人 $3$ 没有偷饼干。

现在，我们考虑每位客人是否是偷饼干者的所有可能情况。

以上是满足最多有 $K = 1$ 个偷饼干者的所有情景。情景 #3 不可能，因为客人 $1$ 是无辜的，且他声称客人 $2$ 是无辜的，但客人 $2$ 实际上是偷窃者。情景 #4 同理。

对于剩下的情景，我们发现客人 $2$ 和客人 $3$ 始终是无辜的，因此答案为 $2$。

限制条件

$1 \le T \le 100$。

$2 \le N \le 10^5$。

$1 \le M \le 10^5$。

对于所有 $i$，$1 \le A_i \le N$。

对于所有 $i$，$1 \le B_i \le N$。

对于所有 $i$，$A_i \ne B_i$。

对于所有 $i \ne j$，$(A_i, B_i) \ne (A_j, B_j)$。

测试集 1

$K = 1$。

测试集 2

$1 \le K \le 20$。

翻译由 DeepSeek V4 Pro 完成