microhhh的回城

时间限制: 5000 ms 内存限制: 200000 kb
总通过人数: 3 总提交人数: 4

题目描述

在雷达发现jhljx后,microhhh立即展开偷袭,发射了2枚GBU-32联合直接攻击弹药(Joint Direct Attack Munition, JDAM ),将jhljx的基地炸了个底朝天。jhljx也立马升空作战,无奈被2枚AIM-120导弹和2枚AIM-9导弹击中,被迫逃到深山老林去,flysnow被她的伙伴接走,microhhh一战告捷,启动回城传送系统。

microhhh有n个基地,然而回城系统不知什么时候出了点问题,无法确定会回到哪个基地。假设时空隧道可以简化为如下图所示

顶端为microhhh持有的传送器编号(编号从0 - n-1)可以通过时空隧道到达基地(时空隧道底端)(编号从0 - n-1)。假设n条时空隧道(从左到右编号0 - n-1)。编号为i的传送器最初在编号为i的时空隧道顶端。每条时间隧道的长度都为l 。另外,有水平的桥梁(i,k),表示在距顶端相同的长度k(k为整数)处,连接两条相邻的时间隧道i和i+1(0<k< l)。另外,两条相邻的桥梁不能在同一长度,也就是说,不能同时有桥梁(i,k)和(i+1,k)。
编号为i的传送器通过上图所示确定到达的基地。它会从i号时间隧道顶端开始往下走。只要它遇到了时间隧道和桥梁的交叉口,他就必须转弯,他可以沿着桥梁向左或向右,或沿着时间隧道往下走。最终会走到j号时间隧道底端,到达j号基地。

上图有6条时间隧道和10条桥梁。编号为1的传送器从时间隧道1往下走。首先他到达桥梁(1,1),转弯走向时空隧道2,继续往下。接着它到了桥梁(2,3),转弯走向时空隧道3。按图上的路径走啊走,到达了4号基地。 现在请你确定每个传送器到达的基地。上一个例子的输出应为3,4,1,0,5,2,因为0号会到达3号基地,1号会达到4号基地,依此类推。
数据范围
1 ≤ n ≤ 10000,n为时间隧道数量
1 ≤ m ≤ 100000,m为桥梁数量
1 ≤ l ≤ 10000,l为时间隧道长度

输入

第一行为数据组数c,表示共c组数据。
每组数据第一行为n,m,l,分别表示时空隧道数量,桥梁数量,时间隧道长度。接下来m行,每行包含两个整数i和k,表示桥梁(i,k)

输出

每组数据输出1行,按顺序输出编号从0 - n-1的入口到达的基地编号。注意需要输出Case i #:

输入样例

1 
6 10 8 
0 2 
2 6 
0 7 
1 1 
4 2 
4 5 
1 4 
2 3 
3 4 
4 7

输出样例

Case 1 #: 3 4 1 0 5 2

microhhh的hint

仔细看样例的空格,冒号为英文冒号,防止RPE。能过样例得到0.1分说明基本的情况可以通过,再接再厉好好改!(这题真的不难。。。)
powered by BUAA Summer Training 2015.08.01

相关推荐