P16884 [GKS 2022 #D] Suspects and Witnesses

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$ 是可以证明是无辜的客人数量。

在样例 #1 中，有 $N = 3$ 位客人，$M = 2$ 条证人证言，最多有 $K = 1$ 个偷饼干者。 证人证言如下： - 客人 $1$：客人 $2$ 没有偷饼干。 - 客人 $2$：客人 $3$ 没有偷饼干。 现在，我们考虑每位客人是否是偷饼干者的所有可能情况。 | 情景 | 客人 $1$ | 客人 $2$ | 客人 $3$ | 是否可能？ | |:-:|:-:|:-:|:-:|:-:| | 情景 #1 | 无辜 | 无辜 | 无辜 | 是 | | 情景 #2 | 偷窃者 | 无辜 | 无辜 | 是 | | 情景 #3 | 无辜 | 偷窃者 | 无辜 | 否 | | 情景 #4 | 无辜 | 无辜 | 偷窃者 | 否 | 以上是满足最多有 $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 完成