#1418. [GCJ 2012 Finals] Shifting Paths

[GCJ 2012 Finals] Shifting Paths

题目描述

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

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

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

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

你从空地 11 出发,到达空地 NN 时即可离开森林。你需要经过多少条路径才能走出森林?

输入格式

输入的第一行为测试用例数 TT。接下来有 TT 组测试数据,每组首先一行一个整数 NN。

接下来 N−1N-1 行,每行两个整数 LiL_i 和 RiR_i。LiL_i 表示从空地 ii 走左路会到达的空地编号,RiR_i 表示从空地 ii 走右路会到达的空地编号。

空地 NN 没有出口,因为到达这里就算完成。

输出格式

对于每个测试用例,输出一行 "Case #xx: yy",其中 xx 为测试用例编号(从 1 开始),yy 为到达空地 NN 所需经过的路径数。如果永远无法到达空地 NN,则输出 "Infinity"。

样例

2
4
2 1
3 1
2 4
3
2 2
1 2
Case #1: 8
Case #2: Infinity

题目来源:洛谷 P13336