简介

A.I. War 是一款由 Arcen Games 开发的即时战略游戏。本题灵感来源于该游戏，但并不要求你玩过它。

题目

你正在一场关乎银河系未来的致命战争中对抗人工智能（A.I.）。为了击败 A.I.，你需要威胁它的母星。一些行星之间通过虫洞相连；任何行星都可以通过虫洞与任意数量的其他行星相连。

你最初只拥有自己的母星。每一回合，你可以征服任何你威胁的行星。如果你不拥有某颗行星，且它通过虫洞与你拥有的任意行星相连，那么你就威胁到了这颗行星。一旦你征服了一颗行星，你就拥有了它。一旦你威胁到了 A.I. 的母星，你就不能再征服任何行星了。

在战术学校最重要的一天里，你发现了关于 A.I. 的两件事：

• 你每征服一颗行星，A.I. 就会变得更强大，因为它会将你视为威胁并生产更多的飞船来保护自己。
• A.I. 会防御所有你当前正在威胁的行星。

你结合这两点事实制定了一个策略：

1. 你将持续征服行星，直到你威胁到 A.I. 的母星为止。
2. 如果存在多种完成第 1 步的方法，请选择征服行星数量最少的那种。
3. 如果存在多种完成第 2 步的方法，请选择在结束时威胁行星数量最多的那种。

给定行星和虫洞的分布，如果你遵循上述策略，在通往 A.I. 母星的路上，你将征服并威胁多少颗行星？

输入格式

输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个测试用例的第一行包含两个空格分隔的整数：P（行星数量）和 W（虫洞数量）。你的母星是行星 0，A.I. 的母星是行星 1。

每个测试用例的第二行包含 W 个空格分隔的对，每对由逗号分隔的整数 x_i,y_i 组成。每一对表示连接行星 x_i 和 y_i 的双向虫洞。

输出格式

对于每个测试用例，输出一行 "Case #x: c t"，其中 x 是用例编号（从 1 开始），c 是你遵循上述策略所征服的行星数量，t 是你在最后威胁的行星数量（包括 A.I. 的母星）。

数据范围

$1 \le \mathbf{T} \le 50$。

$0 \le \mathbf{x}_i < \mathbf{y}_i < \mathbf{P}$。

每个虫洞都是唯一的：如果 $i \neq j$，则 $(\mathbf{x}_i, \mathbf{y}_i) \neq (\mathbf{x}_j, \mathbf{y}_j)$。

保证至少存在一条从你的母星出发，通过一系列虫洞到达 A.I. 母星的路径。

内存限制：1GB。

小数据集（测试集 1 - 可见；10 分）

$2 \le \mathbf{P} \le 36$。

$1 \le \mathbf{W} \le 630$。

时间限制：4 秒。

大数据集（测试集 2 - 隐藏；22 分）

$2 \le \mathbf{P} \le 400$。

$1 \le \mathbf{W} \le 2000$。

时间限制：8 秒。

样例

样例输入 1

4
2 1
0,1
3 3
0,1 1,2 0,2
5 5
0,4 0,2 2,4 1,2 1,4
7 9
0,6 0,2 0,4 2,4 3,4 2,3 3,5 4,5 1,5

样例输出 1

Case #1: 0 1
Case #2: 0 2
Case #3: 1 2
Case #4: 2 4

说明

在第一个用例中，你不需要征服任何东西，就已经威胁到了 A.I. 的母星。

在第三个用例中，你可以在征服一颗行星后威胁到 A.I. 的母星。最终你威胁到了两颗行星，还有一颗行星没有与任何东西相连。

在第四个用例中，你可以通过征服行星 4 和 5 来威胁 A.I. 的母星。最终你威胁到了行星 6、2、3 和 1（A.I. 的母星）。

注意

Arcen Games 是 A.I. War 的开发者。Arcen Games 不认可且未参与 Google Code Jam。