1348. [HNOI 2012] 矿场搭建

【题目描述】

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。（注：根据数据，此处无向图保证初始连通）by wzw

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

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

【输入格式】

输入有若干组数据。

每组数据的第一行是一个正整数 $N$，表示工地的隧道数。

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

输入数据以 $0$ 结尾。

【输出格式】

输出有若干行。

其中第 $i$ 行以 $Case\ i:$ 开始（注意大小写，$Case$ 与 $i$ 之间有空格，$i$ 与 $:$ 之间无空格，$:$ 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 $i$ 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 $i$ 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 $2^{64}$。

输出格式参照以下输入输出样例。

【样例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

【样例2】

点击下载样例2

【样例1说明】

$Case\ 1$ 的四组解分别是 $(2,4),(3,4),(4,5),(4,6)$；

$Case\ 2$ 的一组解为 $(4,5,6,7)$。

【样例2】

对于 $10\%$ 的数据，$N \leq 10$。

对于 $70\%$ 的数据，$数据组数 = 1$。

对于 $100\%$ 的数据，$数据组数 \leq 3，N \leq 300$。