問題文
在停车场N一个人正在尝试停车。 停车场是N可用停车位 编号至1从N。另外,2一条道路连接两个方向的两个停车位。M书籍可用,i路径是u_i第一个停车位和 连接第v_i个停车位。 停车位S与停车场入口相连。 不知怎么的,第
i人 您似乎只想停在i停车位。为此,从停车场入口处,经过无人停放车辆的停车位以及连接停车位的道路。i当我无法到达第二个停车位时,我最终没有停车就离开了。 来自第
1人N人将按顺序来到停车场。请按从小到大的顺序打印出最终停入停车场的人数。
制約
- 1 ≦ N, M ≦ 2*10^5
- 1≦u_i, v_i≦N
- u_i ≠ v_i
- 1 ≦ S ≦ N
- 所有停车位均可从入口处经道路和停车位到达。 如果所有满足
部分点
- M ≦ 2,000 的测试用例都被正确回答,将给出部分分数。40点。 如果您对除上述数据集之外的所有满足
入力
输入是按以下格式从标准输入给出的。
N M S u_1 v_1 : u_M v_M
出力
最终停入停车场的人数按升序排列1逐行输出。
入力例1
3 3 2 1 2 2 3 1 3
出力例1
1 2
1第二辆车在停车位 您可以把车停在那里,这样您就可以前往1。 第 2第二辆车在停车位 您可以把车停在那里,这样您就可以前往2。 第 3辆车是2停车位被第二辆车挡住 我要离开,因为我无法前往3。
入力例2
5 6 5 1 5 3 5 3 2 4 1 1 2 4 3
出力例2
1 2 3 5
如果蓝色圆圈是空车位,红色圆圈是有汽车的车位,则车位将按照上图所示的顺序填满。4汽车无法停车。
入力例3
5 5 5 1 4 4 3 3 2 2 5 5 1
出力例3
1 2 5