K - コンテナの移動 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1,2,\ldots,N の番号がついた N 個の机と、1,2,\ldots,N の番号がついた N 個のコンテナがあります。 机の上には複数のコンテナを積み上げることができます。

はじめ、コンテナ i は机 i の上に置かれています。

Q 個のクエリが与えられるので、順番に処理してください。 i 番目のクエリでは机 f_i にあるコンテナ x_i とその上に積み上げられたコンテナたちを、机 t_i に順番を変えずに移動させてください。

このとき、机 t_i にすでにコンテナがある場合、以下の図のように既に積み上げられたコンテナたちの上にさらに積み上げるように移動させる必要があります。

510ebd9bf498cbd3c0e7b61b902ef09c.png
  • f=1,t=2,x=4 の例です。机 1 にあるコンテナ 4 とその上にあるコンテナ 2 を机 2 の上に動かします。
  • 机 2 の上にはコンテナ 3,5 が置かれているので、その上にさらに積み上げる必要があります。

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
  • 1 番目のクエリで机 1 にあるコンテナ 1 を机 2 に移します。このとき、机 2 にはコンテナ 2 があるので、その上にコンテナ 1 を積み上げます。
  • 2 番目のクエリで机 2 にあるコンテナ 2 とその上にあるコンテナ 1 を机 3 に移します。このとき、机 3 にはコンテナ 3 があるので、その上にコンテナ 2,1 を積み上げます。
  • 3 番目のクエリで机 3 にあるコンテナ 3 とその上にあるコンテナ 2,1 を机 1 に移します。
  • 4 番目のクエリで机 1 にあるコンテナ 2 とその上にあるコンテナ 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

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N desks numbered 1,2,\ldots,N, and N containers numbered 1,2,\ldots,N. We can pile multiple containers on a desk.

Initially, Container i is placed on Desk i.

We will ask you to process Q queries in order. In the i-th query, move Container x_i and the containers above it from Desk f_i to Desk t_i, without changing the order they are piled in.

Here, if there are already some containers on Desk t_i, place Container x_i on top of the containers on Desk t_i. See the figure below:

510ebd9bf498cbd3c0e7b61b902ef09c.png
  • In this example, f=1,t=2,x=4. We are moving Container 4 and the container above it - Container 2 - from Desk 1 to Desk 2.
  • Since there are already some containers - Container 3 and 5 - on Desk 2, so we place Container 4 on top of them.

After processing the Q queries, find the desk on which each container lies.

Constraints

  • All values in input are integers.
  • 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
  • Container x_i is guaranteed to be placed on Desk f_i when the query is given.

Input

Input is given from Standard Input in the following format:

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

Output

Print N lines. The i-th line should contain the integer representing the desk on which Container i lies.

Sample Input 1

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

Sample Output 1

3
3
1
  • In the first query, we move Container 1 from Desk 1 to Desk 2. Container 2 is already on Desk 2, so we place Container 1 on top of it.
  • In the second query, we move Container 2 and the container above it - Container 1 - from Desk 2 to Desk 3. Container 3 is already on Desk 3, so we place Container 2 and 1 on top of it.
  • In the third query, we move Container 3 and the containers above it - Container 2 and 1 - from Desk 2 to Desk 1.
  • In the fourth query, we move Container 2 and the container above it - Container 1 - from Desk 1 to Desk 3.
  • In the end, Container 1 and 2 lie on Desk 3, and Container 3 lies on Desk 1.

Sample Input 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

Sample Output 2

7
3
7
7
5
9
7
7
10
7