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: Runtime Error

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]
    color = query(mat, v, d, c, color)

Submission status: Runtime Error

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]
    color = query(mat, v, d, c, color)

for i in range(n):
    print(int(color[0,i]))

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]
    color = query(mat, v, d, c, color)

for i in range(n):
    print(int(color[0,i]))

Submission status: Runtime Error

Solution code:
import copy
temp=input().split()
N=int(temp[0])
M=int(temp[1])

ab=[[int(j)-1 for j in input().split()] for i in range(M)]
Q=int(input())
vdc=[[int(j)-1 for j in input().split()] for i in range(Q)]

#color=[-1 for i in range(N)]
chain=[[] for i in range(N)]
for i in range(M):
	chain[ab[i][0]]+=[ab[i][1]]
	chain[ab[i][1]]+=[ab[i][0]]
for i in range(N):
	chain[i]+=[i]

INF=-1
dp=[INF for i in range(N)]

for i in range(Q):
	dp[vdc[i][0]][vdc[i][1]+1]=i
#print(chain)
#print(vdc)
#print(dp)
for i in range(9,-1,-1):
	nextDp=[INF for i in range(N)]
	for j in range(N):
		tempMax=INF
		for k in chain[j]:
			if tempMax<dp[k]:
				tempMax=dp[k]
		if tempMax<dp[k]:
			tempMax=dp[k]
		dp[j]=tempMax
	dp=copy.deepcopy(nextDp)
#	for i in range(N)
	
#print(dp)
for i in range(N):
	if dp[i]==INF:
		print(0)
	else:
		print(vdc[dp[i]][2]+1)

Submission status: Runtime Error

Solution code:
vertices,edges = (int(n) for n in input().split(" "))
edge = [[n,n] for n in range(vertices)]
for e in range(edges):
    u,v = (int(n) - 1 for n in input().split(" "))
    edge.append([u,v])
color = [0 for n in range(vertices + 1)]
query = int(input())
dp = [[0 for n in range(11)] for m in range(vertices)]
for q in range(query):
    e,d,col = (int(n) for n in input().split(" "))
    dp[e-1][d] = q + 1
    color[q + 1] = col
for dep in range(10,0,-1):
    for u,v in edge:
        dp[u][dep - 1] = max(dp[u][dep - 1],dp[v][dep],dp[u][dep])
        dp[v][dep - 1] = max(dp[v][dep - 1],dp[u][dep],dp[v][dep])
for v in range(vertices):
    print(color[dp[v][0]])

Submission status: Runtime Error

Solution code:
vertices,edges = (int(n) for n in input().split(" "))
edge = []
for e in range(edges):
    u,v = (int(n) - 1 for n in input().split(" "))
    edge.append([u,v])
color = [0 for n in range(vertices)]
query = int(input())
dp = [[0 for n in range(11)] for m in range(vertices)]
for q in range(query):
    e,d,col = (int(n) for n in input().split(" "))
    dp[e-1][d] = q + 1
    color[q + 1] = col
for dep in range(10,0,-1):
    for u,v in edge:
        dp[u][dep - 1] = max(dp[u][dep - 1],dp[v][dep],dp[u][dep])
        dp[v][dep - 1] = max(dp[v][dep - 1],dp[u][dep],dp[v][dep])
for v in range(vertices):
    print(color[dp[v][0]])

Submission status: Runtime Error

Solution code:
def painting(N,A,v,d,c):
	if d < 0:
		return
	if A[v][d] == 0:
		A[v][d] = c
		for ni,n in enumerate(N[v]):
			if n == 1:
				painting(N,A,ni,d-1,c)
N,M = list(map(int,input().split()))
nodes = [[0]*N for i in range(N)]
dp = [[0]*10 for i in range(N)]
for m in range(M):
	a,b = map(int,input().split())
	nodes[a-1][b-1] = 1
	nodes[b-1][a-1] = 1
for i in range(N):
	nodes[i][i] = 1
Q = int(input())
paint = [list(map(int,input().split())) for q in range(Q)]
paint.reverse()
for q in paint:
	v,d,c = q
	v = v - 1
	painting(nodes,dp,v,d,c)
print("\n".join(list(map(str,[dp[i][0] for i in range(N)]))))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
nodes = [[False]* N for j in range(N)]
for m in range(M):
	a,b = map(int,input().split())
	nodes[a-1][b-1] = True
	nodes[b-1][a-1] = True
