矿场搭建

题目描述

Y 同学正在负责某个煤矿工地的安全规划工作。该工地可以抽象为一个无向图，图中包含若干个挖煤点（顶点）以及连接这些挖煤点的双向隧道（边）。

为了确保安全，Y 同学需要在部分挖煤点设立救援出口。要求满足：无论哪一个单一的挖煤点发生坍塌（即从图中删除任意一个顶点及其相连的所有边），其余的所有正常挖煤点都必须能够通过未坍塌的隧道到达至少一个设有救援出口的挖煤点。

请你编写程序，计算出 Y 同学至少需要设置多少个救援出口，以及在保证出口数量最少的前提下，共有多少种不同的救援出口设置方案。

输入格式

输入包含多组测试数据。

对于每组测试数据： 第一行包含一个正整数 $N$，表示工地的隧道数量。 接下来的 $N$ 行，每行包含两个由空格隔开的正整数 $S$ 和 $T$，表示挖煤点 $S$ 与挖煤点 $T$ 之间有一条双向隧道直接连接。

输入数据以一行包含一个整数 $0$ 作为结束标志。

输出格式

对于每组测试数据，输出一行。

第 $i$ 组数据的输出必须严格以 Case i: 开头（注意大小写，Case 与 i 之间有一个空格，i 与冒号 : 之间无空格，冒号之后有一个空格）。

其后输出两个由空格隔开的正整数：第一个正整数表示至少需要设置的救援出口数量，第二个正整数表示不同最少救援出口的设置方案总数。

样例

样例输入 #1

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

样例输出 #1

Case 1: 2 4
Case 2: 4 1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 500$。 对于每组数据，设 $M$ 为该组数据中所有 $S$ 和 $T$ 的最大值，保证 $1 \le M \le 10^3$，各组数据中出现的挖煤点编号集合恰好为 $\{1, 2, \dots, M\}$，且这 $M$ 个挖煤点构成的无向图连通。