012 - ボールの移動 (Moving Balls)
時間制限 2 秒 / メモリ制限 1024 MB / 得点 1 / x 7 /
問題
N 個のボールがあり,1 から N までの番号が付けられている.また,何個でもボールを入れることのできる N 個の箱があり,箱には 1 から N までの番号が付けられている.
箱 i (1 ≦ i ≦ N) には最初,ボール i が入っていた.
JOI 高校の生徒である葵は,この状態から箱とボールに対して M 回の操作を行った.j 回目 (1 ≦ j ≦ M) の操作は,次のように行われた.
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $X_1$ $Y_1$ $X_2$ $Y_2$ $:$ $X_M$ $Y_M$
出力
N 行で出力せよ.i 行目 (1 ≦ i ≦ N) には,葵が M 回の操作をすべて終えた後,ボール i が入っている箱の番号を出力せよ.
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N \leq 2000$
- $1 \leq M \leq 2000$
- $1 \leq X_j \leq N(1 \leq j \leq M)$
- $1 \leq Y_j \leq N(1 \leq j \leq M)$
- 入力される値はすべて整数である
入出力例
入力例1
3 4 1 2 3 2 2 1 1 3
出力例1
3 1 2
最初,箱 1 にはボール 1 が,箱 2 にはボール 2 が,箱 3 にはボール 3 が入っていた.
葵は以下のように,4 回の操作を行った.
入力例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
出力例4
4 1 3 1