Mine Setup

Problem Source

HNOI 2012

Problem Description

A coal mine site can be viewed as an undirected graph formed by tunnels connecting coal-digging points. For safety, it is desired that if an accident happens at the site, every worker at every digging point has an escape route to a rescue exit.

Therefore the mine owner decides to set up rescue exits at some digging points, so that no matter which single digging point collapses, the workers at all other digging points still have a path to some rescue exit.

Write a program to compute the minimum number of rescue exits that must be set up, and the total number of different ways to set up this minimum number of rescue exits.

Input Format

The input file contains several test cases. For each case the first line is a positive integer $N$ ($N \leq 500$), the number of tunnels at the site; the next $N$ lines each contain two integers $S, T$ ($1 \leq S, T \leq 1000$) separated by a space, meaning digging point $S$ and digging point $T$ are directly connected by a tunnel. The input ends with a line containing $0$.

For each test case, it is guaranteed that all the points that appear in the input are connected.

Output Format

Output one line per test case. The $i$-th line starts with Case i:, followed by two positive integers separated by a space: the first is the minimum number of rescue exits needed for the $i$-th test case, and the second is the total number of different ways to set up that minimum number. The input guarantees the answer is less than $2^{64}$.

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

The four solutions for Case 1 are $(2,4),\ (3,4),\ (4,5),\ (4,6)$; the one solution for Case 2 is $(4,5,6,7)$.