mat1 = np.matrix(nodes,dtype=bool)
mat2 = mat1.copy()
A = [mat1.tolist()]
for i in range(10):
	mat2 = mat2.dot(mat1)
	a = mat2.tolist()
	A.append(a)

white = [i for i in range(N)]
Colour = [0] * N
paint = []
Q = int(input())
for q in range(Q):
	line = list(map(int,input().split()))
	paint.append(line)
white2 = white[:]
paint.reverse()
for p in paint:
	v,d,c = p[0],p[1],p[2]
	if d == 0 and v - 1 in white:
		Colour[v - 1] = c
		white2.remove(v - 1)
		continue
	elif d == 0:
		continue
	else:
		for w in white:
			if d == 1:
				if not A[0][v - 1][w]:
					continue
				else:
					Colour[w] = c
					white2.remove(w)
			else:
				if A[d - 1][v - 1][w] or A[d - 2][v - 1][w]:
					Colour[w] = c
					white2.remove(w)
		if len(white2) == 0:
			break
	if v - 1 in white:
		Colour[v - 1] = c
		if v - 1 in white2:
			white2.remove(v - 1)
	white = white2[:]

for C in Colour:
	print(C)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = map(int,input().split())
nodes = [[False]* N for j in range(N)]
for m in range(M):
	a,b = map(int,input().split())
	nodes[a-1][b-1] = True
	nodes[b-1][a-1] = True
mat1 = np.matrix(nodes,dtype=bool)
mat2 = mat1.copy()
A = [mat1.tolist()]
for i in range(10):
	mat2 = mat2.dot(mat1)
	a = mat2.tolist()
	A.append(a)

white = [i for i in range(N)]
Colour = [0] * N
paint = []
Q = int(input())
for q in range(Q):
	line = list(map(int,input().split()))
	paint.append(line)
white2 = white[:]
paint.reverse()
for p in paint:
	v,d,c = p[0],p[1],p[2]
	if d == 0 and v - 1 in w:
		Colour[v - 1] = c
		white2.remove(v - 1)
		continue
	elif d == 0:
		continue
	else:
		for w in white:
			if d == 1:
				if not A[0][v - 1][w]:
					continue
				else:
					Colour[w] = c
					white2.remove(w)
			else:
				if A[d - 1][v - 1][w] or A[d - 2][v - 1][w]:
					Colour[w] = c
					white2.remove(w)
		if len(white2) == 0:
			break
	if v - 1 in white:
		Colour[v - 1] = c
		if v - 1 in white2:
			white2.remove(v - 1)
	white = white2[:]

for C in Colour:
	print(C)

Submission status: Runtime Error

Solution code:
q = int(input())
node_color = [0 for _ in range(n + 1)]
vdc = [list(map(int, input().split())) for _ in range(q)]

vdc = vdc[::-1]
painted = set()
visited = [[0] * 11 for _ in range(n + 1)]


def dfs(now, dist, color):
    if dist < 0:
        return
    if visited[now][dist]:
        return

    visited[now][dist] += 1
    if not node_color[now]:
        node_color[now] = color

    for x in node[now]:
        dfs(x, dist - 1, color)


for i in vdc:
    v, d, c = i
    dfs(v, d, c)

for m in range(n):
    print(node_color[m + 1])

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import linalg as LA
import math

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat

    if int(math.sqrt(n))**2 == n:
        return LA.matrix_power(f(mat, int(math.sqrt(n))), 2)

    return mat.dot(f(mat, n-1))



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

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    a.append(temp[0])
    b.append(temp[1])
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(N):
    for j in range(N):
        if distance[i][j] != -1:
            for k in range(N):
                if i != k:
                    if distance[j][k] != -1:
                        temp = distance[i][j] + distance[j][k]
                        if distance[i][k] == -1 or temp < distance[i][k]:
                            distance[i][k] = temp
                            distance[k][i] = temp
for i in range(N):
    distance[i][i] = 0

color = np.zeros(N)
for q in range(Q):
    for n in range(N):
        if distance[v[q] - 1][n] != -1:
            if distance[v[q] - 1][n] <= d[q]:
                color[n] = c[q]

for n in range(N):
    print(int(color[n]))

Submission status: Runtime Error

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

