AT_past202010_m 筆塗り

[problemUrl]: https://atcoder.jp/contests/past202010-open/tasks/past202010_m $ 1 $ から $ N $ の番号がついた $ N $ 個の頂点からなる木が与えられます。 $ 1 $ から $ N-1 $ の番号がついた $ N-1 $ 本の辺があり、辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を双方向につないでいます。 それぞれの辺には色を塗ることができます。色は $ 0 $ 以上 $ 10^5 $ 以下の整数で表されます。 はじめ、全ての辺は色 $ 0 $ で塗られています。 この木に対して、$ Q $ 回操作が行われます。$ i $ 回目の操作では、頂点 $ u_i $ と頂点 $ v_i $ の最短経路上にある辺の色が全て色 $ c_i $ で上書きされます。 $ Q $ 回の操作後、辺 $ 1,2,\ldots,N-1 $ がどの色で塗られているかを調べてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ u_1 $ $ v_1 $ $ c_1 $ $ \vdots $ $ u_Q $ $ v_Q $ $ c_Q $

$ N-1 $ 行出力せよ。$ i $ 行目では、辺 $ i $ に塗られている色を出力せよ。

### 注意 この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,\ b_i,u_i,v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - $ 1\ \leq\ c_i\ \leq\ 10^5 $ - 与えられるグラフは木 ### Sample Explanation 1 \- はじめ、全ての辺は色 $ 0 $ で塗られています。 - $ 1 $ 回目の操作では辺 $ 1 $、$ 2 $ の色が色 $ 10 $ で上書きされます。 - $ 2 $ 回目の操作では辺 $ 1 $ の色が色 $ 5 $ で上書きされます。 - 最終的に辺 $ 1,2,3 $ はそれぞれ、$ 5,10,0 $ で塗られています。