← 返回题目列表

AtCoder · agc012_b

B. 飞溅绘画

中文机器翻译题面 查看原题

分数: 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.

2ab7e180230b159d42d35ea7e555b3b0.png


示例输入 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

给定的图形可能未连接。