[AGC012B] Splatter Painting

题意翻译

给一个 $n$ 个点 $m$ 条边的无向图,有 $q$ 次操作。第 $i$ 次操作给出 $v,d,c$,把所有到点 $v$ 的距离不超过 $d$ 的点都染上颜色 $c$。可以覆盖之前染上的颜色。 问最后每个点的颜色。 $1\le n, m, q, c \le 10^5$,$0\le d \le 10$。

题目描述

[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

7 7
1 2
1 3
1 4
4 5
5 6
5 7
2 3
2
6 1 1
1 2 2

输出样例 #1

2
2
2
2
2
1
0

输入样例 #2

14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3

输出样例 #2

1
0
3
1
5
5
3
3
6
1
3
4
5
3

说明

### 制約 - $ 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 与えられるグラフは連結とは限りません。