q=int(input())
v=[0 for i in range(m+1)]
d=[0 for i in range(m+1)]
c=[0 for i in range(m+1)]
for i in range(1,q+1): v[i],d[i],c[i]=map(int,input().split())

for i in range(1,q+1):
    for j in range(1,q+1):
        if abs(v[j]-v[i])<d[i]: c[j]=c[i]
    print(c[i])

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    a.append(temp[0])
    b.append(temp[1])
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(N):
    for j in range(i + 1, N):
        if distance[i][j] != -1:
            for k in range(N):
                if i != k:
                    if distance[j][k] != -1:
                        temp = distance[i][j] + distance[j][k]
                        if distance[i][k] == -1 or temp < distance[i][k]:
                            distance[i][k] = temp
                            distance[k][i] = temp
for i in range(N):
    distance[i][i] = 0

color = np.zeros(N)
for q in range(Q):
    for n in range(N):
        if distance[v[q] - 1][n] != -1:
            if distance[v[q] - 1][n] <= d[q]:
                color[n] = c[q]

for n in range(N):
    print(int(color[n]))

Submission status: Runtime Error

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

nodes = [collections.defaultdict(int) for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    nodes[a-1][b-1] = 1
    nodes[b-1][a-1] = 1


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

colors = [0 for i in range(N)]
sizes = [-1 for i in range(N)]
edges = [[] for i in range(N)]
for query in range(Q-1, -1, -1):
    v, d, c = shots[query]
    dq = collections.deque()
    dq.append((d, v))
    visited = [False for i in range(N)]
    while dq:
        size, idx = dq.popleft()
        if sizes[idx] >= size:
            continue
        else:
            sizes[idx] = size
        visited[idx] = True
        if colors[idx] == 0:
            colors[idx] = c
        for nv, nd in nodes[idx].items():
            if not visited[nv]:
                dq.append((size-nd, nv))
        
        len_next_nodes = len(nodes[idx])
        if len_next_nodes >= 150:
            continue
        next_nodes = nodes[idx].items()
        for nvi, ndi in nodes[idx].items():
            if nvi == idx:
                continue
            nodes[nvi].pop(idx)
            for nvj, ndj in nodes[idx].items():
                if nvj in nodes[nvi]:
                    nodes[nvi][nvj] = nodes[nvj][nvi] = min(nodes[nvi][nvj], nodes[idx][nvi] + nodes[idx][nvj])
                else:
                    nodes[nvi][nvj] = nodes[nvj][nvi] = nodes[idx][nvi] + nodes[idx][nvj]


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

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import linalg as LA

mat_dic = {}

def f(mat, n):
    if mat_dic.get(n, None) is not None:
        return mat_dic.get(n, None)

    if n == 1:
        return mat
    return mat.dot(f(mat, n-1))


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

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = f(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Submission status: Runtime Error

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

for i in range(N):
	if len(G[i][1]) == 1:
		continue
	for d in range(1,11):
		for j in G[i][d-1]:
			G[i][d] |= G[j][1]
			if len(G[i][d] == N):
				break

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

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

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp1, temp2 = map(int, raw_input().split())
    a.append(temp1)
    b.append(temp2)
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(N):
    for j in range(i + 1, N):
        if distance[i][j] != -1:
            for k in range(N):
                if j != k and distance[j][k] != -1:
                    temp = distance[i][j] + distance[j][k]
                    if distance[i][k] == -1 or temp < distance[i][k]:
                        distance[i][k] = temp
                        distance[k][i] = temp
for i in range(N):
    distance[i][i] = 0

color = np.zeros(N)
for q in range(Q):
    for n in range(N):
        if distance[v[q] - 1][n] != -1:
            if distance[v[q] - 1][n] <= d[q]:
                color[n] = c[q]

for n in range(N):
    print(int(color[n]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp1, temp2 = map(int, raw_input().split())
    a.append(temp1)
    b.append(temp2)
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(N):
    for j in range(N):
        if distance[i][j] != -1:
            for k in range(N):
                if distance[j][k] != -1:
                    temp = distance[i][j] + distance[j][k]
                    if distance[i][k] == -1 or temp < distance[i][k]:
                        distance[i][k] = temp
                        distance[k][i] = temp
for i in range(N):
    distance[i][i] = 0

color = np.zeros(N)
for q in range(Q):
    for n in range(N):
        if distance[v[q] - 1][n] != -1:
            if distance[v[q] - 1][n] <= d[q]:
                color[n] = c[q]

for n in range(N):
    print(int(color[n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import linalg as LA


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

mat = np.identity(N)
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1

Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = LA.matrix_power(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp1, temp2 = map(int, raw_input().split())
    a.append(temp1)
    b.append(temp2)
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(N):
    count = 0
    for j in range(N):
        if distance[i][j] != -1:
            for k in range(N):
                if distance[j][k] != -1:
                    temp = distance[i][j] + distance[j][k]
                    if distance[i][k] == -1 or temp < distance[i][k]:
                        distance[i][k] = temp
                        distance[k][i] = temp
for i in range(N):
    distance[i][i] = 0

color = np.zeros(N)
for q in range(Q):
    for n in range(N):
        if distance[v[q] - 1][n] != -1 and distance[v[q] - 1][n] <= d[q]:
            color[n] = c[q]

for n in range(N):
    print(int(color[n]))

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import linalg as LA


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

mat = np.zeros((N, N))
res = np.zeros(N)

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
    mat[a-1, a-1] = 1
    mat[b-1, b-1] = 1


Q = int(input())

for q in range(Q):
    v, d, c = tuple(map(int, input().split(' ')))
    x = LA.matrix_power(mat, d)
    res[x[v-1,:] > 0] = c


for i in range(N):
    print(int(res[i]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp1, temp2 = map(int, raw_input().split())
    a.append(temp1)
    b.append(temp2)
Q = int(raw_input())
v = []
d = []
c = []
for i in range(Q):
    temp = map(int, raw_input().split())
    v.append(temp[0])
    d.append(temp[1])
    c.append(temp[2])

distance = -np.ones(N * N).reshape((N, N))
for i in range(M):
    distance[a[i] - 1][b[i] - 1] = 1
    distance[b[i] - 1][a[i] - 1] = 1

for i in range(M):
    count = 0
    for j in range(M):
        if distance[i][j] != -1:
            for k in range(M):
                if distance[j][k] != -1:
                    temp = distance[i][j] + distance[j][k]
                    if distance[i][k] == -1 or temp < distance[i][k]:
                        distance[i][k] = temp
                        distance[k][i] = temp
for i in range(M):
    distance[i][i] = 0

color = np.zeros(M)
for q in range(Q):
    for m in range(M):
        if distance[v[q] - 1][m] != -1 and distance[v[q] - 1][m] <= d[q]:
            color[m] = c[q]

for m in range(M):
    print(int(color[m]))

Submission status: Runtime Error

Solution code:
# import heapq
from collections import deque

class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def bfs(graph, cur, color, dist):
    visited = set()
    q = deque([(0, cur)])
    while q:
        # d, c = heapq.heappop(q)
        d, c = q.popleft()
        if c in visited:
            continue
        graph[c].color = color
        visited.add(c)
        if d == dist:
            continue
        for n in graph[c].to:
            if n in visited:
                continue
            # heapq.heappush(q, (d+1, n))
            q.append((d+1, n))
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N+1)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a].to.append(b)
        graph[b].to.append(a)
    Q = int(input())
    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        bfs(graph, v, c, d)
    for i in range(1, N+1):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# import heapq
from collections import deque

class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def bfs(graph, cur, color, visited, dist):
    q = deque([(0, cur)])
    while q:
        # d, c = heapq.heappop(q)
        d, c = q.popleft()
        if visited[c]:
            continue
        graph[c].color = color
        visited[c] = True
        if d == dist:
            continue
        for n in graph[c].to:
            if visited[n]:
                continue
            # heapq.heappush(q, (d+1, n))
            q.append((d+1, n))
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N+1)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a].to.append(b)
        graph[b].to.append(a)
    Q = int(input())
    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        visited = [False] * (N + 1)
        bfs(graph, v, c, visited, d)
    for i in range(1, N+1):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import heapq

class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def bfs(graph, cur, color, visited, dist):
    q = [(0, cur)]
    while q:
        d, c = heapq.heappop(q)
        if visited[c]:
            continue
        graph[c].color = color
        visited[c] = True
        if d == dist:
            continue
        for n in graph[c].to:
            if visited[n]:
                continue
            heapq.heappush(q, (d+1, n))
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N+1)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a].to.append(b)
        graph[b].to.append(a)
    Q = int(input())
    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        visited = [False] * (N + 1)
        bfs(graph, v, c, visited, d)
    for i in range(1, N+1):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
N,M = list(map(int,input().split()))
AB = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M) ]
Q= int(input())

vdc = [ list(map(int,input().split())) for _ in range(Q)]
for vdc_elements in vdc:
    vdc_elements[0] = vdc_elements[0]-1
near_dict = defaultdict(set)

for a,b in AB:
        near_dict[a].add(b)
        near_dict[b].add(a)



def get_distance(a,b):
    used = set()
    q = deque()
    q.append((a,0))
    while q :
        #print(used)
        now,dist=q.pop()
        if now ==b:
            return dist
        for i in near_dict[now]:
           if i not in used:
                q.append((i,dist+1))
                used.add(i)

    return 10000000000

def get_color(target_i):
    for i in reversed(range(Q)):
        v,d,c = vdc[i]
        if get_distance(v,target_i) <= d:
            return c
    return 0

#print(get_distance(0,6))
#print(get_distance(1,6))
if N+M+Q > 7000:
    raise
for i in range(N):
    print(get_color(i))

Submission status: Runtime Error

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

import collections


def bfs(s, d, adj_matrix):
    visited = {s}
    dist = {s: 0}
    q = collections.deque()
    q.append(s)
    while q:
        t = q.popleft()
        if dist[t] >= d:
            break
        for u in adj_matrix[t]:
            if u not in visited:
                q.append(u)
                visited.add(u)
                dist[u] = dist[t] + 1
    return visited


def main():
    n, m = (int(x) for x in input().split())
    assert n <= 2000  # !
    adj_matrix = [set() for _ in range(n)]
    color = [0 for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_matrix[a].add(b)
        adj_matrix[b].add(a)
    qu = int(input())
    for _ in range(qu):
        v, d, c = (int(x) for x in input().split())
        v -= 1
        res = bfs(v, d, adj_matrix)
        for u in res:
            color[u] = c
    print(*color, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

G = dict()
N, M = map(int, input().split())
color = [0]*(N+1)
for n in range(1, N+1):
    G[n] = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())

for _ in range(Q):
    v, d, c = map(int, input().split())
    # BFS
    dist = dict()
    deq = deque([v])
    color[v] = c
    dist[v] = 0
    while len(deq) > 0:
        s = deq.popleft()
        if dist[s] >= d:
            break
        for t in G[s]:
            if t in dist.keys()
                pass
            else:
                dist[t] = dist[s] + 1
                color[t] = c
                deq.append(t)
                
for n in range(1, N+1):
    print(color[n])

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def dfs(graph, cur, color, dist):
    graph[cur].color = color
    if dist == 0:
        return
    for n in graph[cur].to:
        dfs(graph, n, color, dist-1)
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N+1)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a].to.append(b)
        graph[b].to.append(a)
    Q = int(input())
    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        dfs(graph, v, c, d)
    for i in range(1, N+1):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self):
        self.color = 0
        self.to = []

