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: Time Limit Exceeded

Solution code:
def makelist2(n,m):
    return[[float("inf") for k in range(m)]for i in range(n)]

n, m = map(int,input().split())
dist = makelist2(n,n)
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    dist[a][b] = 1
    dist[b][a] = 1
for i in range(n):
    dist[i][i] = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

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


for q in range(Q):
    for i in range(n):
        if dist[vbc[q][0]-1][i] <= vbc[q][1] and ans[i] == 0:
            ans[i] = vbc[q][2]

for p in ans:
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

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: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

n, m  = map(int, input().split())
g     = {}
maxD  = np.array([-1 for i in range(n)])
color = np.array([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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.pop()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                if dis-1 > maxD[v]:
                    curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

ans = ''
for x in color:
    ans += str(x)+'\n'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

n, m  = map(int, input().split())
g     = {}
maxD  = np.array([-1 for i in range(n)])
color = np.array([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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                if dis-1 > maxD[v]:
                    curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

ans = ''
for x in color:
    ans += str(x)+'\n'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

n, m  = map(int, input().split())
g     = {}
maxD  = np.array([-1 for i in range(n)])
color = np.array([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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

ans = ''
for x in color:
    ans += str(x)+'\n'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m  = map(int, input().split())
g     = {}
maxD  = [-1 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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

ans = ''
for x in color:
    ans += str(x)+'\n'
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m  = map(int, input().split())
g     = {}
maxD  = [-1 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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if used[node][dis] == True:
            continue
            
        if dis < 0:
            continue
            
        used[node][dis] = True
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)

Submission status: Time Limit Exceeded

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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.pop(0)
    
        if used[node][dis] == True:
            continue
            
        if dis < 0:
            continue
            
        used[node][dis] = True
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = []
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)

Submission status: Time Limit Exceeded

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(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.pop(0)
    
        if used[node][dis] == True:
            continue
        
        used[node][dis] = True
    
        if color[node] == 0:
            color[node] = col

        if dis > 0:
            if node in g:
                for v in g[node]:
                    curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = []
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)

Submission status: Time Limit Exceeded

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 used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g and dist > 0:
        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: Time Limit Exceeded

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(node, dis, col):
    if used[node][dis] == True:
        return
        
    used[node][dis] == True    
    
    if color[node] == 0:
        color[node] = col
        
        
    if node in g and dis > 0:
        for v in g[node]:
            bfs(v, dis-1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
N, M = map(int, input().split())

#　グラフの初期化
a = []
for k in range(N):
  a.append(set())
  A = np.array(a)

# グラフの作成
for k in range(M):
  a, b = map(int, input().split())
  A[a-1].update([b-1])
  A[b-1].update([a-1])

#　色塗り
Q = int(input())
colors = np.zeros(N)

for k in range(Q):
  v, d, c = map(int, input().split())
  v -= 1
  colors[v] = c
  v = [v]
  for length in range(d):
    s = set()
    for m in A[v]:
      s.update(m)
    v = list(s)
    colors[v] = c

#　結果
for k in range(N):
  print(int(colors[k]))

Submission status: Time Limit Exceeded

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]*N
def f(s,d,v):
    H=deque()
    H.append((0,s))
    color[s]=v
    visit=[False]*N
    visit[s]=True
    while H:
        dis,pt=H.popleft()
        if dis>=d:
            continue
        for x in table[pt]:
            if not visit[x]:
                color[x]=v
                visit[x]=True
                H.append((dis+1,x))
    return
for v,d,c in X:
    v=v-1
    f(v,d,c)
    #print(color)
for i in color:
    print(i)

Submission status: Time Limit Exceeded

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

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

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

for co in color:
    print(co)

Submission status: Time Limit Exceeded

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())
v = []
d = []
c = []

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

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

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

for co in color:
    print(co)

Submission status: Time Limit Exceeded

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())
v = []
d = []
c = []

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

color = [0] * n

def dfs(node, dist, dist_max, col):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        dfs(next_node, dist+1, dist_max, col)

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

for co in color:
    print(co)

Submission status: Time Limit Exceeded

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())
v = []
d = []
c = []
for _ in range(q):
    V, D, C = map(int, input().split())
    v.append(V-1)
    d.append(D)
    c.append(C)
v = v[::-1]
d = d[::-1]
c = c[::-1]

color = [0] * n

def dfs(node, dist, dist_max, col):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        dfs(next_node, dist+1, dist_max, col)

for i in range(q):
    dfs(v[i], 0, d[i], c[i])

for co in color:
    print(co)

Submission status: Time Limit Exceeded

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 = [0] * 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: Time Limit Exceeded

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

col = [0 for _ in range(n)]
def bfs(bs, d, c):
  if d < 0:
    return
  nset = set()
  for b in bs:
    nset = nset.union(g[b])
    col[b] = c
  return bfs(nset, d-1, c)
  
q = int(input())
for _ in range(q):
  v, d, c = map(int, input().split())
  col[v-1] = c
  bfs(set(g[v-1]), d-1, c)
for c in col:
  print(c)

Submission status: Time Limit Exceeded

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 = [0] * N

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

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

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

Submission status: Time Limit Exceeded

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],d[i],c[i]=map(int,input().split());v[i]-=1
q=deque()
ans=[0 for i in range(N)]
for t in range(Q)[::-1]:
    reached=[0 for i in range(N)]
    q.append((v[t],d[t]))
    while(q):
        x,l=q.popleft()
        reached[x]=1
        if ans[x]==0:
            ans[x]=c[t]
        if l==0:
            continue
        for y in G[x]:
            if reached[y]==0:
                q.append((y,l-1))
for line in ans:
    print(line)

Submission status: Time Limit Exceeded

Solution code:
import queue
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=queue.Queue()
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.put((v[t],d[t]))
    while(not(q.empty())):
        vv,dd=q.get()
        if color[vv]==0:
            color[vv]=c[t]
        dd-=1
        for y in G[vv]:
            if dp[y]>=dd:
                continue
            dp[y]=dd
            q.put((y,dd))
for line in color:
    print(line)

Submission status: Time Limit Exceeded

Solution code:
import queue
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],d[i],c[i]=map(int,input().split());v[i]-=1
q=queue.Queue()
ans=[0 for i in range(N)]
for t in range(Q)[::-1]:
    reached=[0 for i in range(N)]
    q.put((v[t],d[t]))
    while(not(q.empty())):
        x,l=q.get()
        reached[x]=1
        if ans[x]==0:
            ans[x]=c[t]
        if l==0:
            continue
        for y in G[x]:
            if reached[y]==0:
                q.put((y,l-1))
for line in ans:
    print(line)

Submission status: Time Limit Exceeded

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())
Colors=[0]*N
dp=[[False]*11 for i in range(N)]
def BFS(v,d,c):
  global dp
  for i in range(d+1):
    dp[v][i]=True
  stack=deque([(v,d)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m<0:
      break
    if Colors[n]==0:
      Colors[n]=c
    for u in G[n]:
      if not dp[u][m]:
        stack.append((u,m-1))
        for i in range(m):
          dp[u][i]=True
q=[list(map(int,input().split())) for i in range(Q)]
for i in q[::-1]:
  v,d,c=i
  BFS(v-1,d,c)
for c in Colors:
  print(c)

Submission status: Time Limit Exceeded

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())
Colors=[0]*N

def BFS(v,d,c):
  visited=[False]*N
  visited[v]==True
  stack=deque([(v,0)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m>d:
      break
    Colors[n]=c
    for s in G[n]:
      if not visited[s]:
        stack.append((s,m+1))
        visited[s]=True
        
for i in range(Q):
  v,d,c=map(int,input().split())
  BFS(v-1,d,c)
for c in Colors:
  print(c)

Submission status: Time Limit Exceeded

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)
for ch in v:
  dfs(ch[0],ch[1],ch[2])
for i in range(1,n+1):
  print(iro[i])

Submission status: Time Limit Exceeded

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

"""
agc012 C
"""

from collections import defaultdict

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

graph = defaultdict(list)
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: Time Limit Exceeded

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]*11 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 idx < dp[v][d]:
        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 for e in dp[i])] for i in range(N)), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def main():
	n,m=map(int,input().split())
	arr=[0]*n
	link={}
	for i in range(1,n+1):
		link[str(i)]=[]
	'''create a dictionary storing the vertices each vertex is connected to'''
	for i in range(m):
		a,b=map(int,input().split())
		link[str(b)].append(a)
		link[str(a)].append(b)
	for q in range(int(input())):
		v,d,c=map(int,input().split())
		arr1=dist(link,v,[],d)
		for i in arr1:
			arr[i-1]=c
	for i in arr:
		print(i)
 
 
