AT_past202005_k コンテナの移動

[problemUrl]: https://atcoder.jp/contests/past202005-open/tasks/past202005_k $ 1,2,\ldots,N $ の番号がついた $ N $ 個の机と、$ 1,2,\ldots,N $ の番号がついた $ N $ 個のコンテナがあります。 机の上には複数のコンテナを積み上げることができます。 はじめ、コンテナ $ i $ は机 $ i $ の上に置かれています。 $ Q $ 個のクエリが与えられるので、順番に処理してください。 $ i $ 番目のクエリでは机 $ f_i $ にあるコンテナ $ x_i $ とその上に積み上げられたコンテナたちを、机 $ t_i $ に順番を変えずに移動させてください。 このとき、机 $ t_i $ にすでにコンテナがある場合、以下の図のように既に積み上げられたコンテナたちの上にさらに積み上げるように移動させる必要があります。  - $ f=1,t=2,x=4 $ の例です。机 $ 1 $ にあるコンテナ $ 4 $ とその上にあるコンテナ $ 2 $ を机 $ 2 $ の上に動かします。 - 机 $ 2 $ の上にはコンテナ $ 3,5 $ が置かれているので、その上にさらに積み上げる必要があります。 $ Q $ 個のクエリを処理した後、それぞれのコンテナがどの机の上にあるかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ f_1 $ $ t_1 $ $ x_1 $ $ \vdots $ $ f_{Q} $ $ t_{Q} $ $ x_{Q} $

$ N $ 行出力せよ。$ i $ 行目にはコンテナ $ i $ が置かれている机の番号を出力せよ。

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 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 $ 上にあることが保証される ### Sample Explanation 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 $ にあります。