题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入格式

输入文件有若干组数据，每组数据的第一行是一个正整数 $N$，表示工地的隧道数。

接下来的 $N$ 行每行是用空格隔开的两个整数 $S$ 和 $T$（$S \neq T$），表示挖煤点 $S$ 与挖煤点 $T$ 由隧道直接连接。

注意，每组数据的挖煤点的编号为 $1 \sim Max$，其中 $Max$ 表示由隧道连接的挖煤点中，编号最大的挖煤点的编号，可能存在没有被隧道连接的挖煤点。

输入数据以 $0$ 结尾。

输出格式

每组数据输出结果占一行。

其中第 $i$ 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$，输出格式参照以下输入输出样例。

样例

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

Case 1: 2 4
Case 2: 4 1

样例解释

第一组数据

$N=9$ 条隧道，挖煤点编号最大为 6（因为边中最大编号是 6）。

边列表： 1-3, 4-1, 3-5, 1-2, 2-6, 1-5, 6-3, 1-6, 3-2

图结构

这个图是一个连通图（所有点都连通）。

题目要求：无论哪个挖煤点坍塌后，其他挖煤点都能到达某个救援出口。

即去掉任意一个点（坍塌点），剩下的图仍然连通到救援出口。

这相当于在图中选择一些点作为救援出口，使得对于每个点 $v$，如果 $v$ 不是出口，那么 $v$ 被删除后，剩下的每个点都能到达某个出口。

换一种说法：救援出口构成了一个点覆盖，且满足即使删除任意非出口点，图仍然连通到出口。

这与点双连通分量和割点有关。

算法分析

这个问题是经典的煤矿逃生问题，解法如下：

1. 求出所有点双连通分量（Biconnected Component, BCC）。
2. 对于每个点双连通分量，统计其中包含的割点个数。
3. 分类讨论：
   • 如果点双连通分量中没有割点（即整个图是一个点双连通分量），那么需要设置 2 个救援出口（防止其中一个出口所在点坍塌），方案数为 $C_{size}^2 = \frac{size(size-1)}{2}$，其中 $size$ 是该分量中节点数。
   • 如果点双连通分量中有 1 个割点，那么需要设置 1 个救援出口（因为如果割点坍塌，该分量被隔离，需要内部有出口；如果出口所在点坍塌，还可以通过割点逃到其他分量的出口）。方案数为 $size - 1$（不能设在割点上，因为割点可能坍塌）。
   • 如果点双连通分量中有 ≥2 个割点，则不需要设置救援出口（因为即使一个割点坍塌，仍可通过另一个割点逃到其他分量的出口）。

注意：一个割点可能属于多个点双连通分量。

第一组数据计算

通过 Tarjan 算法求点双连通分量：

图结构：

1---3---5
| / | \
|/  |  2
6---4

实际上可能不同。我们手动分析。

点双连通分量：

• 分量1：{1,2,3,6}（包含割点吗？需要检查）
• 分量2：{1,3,5}
• 分量3：{1,4}

割点：点 1 和点 3 可能是割点。

具体需要程序计算。

根据输出 2 4，说明至少需要 2 个救援出口，方案数为 4。

第二组数据

$N=6$ 条隧道，最大编号为 7。

边： 1-2, 1-3, 2-4, 2-5, 3-6, 3-7

图结构：

    1
   / \
  2   3
 / \ / \
4  5 6  7

这是一个树形结构（没有环），每个点都是割点（除了叶子）。

点双连通分量：每条边构成一个点双连通分量（因为树中任意两点间只有一条简单路径，不含环，所以每个点双连通分量就是一条边）。

每个分量有 2 个节点，其中割点个数：每条边的两个端点中，至少有一个是割点（除了叶子）。实际上，在树中，每条边对应的点双连通分量中，两个点都是割点（除了叶子），但严格来说，叶子不是割点。

计算：

• 分量 (1,2)：割点个数 2（1 和 2 都是割点？1 连接 2,3，删除 1 后图不连通，所以是割点；2 连接 1,4,5，删除 2 后也不连通，是割点）。所以该分量有 2 个割点，不需要出口。
• 分量 (1,3)：同样 2 个割点，不需要出口。
• 分量 (2,4)：2 是割点，4 是叶子（不是割点），所以割点个数为 1，需要 1 个出口，方案数 = size-1 = 1（只能设在 4 上）。
• 分量 (2,5)：类似，需要 1 个出口，方案数 1（设在 5）。
• 分量 (3,6)：需要 1 个出口，方案数 1（设在 6）。
• 分量 (3,7)：需要 1 个出口，方案数 1（设在 7）。

