Mining Your Own Business

A mine is a network of tunnels that meet at junctions. The junctions and tunnels form a connected network: from any junction you can reach any other junction through the tunnels.

The owner worries that if a junction collapses, workers in one part of the mine could be cut off from the rest. To guard against this, escape shafts to the surface can be installed at junctions. Installing a shaft at every junction would be wasteful, so instead install the minimum number of escape shafts such that, no matter which single junction collapses, every worker who survives the collapse still has a path through the remaining tunnels to a junction with a shaft.

Compute the minimum number of escape shafts required, and the total number of different ways to install that minimum number of shafts.

The input contains several test cases. The first line of each case contains a positive integer $N$ ($N \le 5 \cdot 10^4$), the number of tunnels. Each of the next $N$ lines contains two distinct integers $s$ and $t$, the numbers of the two junctions joined by a tunnel. Junctions are numbered consecutively starting at $1$. Each pair of junctions is joined by at most one tunnel, and the tunnels of each mine form a single connected network (you can get from any junction to any other).

The last test case is followed by a line containing a single zero.

For each test case, display its case number followed by the minimum number of escape shafts needed and the total number of ways these shafts can be installed. The result fits in a signed 64-bit integer. Use the format Case X: S W, where S is the minimum number of shafts and W is the number of ways.