LOJ10099矿场搭建

柔光的暖阳◎ 2021-11-10 14:58 293阅读 0赞

HNOI 2012

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

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

#### 输入格式 ####

输入文件有若干组数据，每组数据的第一行是一个正整数N，表示工地的隧道数，接下来的N行每行是用空格隔开的两个整数 S 和  T，表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。

#### 输出格式 ####

输入文件中有多少组数据，输出文件中就有多少行。每行对应一组输入数据的结果。

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

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

#### 样例 ####

#### 样例输入 ####

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

#### 样例解释 ####

`Case 1` 的四组解分别是 (2,4),(2,5),(4,6)，(4,5)；

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

#### 数据范围与提示 ####

N<=500，输入数据保证答案小于2^64 。

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_