AT_arc056_b [ARC056B] 駐車場

[problemUrl]: https://atcoder.jp/contests/arc056/tasks/arc056_b 駐車場で$ N $人が車を駐めようとしています。 駐車場は$ N $個の駐車スペースがあり$ 1 $から$ N $まで番号付けられています。また、$ 2 $つの駐車スペースを双方向に結ぶ道が$ M $本あり、$ i $番目の道は$ u_i $番目の駐車スペースと$ v_i $番目の駐車スペースを結んでいます。 駐車スペース$ S $は駐車場の入り口とつながっています。 $ i $番目の人は、どういうわけか$ i $番目の駐車スペースにしか車を駐めたくないようです。このため、駐車場の入り口から、まだ誰も車を駐めていない駐車スペースとそれらを結ぶ道を通って$ i $番目の駐車スペースに行くことができないとき、車を駐めずに帰ってしまいます。 $ 1 $番目の人から$ N $番目の人まで順番に駐車場にやってきます。最終的に駐車場に駐める人の番号を昇順に出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S $ $ u_1 $ $ v_1 $ : $ u_M $ $ v_M $

最終的に駐車場に駐める人の番号を昇順に$ 1 $行ずつ出力せよ。

### 制約 - $ 1\ ≦\ N,\ M\ ≦\ 2*10^5 $ - $ 1≦u_i,\ v_i≦N $ - $ u_i\ ≠\ v_i $ - $ 1\ ≦\ S\ ≦\ N $ - 全ての駐車スペースへは、入り口から道と駐車スペースを経由してたどり着くことができる ### 部分点 - $ M\ ≦\ 2,000 $ を満たすテストケース全てに正解した場合、部分点として$ 40 $点が与えられる。 ### Sample Explanation 1 $ 1 $番目の車は、駐車スペース$ 1 $に行くことができるためそこに駐めます。 $ 2 $番目の車は、駐車スペース$ 2 $に行くことができるためそこに駐めます。 $ 3 $番目の車は、$ 2 $番目の車に塞がれ駐車スペース$ 3 $に行くことができないため、帰ります。 ### Sample Explanation 2 !\[https://arc056.contest.atcoder.jp/img/arc/056/vafbafvasrf/imgB.png\](https://arc056.contest.atcoder.jp/img/arc/056/vafbafvasrf/imgB.png)青い円を空いている駐車スペース、赤い円を車のいる駐車スペースとすると、上図のような順番で駐車スペースが埋まっていき、$ 4 $番目の車は駐めることができません。