Description

Original source: HNOI 2012

A coal mine site can be viewed as an undirected graph composed of tunnels connecting coal mining points. For safety reasons, it is desired that in the event of an accident, all workers at any coal mining point can have an escape route to a rescue exit. Therefore, the mine owner decides to establish rescue exits at certain coal mining points, ensuring that no matter which coal mining point collapses, workers at other coal mining points have a path to a rescue exit.

Write a program to calculate the minimum number of rescue exits needed and the total number of different configurations for these minimum rescue exits.

Input Format

The input file contains several sets of data. The first line of each set is a positive integer $N$, representing the number of tunnels in the site. The following $N$ lines each contain two integers $S$ and $T$ separated by a space, indicating that coal mining point $S$ is directly connected to coal mining point $T$ by a tunnel. The input data ends with $0$.

Output Format

The output file should have as many lines as there are sets of data in the input file. Each line corresponds to the result of a set of input data.

The $i$-th line starts with Case i: (note the capitalization, with a space between Case and i, no space between i and :, and a space after :), followed by two positive integers separated by a space. The first integer represents the minimum number of rescue exits required for the $i$-th set of input data, and the second integer represents the total number of different configurations for these minimum rescue exits.

Refer to the sample input and output for the specific format.

Sample 1

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)$.

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

Data Range and Hints

$N\le 500$, the input data guarantees the answer is less than $2^{64}$.