Description

你在森林中已经走了好几个小时，现在你只想回家。

这片森林里有 $N$ 个空地，编号为 $1, 2, \dots, N$。你现在位于空地 $1$，必须到达空地 $N$ 才能离开森林。每个空地 $1$ 到 $N-1$ 都有一条左路和一条右路通往其他空地，同时也可能有若干条单向小路通向这里。不幸的是，这片森林闹鬼，你每次进入一个空地时，两条出口中必有一条会被神秘的树木挡住。具体来说，在你第 $k$ 次进入某个空地时：

• 如果 $k$ 是奇数，你必须走左路离开该空地；
• 如果 $k$ 是偶数，你必须走右路离开该空地；
• 所有路径都是单向的，因此每一步你都别无选择：只能沿着唯一未被封锁的出口前进。

因此，你第一次到达空地 $1$ 时，会走左路离开。如果以后第二次回到空地 $1$，则会走右路离开；第三次又走左路，如此循环。

你从空地 $1$ 出发，到达空地 $N$ 时即可离开森林。你需要经过多少条路径才能走出森林？

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组首先一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $L_i$ 和 $R_i$。$L_i$ 表示从空地 $i$ 走左路会到达的空地编号，$R_i$ 表示从空地 $i$ 走右路会到达的空地编号。

空地 $N$ 没有出口，因为到达这里就算完成。

Output Format

对于每个测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为到达空地 $N$ 所需经过的路径数。如果永远无法到达空地 $N$，则输出 "Infinity"。

2
4
2 1
3 1
2 4
3
2 2
1 2

Case #1: 8
Case #2: Infinity

Hint

样例说明

在第一个样例中，你在森林中的路线如下表所示：

限制条件

• $1 \leq T \leq 30$
• 对所有 $i$，$1 \leq L_i, R_i \leq N$

测试集 1（5 分，结果可见）

• $2 \leq N \leq 10$

测试集 2（46 分，结果隐藏）

• $2 \leq N \leq 40$

翻译由 ChatGPT-4.1 完成。