分数: 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。 见下图:
- 在此示例中, 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