Description

A coal mining site can be viewed as an undirected graph where tunnels connect mining points. For safety, we want that in case of an accident, all miners at the remaining mining points can have a way out to reach a rescue exit. Therefore, the owner decides to set up rescue exits at some mining points so that no matter which single mining point collapses, workers at all other mining points still have a path to a rescue exit.

Please write a program to compute the minimum number of rescue exits required, as well as the total number of distinct configurations that achieve this minimum.

Input Format

The input file contains multiple test cases.

For each test case, the first line contains a positive integer $N\ (N \le 500)$, the number of tunnels.

Each of the next $N$ lines contains two integers $S$ and $T$ separated by a space, indicating that mining point $S$ is directly connected to mining point $T$ by a tunnel.

The input ends with a single $0$.

Output Format

For each test case, output one line.

The $i$-th test case output starts with $\verb!Case i: !$ (note the letter case; there is a space between $\verb!Case!$ and $\verb!i!$, no space between $\verb!i!$ and $\verb!:!$, and there is one space after $\verb!:!$).

After that, output two space-separated positive integers: the first is the minimum number of rescue exits required for the $i$-th test case, and the second is the number of distinct configurations achieving this minimum.

The testdata guarantees the answer is less than $2^{64}$. Refer to the sample input and output format.

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

Hint

Sample Explanation

• The four solutions for Case 1 are $(2, 4)$, $(3, 4)$, $(4, 5)$, $(4, 6)$.
• One solution for Case 2 is $(4, 5, 6, 7)$.

Constraints

For each test case, let $m$ be the maximum value among all $S$ and $T$ in that case. Then:

• $1 \le m \le 10^3$.
• The set of vertices formed by all $S$ and $T$ values is $V \subseteq [1, m] \cap \mathbb{Z}$.
• The graph induced by $V$ is connected.

Translated by ChatGPT 5