← 返回题目列表

AtCoder · past202005_k

K. 移动集装箱

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

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有 N 桌子编号 1,2,\ldots,N,和 N 集装箱编号 1,2,\ldots,N。 我们可以在一张桌子上堆放多个容器。

最初,容器 i 放在桌子上 i.

我们将要求您处理 Q 按顺序查询。 在 i-第查询,移动容器 x_i 以及办公桌上方的容器 f_i 到办公桌 t_i,不改变它们的堆积顺序。

这里,如果桌面上已经有一些容器 t_i,放置容器 x_i 在桌子上的容器顶部 t_i。 见下图:

510ebd9bf498cbd3c0e7b61b902ef09c.png
  • 在此示例中, f=1,t=2,x=4。我们正在搬运集装箱 4 及其上方的容器 - Container 2 - 来自办公桌 1 到办公桌 2.
  • 由于已经有一些容器 - Container 3 和 5 - 在桌子上 2,所以我们放置 Container 4 在他们上面。

处理后 Q 查询,找到每个容器所在的桌子。

约束

  • 输入中的所有值都是整数。
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq f_i, t_i, x_i\leq N
  • f_i \neq t_i
  • 集装箱 x_i 保证放在桌子上 f_i 给出查询时。

输入

输入由标准输入按以下格式给出:

N Q
f_1 t_1 x_1
\vdots
f_{Q} t_{Q} x_{Q}

输出

打印 N 行。的 i- 第行应包含代表容器所在桌子的整数 i 谎言。


示例输入 1

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

示例输出 1

3
3
1
  • 在第一个查询中,我们移动 Container 1 来自办公桌 1 到办公桌 2。集装箱 2 已在桌面上 2,所以我们放置 Container 1 在它上面。
  • 在第二个查询中,我们移动 Container 2 及其上方的容器 - Container 1 - 来自办公桌 2 到办公桌 3。集装箱 3 已在桌面上 3,所以我们放置 Container 2 和 1 在它上面。
  • 在第三个查询中,我们移动 Container 3 及其上方的容器 - 容器 2 和 1 - 来自办公桌 2 到办公桌 1.
  • 在第四个查询中,我们移动 Container 2 及其上方的容器 - Container 1 - 来自办公桌 1 到办公桌 3.
  • 最后,容器 1 和 2 躺在桌子上 3和容器 3 躺在桌子上 1.

示例输入 2

10 20
3 6 3
6 5 6
10 8 10
5 7 3
1 3 1
4 10 4
5 4 6
10 7 4
7 9 3
9 8 4
8 1 4
3 7 1
2 3 2
9 8 3
8 1 10
8 2 8
9 10 9
2 1 8
4 9 6
1 7 4

示例输出 2

7
3
7
7
5
9
7
7
10
7