Problem:


Score : 700 points

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of N vertices numbered 1 through N, and M edges.
Initially, all the vertices are painted in color 0. The i-th edge bidirectionally connects two vertices a_i and b_i. The length of every edge is 1.

Squid performed Q operations on this graph. In the i-th operation, he repaints all the vertices within a distance of d_i from vertex v_i, in color c_i.

Find the color of each vertex after the Q operations.

Constraints

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 and c_i are all integers.

There are no self-loops or multiple edges in the given graph.

Partial Score

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

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
:
a_{M} b_{M}
Q
v_1 d_1 c_1
:
v_{Q} d_{Q} c_{Q}

Output

Print the answer in N lines.
In the i-th line, print the color of vertex i after the Q operations.

Sample Input 1

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 1

2
2
2
2
2
1
0

Initially, each vertex is painted in color 0.
In the first operation, vertices 5 and 6 are repainted in color 1.
In the second operation, vertices 1, 2, 3, 4 and 5 are repainted in color 2.

Sample Input 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

Sample Output 2

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

The given graph may not be connected.



Sample input:
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:
2
2
2
2
2
1
0

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    Q = int(input())
    queries = [None] * Q
    dp = [[-1] * 11 for _ in range(N)]
    for i in range(Q):
        v, d, c = map(int, input().split())
        queries[i] = (v, d, c)
    for i in range(Q)[::-1]:
        v, d, c = queries[i]
        if dp[v-1][d] == -1:
            dp[v-1][d] = i
    for j in range(10)[::-1]:
        for i in range(N):
            dp[i][j] = max(dp[i][j], dp[i][j+1])
            for nxt in adj[i]:
                dp[i][j] = max(dp[i][j], dp[nxt][j+1])
    for i in range(N):
        x = dp[i][0]
        if x == -1:
            print(0)
        else:
            print(queries[x][2])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(i,v,d,c):
  if dp[v][d]==-1:
    dp[v][d]=i
    if d>0:
      dfs(i,v,d-1,c)
      for u in g[v]:
        dfs(i,u,d-1,c)
  
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[]
for i in range(q):
  v,d,c=map(int,input().split())
  arr.append((i,v,d,c))
dp=[[-1]*11 for _ in range(n+1)]
for i,v,d,c in arr[::-1]:
  dfs(i,v,d,c)
ans=[]
for i in range(1,n+1):
  if dp[i][0]==-1:
    ans.append(0)
  else:
    ans.append(arr[dp[i][0]][3])
for i in range(n):
  print(ans[i])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    def dfs(d,x,c):
        if d <= dp[x]:
            return
        dp[x] = d
        if not f[x]:
            f[x] = c
        for y in v[x]:
            dfs(d-1,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    dp = defaultdict(lambda : -1)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(d,x,c)
    for i in f:
        print(i)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adjL[A-1].append(B-1)
        adjL[B-1].append(A-1)
    Q = int(input())
    querys = []
    for iQ in range(Q):
        v, d, c = map(int, input().split())
        querys.append((iQ, v-1, d, c))

    dp = [[-1]*(11) for _ in range(N)]

    def rec(vNow, d, c, iQ):
        if dp[vNow][d] == -1:
            dp[vNow][d] = iQ
            if d > 0:
                rec(vNow, d-1, c, iQ)
                for v2 in adjL[vNow]:
                    rec(v2, d-1, c, iQ)

    for iQ, v, d, c in reversed(querys):
        rec(v, d, c, iQ)

    anss = [0] * N
    for v in range(N):
        if dp[v][0] != -1:
            anss[v] = querys[dp[v][0]][3]

    print('\n'.join(map(str, anss)))

solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
nei =[[i] for i in range(n)]

for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    nei[a].append(b)
    nei[b].append(a)

color = [0 for i in range(n)]
depth = [-1 for i in range(n)]

def paint(v,d,c,pre):
    if d <= depth[v]:
        return
    depth[v] = d
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for next in nei[v]:
        if next == pre:
            continue
        paint(next,d-1,c,v)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2],-1)
    #print(color)


for co in color:
    print(co)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
adj = [[i] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])

Submission status: Accepted

Solution code:
n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
Q=int(input())
X=[[int(i) for i in input().split()] for i in range(Q)]
color=[0]*Q
dp=[[-1]*N for i in range(11)]
for i in range(Q-1,-1,-1):
    v, d, c=X[i]
    v=v-1
    color[i]=c
    dp[d][v]=max(dp[d][v],i)

