题目描述

イカはグラフの頂点に色を塗るのが好きです。

$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$ の色を出力せよ。

题目大意

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

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

2
2
2
2
2
1
0

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

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$ で塗られます。 

Sample Explanation 2

与えられるグラフは連結とは限りません。