所以总共需要 4 个出口（在 4,5,6,7），方案数 = 1×1×1×1 = 1。

输出 Case 2: 4 1，符合。

数据范围

• $1 \le N \le 500$
• $1 \le Max \le 1000$

算法分析

问题转化

这是一个点连通度相关的问题。我们需要选择一些点作为救援出口，使得删除任意一个点（非出口）后，剩下的每个点都能到达至少一个出口。

这等价于：救援出口集合是一个点覆盖，且满足图在删除任意非出口点后，剩余部分仍与出口连通。

通过点双连通分解，可以将问题简化为对每个点双连通分量独立处理。

点双连通分量

点双连通分量（BCC）是极大的无割点子图。Tarjan 算法可以在 $O(N+Max)$ 时间内求出所有点双连通分量。

算法步骤

1. 读入边，构建无向图。
2. 使用 Tarjan 算法求出所有割点和点双连通分量。
   • 注意：一个割点可能属于多个点双连通分量。
3. 统计每个点双连通分量中的割点个数 $cnt$。
   • 如果 $cnt = 0$：需要 2 个出口，方案数 $= \frac{size \times (size-1)}{2}$。
   • 如果 $cnt = 1$：需要 1 个出口，方案数 $= size - 1$（不能选割点）。
   • 如果 $cnt \ge 2$：不需要出口（方案数 1，表示该分量对出口数无贡献，但乘法中乘以 1）。
4. 将所有点双连通分量的结果合并：
   • 总最少出口数 = 各分量所需出口数之和。
   • 总方案数 = 各分量方案数的乘积（乘法原理）。
5. 输出结果。

注意：可能存在多个连通块（即整个图不连通），但题目输入保证所有给出的边构成的图是连通的吗？不一定，可能存在孤立的点（没有边连接）。对于孤立的点，它自身构成一个点双连通分量（size=1，割点个数0），需要 2 个出口？但只有一个点，无法设两个出口。实际上，孤立点需要 1 个出口（因为如果它坍塌，没有其他点；如果它不坍塌，需要出口）。所以对于 size=1 且 cnt=0 的分量，需要 1 个出口，方案数 1。

因此，需要特殊处理 size=1 的情况。

处理细节

• 图可能不连通，每个连通块独立处理，然后结果相加。
• 注意编号最大为 Max，但可能存在没有边的点，这些点需要单独考虑。
• 使用 unsigned long long 存储方案数（保证小于 $2^{64}$）。

样例验证

第一组数据

通过点双连通分量计算： 假设分量：

1. {1,2,3,6}：割点个数 2（1 和 3 是割点），不需要出口。
2. {1,3,5}：割点个数 2（1 和 3），不需要出口。
3. {1,4}：割点个数 1（1 是割点），需要 1 个出口，方案数 = size-1 = 1（只能选 4）。 所以总出口数 = 1，方案数 = 1。但输出是 2 4，不符。

可能分量划分不同。需要实际运行算法。

实际上，根据经典题解，第一组数据的结果是 2 4，说明我们的分析可能漏了某些分量。

重新检查图：边很多，可能点双连通分量不同。

运行 Tarjan 算法后，可能得到：

• 分量 A：{1,3,5}，割点 1 和 3。
• 分量 B：{1,2,3,6}，割点 1 和 3。
• 分量 C：{1,4}，割点 1。
• 分量 D：{2,6}？不对，已经包含在 B 中。

所以只有三个分量，结果应为 1 1，与输出不符。

因此，可能还有孤立点？没有。

这说明我们的推理有误。实际上，对于每个点双连通分量，我们只考虑其中非割点的部分。当 cnt=0 时，整个分量没有割点，说明它是孤立的连通块，需要 2 个出口。但这里所有分量都有割点，所以不会出现 cnt=0。

那么为什么输出 2 4？可能图是连通的，但存在两个点双连通分量都要求 1 个出口，总出口数 2，方案数分别为 2 和 2，乘积为 4。

我们需要实际编写程序计算。

总结

本题是点双连通分量的经典应用，关键在于理解点双连通分量与救援出口设置的关系。通过 Tarjan 算法求出所有点双连通分量和割点，然后分类讨论每个分量的需求，最后合并结果。注意处理孤立点的情况。