def dist(link, start, arr, d):
	'''move along edges to store all vertices within distance d'''
	if d == 0:
		arr.append(start)
	else:
	    arr.append(start)
	    for edge in link[str(start)]:
	        dist(link, edge, arr, d-1)
 
	return arr
 
main()

Submission status: Time Limit Exceeded

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

    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: Time Limit Exceeded

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

    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = defaultdict(list)
    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: Time Limit Exceeded

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


def func(v, d, c, color, depth, graph):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return

    for u in graph[v]:
        func(u, d - 1, c, color, depth, graph)

def main():
    N, M = map(int, input().split())
    graph = defaultdict(list)
    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 v, d, c in q[::-1]:
        func(v, d, c, color, depth, graph)
    print(*color, sep="\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def bfs_sp(root, edges, n):
	cons = 10 * n + 1
	dis = [cons] * n
	# distance to itself is zero
	dis[root - 1] = 0
	queue = []
	queue.append(root)
	while len(queue)>0:
		# here the 0 in pop() is very important
		# which makes list as a queue
		end = queue.pop(0)
		for child in edges[end]:
			if dis[child-1]==cons:
				dis[child-1]=dis[end-1]+1
				queue.append(child)
	return dis


def splatter_painting():
	n, m = map(int, raw_input().split(" "))
	edges = defaultdict(list)
	for i in range(m):
		a = map(int, raw_input().split(" "))
		edges[a[0]].append(a[1])
		edges[a[1]].append(a[0])
	k = int(raw_input())
	q = []
	for i in range(k):
		q.append(map(int, raw_input().split(" ")))

	dic_root_distances = {}
	for i in range(n):
		dic_root_distances[i+1] = bfs_sp(i+1, edges, n)
	# print dic_root_distances

	ans = [0]*n
	for _q in reversed(q):
		dis = dic_root_distances[_q[0]]
		for i in range(n):
			if dis[i]<=_q[1] and ans[i]==0:
				ans[i] = _q[2]
		if 0 not in ans:
			break
	for c in ans:
		print c


if __name__ == "__main__":
	splatter_painting()