题目描述

イカ喜欢给图的顶点涂色。

给定一个由 $N$ 个编号为 $1$ 至 $N$ 的顶点和 $M$ 条边组成的简单无向图。所有顶点初始时都被涂有颜色 $0$。第 $i$ 条边连接顶点 $a_i$ 与顶点 $b_i$，边的长度为 $1$，且是双向的。

イカ对这张图进行了 $Q$ 次操作。在第 $i$ 次操作时，将距离顶点 $v_i$ 不超过 $d_i$ 的所有顶点的颜色覆盖为颜色 $c_i$。

请在 $Q$ 次操作结束后，输出每个顶点被涂的颜色。

输入格式

输入以以下形式从标准输入中给出。

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$Q$
$v_1$ $d_1$ $c_1$
$\vdots$
$v_Q$ $d_Q$ $c_Q$

输出格式

输出 $N$ 行。第 $i$ 行输出第 $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

输出

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

输出

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

说明/提示

条件限制

• $1 \leq N, M, Q \leq 10^5$
• $1 \leq a_i, b_i, v_i \leq N$
• $a_i \neq b_i$
• $0 \leq d_i \leq 10$
• $1 \leq c_i \leq 10^5$
• $d_i$ 与 $c_i$ 都是整数
• 输入的图中不存在自环和重边

部分得分

• 若能通过满足 $1 \leq N, M, Q \leq 2{,}000$ 的数据集，可获得 $200$ 分的部分分数。

样例解释 1

初始时，每个顶点的颜色为 $0$。经过第 $1$ 次操作后，顶点 $5,6$ 的颜色被覆盖为 $1$。第 $2$ 次操作后，顶点 $1,2,3,4,5$ 的颜色被覆盖为 $2$。

样例解释 2

给定的图不一定是连通的。

由 ChatGPT 5 翻译