分数: 700 点
问题陈述
Squid 喜欢在图中绘制顶点。
有一个简单的无向图,包括 N 顶点编号 1 通过 N,和 M 边缘。 最初,所有顶点都被涂上颜色 0。的 i第一条边双向连接两个顶点 a_i 和 b_i。每条边的长度为 1.
鱿鱼执行 Q 在此图上进行操作。在 i第次操作,他重新绘制了距离内的所有顶点 d_i 从顶点 v_i,彩色 c_i.
找到后面每个顶点的颜色 Q 操作。
约束
- 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 均为整数。
- 给定图中没有自环或多重边。
部分分数
- 200 通过满足以下条件的测试集将获得积分 1 ≤ N,M,Q ≤ 2{,}000.
输入
输入由标准输入按以下格式给出:
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第行,打印顶点的颜色 i 之后 Q 操作。
示例输入 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
最初,每个顶点都被涂上颜色 0。 在第一个操作中,顶点 5 和 6 重新涂上颜色 1。 在第二次操作中,顶点 1, 2, 3, 4 和 5 重新涂上颜色 2.
示例输入 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
给定的图形可能未连接。