B - Splatter Painting Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700700 点

問題文

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

11 から NN までの番号がついた NN 個の頂点と MM 本の辺からなる単純無向グラフが与えられます。 全ての頂点ははじめ、色 00 で塗られています。ii 番目の辺は頂点 aia_i と頂点 bib_i を双方向につなぐ長さ 11 の辺です。

イカはこのグラフに対して QQ 回の操作を行いました。 ii 回目の操作では、頂点 viv_i から距離 did_i 以内にあるような頂点たち全ての色を色 cic_i で上書きしました。

QQ 回の操作後において、各頂点がどの色で塗られているか調べてください。

制約

  • 1≦N,M,Q≦1051 ≦ N,M,Q ≦ 10^5
  • 1≦ai,bi,vi≦N1 ≦ a_i,b_i,v_i ≦ N
  • ai≠bia_i ≠ b_i
  • 0≦di≦100 ≦ d_i ≦ 10
  • 1≦ci≦1051 ≦ c_i ≦10^5
  • di,cid_i, c_i いずれも整数
  • 与えられるグラフに自己ループや多重辺は存在しない

部分点

  • 1≦N,M,Q≦2,0001 ≦ N,M,Q ≦ 2{,}000 を満たすデータセットに正解した場合は、部分点として 200200 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

NN MM
a1a_1 b1b_1
::
aMa_{M} bMb_{M}
QQ
v1v_1 d1d_1 c1c_1
::
vQv_{Q} dQd_{Q} cQc_{Q}

出力

答えを NN 行に出力せよ。 ii 行目では QQ 回の操作後における頂点 ii の色を出力せよ。

入力例 1Copy

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

出力例 1Copy

Copy
2
2
2
2
2
1
0

はじめ、各頂点は色 00 で塗られています。 11 回目の操作により、頂点 5,65,6 が色 11 で塗られます。 22 回目の操作により、頂点 1,2,3,4,51,2,3,4,5 が色 22 で塗られます。

2ab7e180230b159d42d35ea7e555b3b0.png

入力例 2Copy

Copy
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

出力例 2Copy

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

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

Score : 700700 points

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of NN vertices numbered 11 through NN, and MM edges. Initially, all the vertices are painted in color 00. The ii-th edge bidirectionally connects two vertices aia_i and bib_i. The length of every edge is 11.

Squid performed QQ operations on this graph. In the ii-th operation, he repaints all the vertices within a distance of did_i from vertex viv_i, in color cic_i.

Find the color of each vertex after the QQ operations.

Constraints

  • 1≤N,M,Q≤1051 ≤ N,M,Q ≤ 10^5
  • 1≤ai,bi,vi≤N1 ≤ a_i,b_i,v_i ≤ N
  • ai≠bia_i ≠ b_i
  • 0≤di≤100 ≤ d_i ≤ 10
  • 1≤ci≤1051 ≤ c_i ≤10^5
  • did_i and cic_i are all integers.
  • There are no self-loops or multiple edges in the given graph.

Partial Score

  • 200200 points will be awarded for passing the testset satisfying 1≤N,M,Q≤2,0001 ≤ N,M,Q ≤ 2{,}000.

Input

Input is given from Standard Input in the following format:

NN MM
a1a_1 b1b_1
::
aMa_{M} bMb_{M}
QQ
v1v_1 d1d_1 c1c_1
::
vQv_{Q} dQd_{Q} cQc_{Q}

Output

Print the answer in NN lines. In the ii-th line, print the color of vertex ii after the QQ operations.

Sample Input 1Copy

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

Sample Output 1Copy

Copy
2
2
2
2
2
1
0

Initially, each vertex is painted in color 00. In the first operation, vertices 55 and 66 are repainted in color 11. In the second operation, vertices 11, 22, 33, 44 and 55 are repainted in color 22.

2ab7e180230b159d42d35ea7e555b3b0.png

Sample Input 2Copy

Copy
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

Sample Output 2Copy

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

The given graph may not be connected.

2025-05-15 (Thu)
09:39:19 +00:00