for d in range(10,0,-1):
    for x in range(N):
        for y in table[x]:
            dp[d-1][y]=max(dp[d][x],dp[d-1][y])
for i in range(N):
    s=-1
    for d in range(11):
        s=max(s,dp[d][i])
    if s==-1:
        print(0)
    else:
        print(color[s])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
n,m=map(int, input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int, input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
q=int(input())
Q=[list(map(int,input().split())) for _ in range(q)][::-1]
Visited=[-1]*n
Color=[0]*n
que=deque()
for v,d,c in Q:
    v-=1
    if Visited[v]>=d:
        continue
    Visited[v]=d
    que.append((v,d))
    while que:
        v,d=que.popleft()
        if not Color[v]:
            Color[v]=c
        d-=1
        for i in Edges[v]:
            if Visited[i]>=d:
                continue
            Visited[i]=d
            que.append((i,d))
print(*Color,sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n
depth = [-1] * n

def dfs(node, dist, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if color[node] == 0:
        color[node] = col
    if dist == 0:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist-1, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, d, c, -1)

for co in color:
    print(co)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

cs = [0] * N
depth = [-1] * N

def rec(v,d,c,pv):
    if d <= depth[v]: return
    depth[v] = d
    if cs[v]==0:
        cs[v] = c
    if d==0: return
    for to in es[v]:
        if to==pv: continue
        rec(to,d-1,c,v)

for v,d,c in qs[::-1]:
    rec(v-1,d,c,-1)

print(*cs, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
Q=int(input())
v=[0 for i in range(Q)]
d=[0 for i in range(Q)]
c=[0 for i in range(Q)]
for i in range(Q):
    v[-i-1],d[-i-1],c[-i-1]=map(int,input().split());v[-i-1]-=1
q=deque()
color=[0 for i in range(N)]
dp=[-1 for i in range(N)]
for t in range(Q):
    if dp[v[t]]>=d[t]:
        continue
    dp[v[t]]=d[t]
    q.append((v[t],d[t]))
    while(q):
        vv,dd=q.popleft()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.append((y,dd))
for line in color:
    print(line)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=map(int,input().split())
  dp[v-1][d]=i
  C.append(c)
for d in range(1,11)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = [list(map(int,input().split())) for i in range(m)]
q = int(input())
v = [list(map(int,input().split())) for i in range(q)]
v = v[::-1]
l = [[] for i in range(n+1)]
for pi in p:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
mita = [-1]*(n+1)
tugi = [set() for i in range(n+1)]
iro = [0] *(n+1)
def dfs(x,y,z):
  if iro[x] == 0:
    iro[x] = z
  if mita[x] >=y:
    return
  for i in l[x]:
    if y-1>=0:
      dfs(i,y-1,z)
  mita[x] = y
for ch in v:
  dfs(ch[0],ch[1],ch[2])
for i in range(1,n+1):
  print(iro[i])

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        for i in range(d+1):
            if dp[v][i] == -1:
                dp[v][i] = t
        if d > 0:
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x,y,dp = [[] for i in range(n)],[],[[0,-1] for i in range(n)]
for i in range(m):
	a,b = (int(i)-1 for i in input().split())
	x[a].append(b)
	x[b].append(a)
q = int(input())
for i in range(q):
	v,d,c = (int(i) for i in input().split())
	y.append((v-1,d,c))
def f(v,d,c):
	z,z2 = dp[v]
	if d>z2:
		if z: dp[v] = z,d
		else: dp[v] = c,d
		if d:
			for i in x[v]: f(i,d-1,c)
for i,j,k in y[::-1]: f(i,j,k)
for i in dp: print(i[0])

Submission status: Accepted

Solution code:
n, m=map(int, raw_input().split())
adj=[[] for i in range(n+1)]
for i in range(m):
	a, b=map(int, raw_input().split())
	adj[a].append(b)
	adj[b].append(a)
q=input()
bucket=[[] for i in range(11)]
for i in range(q):
	v, d, c=map(int, raw_input().split())
	bucket[d].append((v, c, i))
result=[0]*(n+1)
time=[-1]*(n+1)
for i in range(10, -1, -1):
	new_result=result[:]
	new_time=time[:]
	for cur in range(n+1):
		for to in adj[cur]:
			if new_time[to]<time[cur]:
				new_time[to]=time[cur]
				new_result[to]=result[cur]
	result=new_result
	time=new_time
	for cur, color, t in bucket[i]:
		if time[cur]<t:
			time[cur]=t
			result[cur]=color
for i in range(1, n+1):
	print result[i]
print

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

Q = int(input())
C = []
for i in range(Q):
    v, d, c = map(int, input().split())
    C.append((v - 1, d, c))
dp = [[0, -1] for i in range(N)]


def paint(v, d, c):
    x, y = dp[v]
    if d <= y:
        return
    if x == 0:
        dp[v] = c, d
    else:
        dp[v] = x, d

    if d == 0:
        return
    for i in G[v]:
        paint(i, d - 1, c)


for v, d, c in reversed(C):
    paint(v, d, c)

for k in dp:
    print(k[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"
MAX = 100001

dp = [0 for i in range(MAX)]
color = [0 for i in range(MAX)]
e = [[] for i in range(MAX)]

def paint(v, d, c):
    if not color[v]:
        color[v] = c
    if dp[v] >= d or d == 0:
        return
    dp[v] = d
    for u in e[v]:
        paint(u, d - 1, c)

def main():
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        e[a].append(b)
        e[b].append(a)
    q = int(input())
    vq, dq, cq = [], [], []
    for i in range(q):
        v, d, c = map(int, input().split())
        vq.append(v)
        dq.append(d)
        cq.append(c)
    assert len(vq) == len(dq) == len(cq) == q

    for i in reversed(range(q)):
        paint(vq[i], dq[i], cq[i])
    for i in range(n):
        print(color[i + 1])


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(101010)

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    es[a].append(b)
    es[b].append(a)
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

mem = [[0,-1] for i in range(N)] # [color,depth] for v
def paint(v,d,c):
    mc,md = mem[v]
    if d <= md: return
    mem[v] = [mc if mc else c, d]
    if d == 0: return
    for to in es[v]:
        paint(to,d-1,c)

for v,d,c in reversed(qs):
    paint(v-1,d,c)
for c,d in mem:
    print(c)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

Adj = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    Adj[a].append(b)
    Adj[b].append(a)

Q = int(input())
v, d, c = [0]*Q, [0]*Q, [0]*Q
for i in range(Q):
    v[i], d[i], c[i] = map(int, input().split())

memo = [[0] * (10+1) for i in range(N+1)]


def paint(v, d, i):
    # すでに塗られていたらもう先は見ない
    if memo[v][d]:
        return

    # 塗られていなければ何番目の操作で色が塗られたかを覚えておく
    memo[v][d] = i

    # 距離-1は存在しないので終了ストッパー
    if d == 0:
        return

    # 何番目の操作で色が塗られたかを0まで伝播
    paint(v, d-1, i)

    # 今見ているところの隣接頂点について同じことをやりにいく
    # ただし離れるにつれて届く範囲は1ずつ減っていく
    for u in Adj[v]:
        paint(u, d-1, i)


# 逆順にクエリを処理
for q in range(Q-1, -1, -1):
    paint(v[q], d[q], q+1)


for i in range(1, N+1):
    # 操作が加わった形跡があれば、それが何番目の操作であるか確認し、その操作に該当する色を取りに行く
    if memo[i][0] != 0:
        print(c[memo[i][0]-1])
    else:
        print(0)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dp = [{-1: -1} for i in range(N)]
mark = {}
Q = int(input())
col = [0]*(Q+1)
col[-1] = 0
C = []
for i in range(Q):
    v, d, c = map(int, input().split())
    col[i] = c
    C.append((v-1, d))

def dfs(v, d, idx):
    if d <= max(dp[v]):
        return
    dp[v][d] = idx
    if d:
        for w in G[v]:
            dfs(w, d-1, idx)

for i in range(Q-1, -1, -1):
    v, d = C[i]
    dfs(v, d, i)
print(*(col[max(e.values())] for e in dp), sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


color, depth, graph = [], [], {}
def func(v, d, c):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return
    depth[v] = d
    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    Q = int(input())
    q = []
    for _ in range(Q):
        v, d, c = map(int, input().split())
        q.append((v - 1, d, c))

    color = [0] * N
    depth = [0] * N
    for i in range(Q - 1, -1, -1):
        func(q[i][0], q[i][1], q[i][2])
    print(*color, sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def dfs(v, d, c, e):
    if (dp[v][d] != 0):
        return dp[v][d]

    if (d == 0):
        dp[v][d] = c
        return dp[v][d]

    for u in e[v]:
        dp[u][d-1] = dfs(u, d-1, c, e)

    dp[v][d] = dfs(v, d-1, c, e)
    return dp[v][d]

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

dp = [[0]*11 for i in range(10**5+1)]
e = [[] for i in range(10**5+1)]

N, M = na()
for i in range(M):
    a, b = na()
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
Q = ni()
qv = [[0,0,0] for i in range(Q)]
for i in range(Q):
    v, d, c = na()
    v -= 1
    qv[Q-1-i][0] = v
    qv[Q-1-i][1] = d
    qv[Q-1-i][2] = c

for i in range(Q):
    dfs(qv[i][0],qv[i][1],qv[i][2],e)

for i in range(N):
    print (dp[i][0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n, m = map(int,input().split())
node = [[] for i in range(n + 1)]

for i in range(m):
    a, b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)

q = int(input())
vdc = [[0] * 3 for i in range(q)]
for i in range(q):
    vdc[i][0], vdc[i][1], vdc[i][2] = map(int, input().split())
vdc = vdc[::-1]

ans = [0] * (n + 1)
visited = [[0] * 11 for i in range(n + 1)]
def f(v, d, c):
    if d < 0:
        return
    if visited[v][d]:
        return

    visited[v][d] = 1
    if ans[v] == 0:
        ans[v] = c
        #print("ans", v, ans[v])

    for x in node[v]: #頂点xは頂点vに隣接する頂点
        f(x, d - 1, c)

for v, d, c in vdc:
    f(v, d, c)

for i in range(n):
    print(ans[i + 1])

Submission status: Accepted

Solution code:
from queue import deque


def paint(s, d, c):
    queue = deque([(d, s)])
    while queue:
        remains, v = queue.popleft()
        if painted[v] >= remains:
            continue
        if colors[v] == 0:
            colors[v] = c
        painted[v] = remains
        if remains:
            queue.extend((remains - 1, u) for u in links[v])


n, m = map(int, input().split())
links = [None] + [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    links[a].add(b)
    links[b].add(a)

q = int(input())
queries = [map(int, input().split()) for _ in range(q)]
colors = [0] * (n + 1)
painted = [-1] * (n + 1)
while queries:
    paint(*queries.pop())

for c in colors[1:]:
    print(c)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict

G = defaultdict(list)
N, M = map(int, input().split())
color = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())

data = [list(map(int, input().split())) for _ in range(Q)]
data.reverse()
color_d = [-1] * (N + 1)

for v, d, c in data:
    if color_d[v] >= d:
        pass
    # BFS
    deq = deque([v])
    if color[v] == 0:
        color[v] = c
    color_d[v] = d
    while len(deq) > 0:
        s = deq.popleft()
        for t in G[s]:
            if color_d[t] >= color_d[s] - 1:
                pass
            else:
                color_d[t] = color_d[s] - 1
                if color[t] == 0:
                    color[t] = c
                if color_d[t] > 0:
                    deq.append(t)

for n in range(1, N + 1):
    print(color[n])

Submission status: Accepted

Solution code:
from collections import deque

N, M = map( int, input().split() )

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = map( int, input().split() )
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( input() )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = map( int, input().split() )
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = deque()
  vis[ V[ qi ] ] = D[ qi ]
  que.append( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while len( que ):
    d, u = que.popleft()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.append( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

for i in range( N ):
  print( col[ i ] )

Submission status: Accepted

Solution code:
from collections import defaultdict

def paint(v, d, c):
    if color[v] == 0:
        color[v] = c
    if dp[v] >= d or d == 0:
        return
    dp[v] = d
    for nb in graph[v]:
        paint(nb, d-1, c)

N, M = map(int, input().split())
dp = [0] * N
color = [0] * N
graph = defaultdict(set)
for _ in range(M):
    i, j = map(int, input().split())
    graph[i-1].add(j-1)
    graph[j-1].add(i-1)
Q = int(input())
vdcs = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    vdcs.append((v-1, d, c))
vdcs.reverse()

for v, d, c in vdcs:
    paint(v, d, c)

for c in color:
    print(c)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
edges += [[i, i] for i in range(n)]

q = int(input())
color = [0] * (q + 1)
dp = [[0 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, color[i + 1] = map(int, input().split())
    dp[d][v - 1] = i + 1
 
for i in reversed(range(1, 11)):
    for u, v in edges:
        dp[i - 1][u] = max(dp[i - 1][u], dp[i][v])
        dp[i - 1][v] = max(dp[i - 1][v], dp[i][u])
 
print(*[color[dp[0][i]] for i in range(n)], sep = '\n')

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
edges = [map(lambda x: int(x) - 1, raw_input().split()) for _ in xrange(m)]
 
q = input()
vv = [None] * q
dd = [None] * q
cc = [None] * q
dp = [[-1 for j in xrange(11)] for i in xrange(n)]
for i in xrange(q):
    vv[i], dd[i], cc[i] = map(int, raw_input().split())
    dp[vv[i] - 1][dd[i]] = i
 
for i in reversed(range(1, 11)):
    for j in xrange(n):
        dp[j][i - 1] = max(dp[j][i - 1], dp[j][i])
    for u, v in edges:
        dp[u][i - 1] = max(dp[u][i - 1], dp[v][i])
        dp[v][i - 1] = max(dp[v][i - 1], dp[u][i])
 
for i in xrange(n):
    if dp[i][0] == -1:
        print('0')
    else:
        print(cc[dp[i][0]])

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())

g = [[i] for i in xrange(n)]

for _ in xrange(m):
    u, v = map(lambda x: int(x) - 1, raw_input().split())
    g[u].append(v)
    g[v].append(u)

q = input()
c = [None] * q
dp = [[-1 for j in range(n)] for i in xrange(11)]
for i in xrange(q):
    v, d, c[i] = map(int, raw_input().split())
    dp[d][v - 1] = i
 
for i in reversed(range(1, 11)):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in xrange(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print(c[dp[0][i]])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

g = [[i] for i in range(n)]

for _ in range(m):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)

q = int(input())
c = [None] * q
dp = [[-1 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, c[i] = map(int, input().split())
    dp[d][v - 1] = i
 
for i in reversed(range(1, 11)):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in range(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print(c[dp[0][i]])

Submission status: Accepted

Solution code:
def recClr(v,d,c):
#    print "recClr",v,d,c
    if visited[v-1] >= d:
        return
    else:
        visited[v-1]=d
    if clr[v-1]==0:
        clr[v-1]=c
    if d>0:
        if v in ab:
            for b in ab[v]:
                recClr(b,d-1,c)


N,M=map(int,raw_input().split())
ab={}
for i in xrange(M):
    a,b=map(int,raw_input().split())
    if a in ab:
        ab[a].append(b)
    else:
        ab[a]=[b]
    if b in ab:
        ab[b].append(a)
    else:
        ab[b]=[a]
#print ab


clr=[0]*N
visited=[-1]*N

Q=input()
op=[]
for i in xrange(Q):
    v,d,c=map(int,raw_input().split())
    op.append((v,d,c))
op.reverse()
for v,d,c in op:
    recClr(v,d,c)
#print clr   

for i in clr:
    print i

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e = []

for _ in range(1,m+1):
    a,b=map(int,input().split())
    e.append((a,b))

q = int(input())
cs = [0] * (q+1)
dp = [[0]*11 for _ in range(n+1)]
for i in range(1, q+1):
    v,d,c=map(int,input().split())
    cs[i] = c
    dp[v][d] = i

for d in range(9, -1, -1):
    for i in range(1,n+1):
        dp[i][d] = max(dp[i][d], dp[i][d+1])
    for a,b in e:
        dp[a][d] = max(dp[a][d], dp[b][d+1])
        dp[b][d] = max(dp[b][d], dp[a][d+1])

for i in range(1, n+1):
    print(cs[dp[i][0]])

Submission status: Accepted

Solution code:
import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    def rec(v, d, i):
        if dp[v][d]:
            return

        dp[v][d] = i

        if d == 0:
            return

        rec(v, d - 1, i)

        for u in Adj[v]:
            rec(u, d - 1, i)


    N, M = map(int, sys.stdin.readline().split())

    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        Adj[a].append(b)
        Adj[b].append(a)

    Q = int(sys.stdin.readline())

    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

    for i in range(Q - 1, -1, -1):
        v[i], d[i], c[i] = map(int, sys.stdin.readline().split())
        v[i] -= 1

    dp = [[0]*(10 + 1) for i in range(N)]

    for i in range(Q):
        rec(v[i], d[i], i + 1)

        # for i in range(N):
            # print(*dp[i])

        # print()

    for i in range(N):
        if dp[i][0] > 0:
            print(c[dp[i][0] - 1])
        else:
            print(0)

if __name__ == '__main__':
    solve()