#1418. [GCJ 2012 Finals] Shifting Paths
[GCJ 2012 Finals] Shifting Paths
题目描述
你在森林中已经走了好几个小时,现在你只想回家。
这片森林里有 个空地,编号为 。你现在位于空地 ,必须到达空地 才能离开森林。每个空地 到 都有一条左路和一条右路通往其他空地,同时也可能有若干条单向小路通向这里。不幸的是,这片森林闹鬼,你每次进入一个空地时,两条出口中必有一条会被神秘的树木挡住。具体来说,在你第 次进入某个空地时:
- 如果 是奇数,你必须走左路离开该空地;
- 如果 是偶数,你必须走右路离开该空地;
- 所有路径都是单向的,因此每一步你都别无选择:只能沿着唯一未被封锁的出口前进。
因此,你第一次到达空地 时,会走左路离开。如果以后第二次回到空地 ,则会走右路离开;第三次又走左路,如此循环。
你从空地 出发,到达空地 时即可离开森林。你需要经过多少条路径才能走出森林?
输入格式
输入的第一行为测试用例数 。接下来有 组测试数据,每组首先一行一个整数 。
接下来 行,每行两个整数 和 。 表示从空地 走左路会到达的空地编号, 表示从空地 走右路会到达的空地编号。
空地 没有出口,因为到达这里就算完成。
输出格式
对于每个测试用例,输出一行 "Case #: ",其中 为测试用例编号(从 1 开始), 为到达空地 所需经过的路径数。如果永远无法到达空地 ,则输出 "Infinity"。
样例
2
4
2 1
3 1
2 4
3
2 2
1 2
Case #1: 8
Case #2: Infinity
题目来源:洛谷 P13336