AT_agc012_b [AGC012B] Splatter Painting

[problemUrl]: https://atcoder.jp/contests/agc012/tasks/agc012_b イカはグラフの頂点に色を塗るのが好きです。 $ 1 $ から $ N $ までの番号がついた $ N $ 個の頂点と $ M $ 本の辺からなる単純無向グラフが与えられます。 全ての頂点ははじめ、色 $ 0 $ で塗られています。$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を双方向につなぐ長さ $ 1 $ の辺です。 イカはこのグラフに対して $ Q $ 回の操作を行いました。 $ i $ 回目の操作では、頂点 $ v_i $ から距離 $ d_i $ 以内にあるような頂点たち全ての色を色 $ c_i $ で上書きしました。 $ Q $ 回の操作後において、各頂点がどの色で塗られているか調べてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ : $ $ a_{M} $ $ b_{M} $ $ Q $ $ v_1 $ $ d_1 $ $ c_1 $ $ : $ $ v_{Q} $ $ d_{Q} $ $ c_{Q} $

答えを $ N $ 行に出力せよ。 $ i $ 行目では $ Q $ 回の操作後における頂点 $ i $ の色を出力せよ。

### 制約 - $ 1\ ≦\ N,M,Q\ ≦\ 10^5 $ - $ 1\ ≦\ a_i,b_i,v_i\ ≦\ N $ - $ a_i\ ≠\ b_i $ - $ 0\ ≦\ d_i\ ≦\ 10 $ - $ 1\ ≦\ c_i\ ≦10^5 $ - $ d_i,\ c_i $ いずれも整数 - 与えられるグラフに自己ループや多重辺は存在しない ### 部分点 - $ 1\ ≦\ N,M,Q\ ≦\ 2{,}000 $ を満たすデータセットに正解した場合は、部分点として $ 200 $ 点が与えられる。 ### Sample Explanation 1 はじめ、各頂点は色 $ 0 $ で塗られています。 $ 1 $ 回目の操作により、頂点 $ 5,6 $ が色 $ 1 $ で塗られます。 $ 2 $ 回目の操作により、頂点 $ 1,2,3,4,5 $ が色 $ 2 $ で塗られます。 !\[2ab7e180230b159d42d35ea7e555b3b0.png\](https://atcoder.jp/img/agc012/2ab7e180230b159d42d35ea7e555b3b0.png) ### Sample Explanation 2 与えられるグラフは連結とは限りません。