第21回日本情報オリンピック　一次予選(第3回)

2021年11月22日
情報オリンピック日本委員会

問題文

N 個のボールがあり，1 から N までの番号が付けられている．また，何個でもボールを入れることのできる N 個の箱があり，箱には 1 から N までの番号が付けられている．

箱 i (1 ≦ i ≦ N) には最初，ボール i が入っていた．

JOI 高校の生徒である葵は，この状態から箱とボールに対して M 回の操作を行った．j 回目 (1 ≦ j ≦ M) の操作は，次のように行われた．

• ボール X_j が入っている箱を探し，その箱からボール X_j を取り出す．その後，箱 Y_j にボール X_j を入れる．

葵が M 回の操作をすべて終えた後，N 個のボールがそれぞれどの箱に入っているかを求めよ．

制約

• 1 ≦ N ≦ 2000．
• 1 ≦ M ≦ 2000．
• 1 ≦ X_j ≦ N (1 ≦ j ≦ M)．
• 1 ≦ Y_j ≦ N (1 ≦ j ≦ M)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．
N M
X₁ Y₁
X₂ Y₂
:
X_M Y_M

出力

N 行で出力せよ．i 行目 (1 ≦ i ≦ N) には，葵が M 回の操作をすべて終えた後，ボール i が入っている箱の番号を出力せよ．

入力例 1

3 4
1 2
3 2
2 1
1 3

出力例 1

3
1
2

最初，箱 1 にはボール 1 が，箱 2 にはボール 2 が，箱 3 にはボール 3 が入っていた．

葵は以下のように，4 回の操作を行った．

• 1 回目の操作では，ボール 1 を箱 1 から取り出した後，箱 2 に入れた．
• 2 回目の操作では，ボール 3 を箱 3 から取り出した後，箱 2 に入れた．
• 3 回目の操作では，ボール 2 を箱 2 から取り出した後，箱 1 に入れた．
• 4 回目の操作では，ボール 1 を箱 2 から取り出した後，箱 3 に入れた．

操作をすべて終えた後，ボール 1 は箱 3 ，ボール 2 は箱 1 ，ボール 3 は箱 2 に入っている．したがって，3,1,2 をこの順に改行区切りで出力する．

入力例 2

3 3
1 1
2 2
3 3

出力例 2

1
2
3

操作をすべて終えた後，ボール 1 は箱 1 ，ボール 2 は箱 2 ，ボール 3 は箱 3 に入っている．したがって，1,2,3 をこの順に改行区切りで出力する．

入力例 3

4 2
1 3
2 4

出力例 3

3
4
3
4

入力例 4

4 8
1 3
3 2
2 4
2 3
4 1
2 1
1 4
3 3

出力例 3

4
1
3
1