John Digger 拥有一座大型的 illudium phosdex 矿。这座矿由一系列在各个大型枢纽处汇合的隧道组成。与其他矿主不同，Digger 确实关心工人的福利，并对矿井的布局感到担忧。具体来说，他担心可能会有一个枢纽在发生坍塌时，会将矿井某一部分的工人与其他工人隔离开来（如你所知，illudium phosdex 非常不稳定）。为了应对这种情况，他希望在枢纽处安装特殊的逃生井，直通地面。他可以在每个枢纽处都安装一个逃生井，但 Digger 并没有那么关心他的工人。相反，他希望安装最少数量的逃生井，使得如果任何一个枢纽发生坍塌，所有在坍塌中幸存的工人都能有一条通往地面的路径。

编写一个程序，计算所需的最少逃生井数量，以及安装这些最少数量逃生井的总方案数。

输入格式

输入包含多组测试数据。每组数据的第一行包含一个正整数 $N$ ($N \le 5 \cdot 10^4$)，表示矿井隧道的数量。接下来 $N$ 行，每行包含两个不同的整数 $s$ 和 $t$，表示枢纽编号。枢纽编号从 1 开始连续编号。每对枢纽之间最多由一条隧道连接。每组矿井隧道构成一个连通单元（即，你可以从任何一个枢纽到达其他任何枢纽）。

最后一组测试数据后跟有一行，包含一个单独的零。

输出格式

对于每组测试数据，显示其用例编号，随后是该矿井系统所需的最少逃生井数量，以及安装这些逃生井的总方案数。你可以假设结果适合存储在有符号 64 位整数中。

请遵循样例输出的格式。

样例

输入 1

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

输出 1

Case 1: 2 4
Case 2: 4 1