def dfs(graph, cur, color, visited, dist):
    visited[cur] = True
    graph[cur].color = color
    if dist == 0:
        return
    for n in graph[cur].to:
        if visited[n]:
            continue
        dfs(graph, n, color, visited, dist-1)
    
def main():
    N, M = [int(i) for i in input().split()]
    graph = [Node() for _ in range(N+1)]
    for _ in range(M):
        a, b = [int(i) for i in input().split()]        
        graph[a].to.append(b)
        graph[b].to.append(a)
    Q = int(input())
    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    for _ in range(Q):
        v, d, c = [int(i) for i in input().split()]
        visited = [False] * (N + 1)
        dfs(graph, v, c, visited, d)
    for i in range(1, N+1):
        print(graph[i].color)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stderr
from collections import deque

def solve():
    N, M = map(int, input().split())

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

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

    Q = int(stdin.readline())

    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    
    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

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

    cols = [0] * N

    for i in range(Q):
        bfs(N, Adj, v[i], d[i], c[i], cols)

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

def bfs(N, Adj, v, d, c, cols):
    visited = [False] * N
    visited[v] = True

    nxts = deque([[v, 0]])

    while nxts:
        u, dis = nxts.popleft()

        if dis > d:
            continue

        cols[u] = c

        for w in Adj[u]:
            if not visited[w]:
                visited[w] = True
                nxts.append([w, dis + 1])

    return

if __name__ == '__main__':
    solve()