問題文

駐車場で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

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