P13336 [GCJ 2012 Finals] Shifting Paths

你在森林中已经走了好几个小时，现在你只想回家。 这片森林里有 $N$ 个空地，编号为 $1, 2, \dots, N$。你现在位于空地 $1$，必须到达空地 $N$ 才能离开森林。每个空地 $1$ 到 $N-1$ 都有一条左路和一条右路通往其他空地，同时也可能有若干条单向小路通向这里。不幸的是，这片森林闹鬼，你每次进入一个空地时，两条出口中必有一条会被神秘的树木挡住。具体来说，在你第 $k$ 次进入某个空地时： - 如果 $k$ 是奇数，你必须走左路离开该空地； - 如果 $k$ 是偶数，你必须走右路离开该空地； - 所有路径都是单向的，因此每一步你都别无选择：只能沿着唯一未被封锁的出口前进。 因此，你第一次到达空地 $1$ 时，会走左路离开。如果以后第二次回到空地 $1$，则会走右路离开；第三次又走左路，如此循环。 你从空地 $1$ 出发，到达空地 $N$ 时即可离开森林。你需要经过多少条路径才能走出森林？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组首先一行一个整数 $N$。 接下来 $N-1$ 行，每行两个整数 $L_i$ 和 $R_i$。$L_i$ 表示从空地 $i$ 走左路会到达的空地编号，$R_i$ 表示从空地 $i$ 走右路会到达的空地编号。 空地 $N$ 没有出口，因为到达这里就算完成。

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

**样例说明** 在第一个样例中，你在森林中的路线如下表所示： | 路径数 | 当前空地 | 离开方向 | |:-:|:-:|:-:| | 0 | 1 | 左 | | 1 | 2 | 左 | | 2 | 3 | 左 | | 3 | 2 | 右 | | 4 | 1 | 右 | | 5 | 1 | 左 | | 6 | 2 | 左 | | 7 | 3 | 右 | | 8 | 4 | - | ## 限制条件 - $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 完成。