P13377 [GCJ 2011 #2] A.I. War

A.I. War is a real-time strategy game developed by Arcen Games. This problem was inspired by the game, but does not assume you have played it. Arcen Games is the creator of A.I. War. Arcen Games does not endorse and has no involvement with Google Code Jam.

你正与一个人工智能在一场关乎银河未来的致命战争中对抗。为了击败这个人工智能，你需要威胁它的 $home\ planet$（母星）。一些行星之间通过虫洞相连；任何行星都可以通过虫洞与任意数量的其他行星相连。 你一开始只拥有你的母星。每一回合，你可以征服任何你$威胁$的行星。如果你还未拥有某个行星，并且它通过虫洞与任何你已拥有的行星相连，那么你就威胁着这个行星。一旦你征服了某个行星，你就拥有了它。一旦你威胁到了人工智能的母星，你就不能再征服其他行星。 在参加战术学校最重要的一天时，你发现了关于人工智能的两件事： - 每当你征服一个行星，人工智能就会变得更强大，因为它会把你视为威胁，并制造更多的战舰来防御自己。 - 人工智能会防御你当前威胁的每一个行星。 你将这两点结合起来，制定了如下策略： 1. 你将不断征服行星，直到你威胁到人工智能的母星为止。 2. 如果有多种完成第 1 步的方法，选择征服行星数量$最少$的方法。 3. 如果有多种完成第 2 步的方法，选择最终威胁行星数量$最多$的方法。 给定所有行星和虫洞的信息，按照上述策略，你在威胁到人工智能母星的过程中，会征服和威胁多少个行星？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试用例。每组测试用例的第一行为两个用空格分隔的整数：$P$ 表示行星数，$W$ 表示虫洞数。你的母星编号为 $0$，人工智能的母星编号为 $1$。 每组测试用例的第二行为 $W$ 个用空格分隔的逗号分隔整数对 $x_{i}, y_{i}$。每对表示存在一条双向虫洞连接行星 $x_{i}$ 和 $y_{i}$。

对于每组测试用例，输出一行，格式为 "Case #$x$: $c\ t$"，其中 $x$ 为测试用例编号（从 $1$ 开始），$c$ 为按照上述策略你征服的行星数，$t$ 为最后你威胁的行星数（包括人工智能的母星）。

**样例解释** 在第一个样例中，你无需征服任何行星，就已经威胁到了人工智能的母星。 在第三个样例中，你只需征服一个行星就能威胁到人工智能的母星。你最终威胁了两个行星，还有一个行星没有与任何行星相连。 在第四个样例中，你可以通过征服行星 $4$ 和 $5$ 来威胁人工智能的母星。你最终威胁了行星 $6$、$2$、$3$ 和 $1$（人工智能的母星）。 **数据范围** - $1 \leq T \leq 50$。 - $0 \leq x_{i} < y_{i} < P$。 - 每条虫洞唯一：如果 $i \neq j$，则 $(x_{i}, y_{i}) \neq (x_{j}, y_{j})$。 - 保证至少存在一条路径可以通过虫洞从你的母星到达人工智能的母星。 **小数据集（10 分，测试点 1 - 可见）** - $2 \leq P \leq 36$。 - $1 \leq W \leq 630$。 - 时间限制：3 秒。 **大数据集（22 分，测试点 2 - 隐藏）** - $2 \leq P \leq 400$。 - $1 \leq W \leq 2000$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译