← 返回题目列表

AtCoder · joi2022_yo1c_d

D. 移动球

中文机器翻译题面 查看原题

配点: 100 点

問題文

N 球, 它们的编号最大为1 减去 N 。另外,你可以放任意数量的球。 有 N 个盒子,每个盒子有 它们的编号最大为 1 减去 N 。

箱 i (1 \leqq i \leqq N) 最初有一个球 包括 i 。

JOI葵,一名高中生,从这种状态开始对盒子和球做出反应。 执行了 M 操作。j 回目 (1 \leqq j \leqq M)的操作如下进行。

  • 球 X_j 的盒子并将球从该盒子中取出。 摘录 X_j 。然后是盒子 球到 Y_j 输入 X_j 。

葵 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 的盒子的编号。


入力例 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

出力例 4

4
1
3
1