Problem: 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.

Submission attempts (in order):
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)

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)

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)    



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]

while len(Q) > 0:
    node, dis, col = Q.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]:
                Q.append([v, dis-1, col])
    
for x in color:
    print(x)

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)    


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)

from collections import deque
import numpy as np
import sys

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 u, v in (map(int, sys.stdin.readline().split()) for _ in [0]*n):
    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 = [list(map(int, l.split())) for l in sys.stdin][::-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-1, dis, col])
    bfs(curQ)

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


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)

Verdicts: Runtime Error

Time Limit Exceeded

Time Limit Exceeded

Wrong Answer

Time Limit Exceeded

Time Limit Exceeded

Runtime Error

Accepted