AT_agc012_b [AGC012B] Splatter Painting

イカ喜欢给图的顶点涂色。 给定一个由 $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 \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 翻译