AtCoder Regular Contest 056

B - 駐車場


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

駐車場で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
https://arc056.contest.atcoder.jp/img/arc/056/vafbafvasrf/imgB.png

青い円を空いている駐車スペース、赤い円を車のいる駐車スペースとすると、上図のような順番で駐車スペースが埋まっていき、4番目の車は駐めることができません。


入力例3

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

出力例3

1
2
5

Submit提出する