Problem1099--「一本通 3.6 例 2」矿场搭建

1099: 「一本通 3.6 例 2」矿场搭建

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:HNOI 2012
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

Input

输入文件有若干组数据,每组数据的第一行是一个正整数 NNN,表示工地的隧道数,接下来的 NNN 行每行是用空格隔开的两个整数 SSSTTT ,表示挖煤点 SSS 与挖煤点 TTT 由隧道直接连接。输入数据以 000 结尾。

Output

输入文件中有多少组数据,输出文件中就有多少行。每行对应一组输入数据的结果。
其中第 iii 行以Case i:开始(注意大小写,Case与i之间有空格,i与:之间无空格,:之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 iii 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 iii 组输入数据不同最少救援出口的设置方案总数。
输出格式参照以下输入输出样例。

Sample Input

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

Sample Output

Case 1: 2 4
Case 2: 4 1

HINT

N≤500N\le 500N500,输入数据保证答案小于 2642^{64}264

Source/Category


Submit Status