煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

输入文件有若干组数据，每组数据的第一行是一个正整数 N，表示工地的隧道数。

接下来的 N 行每行是用空格隔开的两个整数 S 和 T（S \neq T），表示挖煤点 S 与挖煤点 T 由隧道直接连接。

输入数据以 0 结尾。

注意：

1. 每组数据的挖煤点的编号为 1 \sim Max，其中 Max 表示由隧道连接的挖煤点中，编号最大的挖煤点的编号。

2. 可能存在没有被隧道连接的挖煤点。对于这样的挖煤点，该点一定要设置救援出口，本题不考虑这类挖煤点坍塌后，该点的工人可以通过道路通向其他救援出口的情况。即：如果遇到没有被隧道连接的挖煤点，该点必定会被设置为救援出口，同时不影响本题的救援出口的设置方案数。

对于每组测试数据，输出结果占一行。

其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与 : 之间无空格，: 之后有空格）。

其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。

输入数据保证答案小于 2⁶⁴，输出格式参照以下输入输出样例。

数据范围

对于所有测试数据，1≤N≤500，1≤Max≤1000。

样例 1 解释

对于第 1 个 Case，四种设置方案分别是：(2,4)，(3,4)，(4,5)，(4,6)。

对于第 2 个 Case，设置方案为：(4,5,6,7)。

Tarjan割点双连通分量