← 返回题目列表

AtCoder · arc056_b

B. 停车场

中文机器翻译题面 查看原题

問題文

在停车场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
../../assets/statements/atcoder/arc056_b/001-386805a6190fee32b976bbf6.webp

如果蓝色圆圈是空车位,红色圆圈是有汽车的车位,则车位将按照上图所示的顺序填满。4汽车无法停车。


入力例3

5 5 5
1 4
4 3
3 2
2 5
5 1

出力例3

1
2
5