ボールの移動 (Moving Balls)

Unrated

日本語

Language

Statement

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

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

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

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

\(1 \leqq N \leqq 2\,000\)．
\(1 \leqq M \leqq 2\,000\)．
\(1 \leqq X_j \leqq N\) (\(1 \leqq j \leqq M\))．
\(1 \leqq Y_j \leqq N\) (\(1 \leqq j \leqq M\))．
入力される値はすべて整数である．

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\)
\(X_1\) \(Y_1\)
\(X_2\) \(Y_2\)
\(\vdots\)
\(X_M\) \(Y_M\)

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

Sample input 1

Sample output 1

3
1
2

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

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

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

Sample input 2

Sample output 2

1
2
3

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

Sample input 3

4 2
1 3
2 4

Sample output 3

Sample input 4

Sample output 4