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:
from queue import deque


def dijkstra(s, d):
    queue = deque([(0, s)])
    paint = set()
    while queue:
        cost, v = queue.popleft()
        if cost > d:
            break
        paint.add(v)
        queue.extend((cost + 1, u) for u in links[v] if u not in paint)
    return paint


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)]
painted = set()
colors = [0] * (n + 1)
while queries:
    v, d, c = queries.pop()
    paint = dijkstra(v, d) - painted
    for i in paint:
        colors[i] = c
    painted |= paint

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

Submission status: Time Limit Exceeded

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

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

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

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

data = map(int, sys.stdin.read().split())

n = next(data)
m = next(data)
mat = sp.lil_matrix((n, n))

for i in range(m):
    a = next(data)
    b = next(data)
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

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

for i in range(q):
    v = next(data)
    d = next(data)
    c = next(data)
    color = query(mat, v, d, c, color)

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

Submission status: Time Limit Exceeded

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(d):
        acc1 = acc1 * mat
        acc2 = acc2 + acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color = color - color.multiply(mask)
    color = 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: Time Limit Exceeded

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=-1000
dp=[[INF for j in range(11)] 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):
	for j in range(N):
		tempMax=INF
		for k in chain[j]:
			if tempMax<dp[k][i+1]:
				tempMax=dp[k][i+1]
		if tempMax<dp[k][i]:
			tempMax=dp[k][i]
		dp[j][i]=tempMax
#	for i in range(N)
	
#print(dp)
for i in range(N):
	if dp[i][0]==INF:
		print(0)
	else:
		print(vdc[dp[i][0]][2]+1)

Submission status: Time Limit Exceeded

Solution code:
class Graph:
    """an un-directed graph."""

    def __init__(self, v):
        self.__adj = [[] for i in range(v)]

    def add_edge(self, v, w):
        self.__adj[v].append(w)
        self.__adj[w].append(v)

    def adj(self, v):
        return self.__adj[v]

    def v(self):
        return len(self.__adj)


def main():
    N, M = map(int, input().split())
    G = Graph(N)
    for i in range(M):
        a, b = map(int, input().split())
        G.add_edge(a - 1, b - 1)
    # print(G._Graph__adj)

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

    painted = [False] * (1 + N)
    remain = N
    for i in reversed(range(Q)):
        # print("remain ", remain, " i ", i)
        if (remain < 1):
            break
        vi, di, ci = v[i], d[i], c[i]
        marked = [False] * (1 + N)

        cnt = di + 1
        queue = []
        queue.append(vi)
        marked[vi] = True
        while cnt > 0:
            # print("queue ", queue)
            curr_queue = queue.copy()
            queue.clear()
            while len(curr_queue) > 0:
                pop = curr_queue.pop()
                # print("pop ", pop)
                if (not painted[pop]):
                    ans[pop] = ci
                    painted[pop] = True
                    remain -= 1
                    # print("paint ", pop, " remain ", remain)
                for adj in G.adj(pop - 1):
                    nex = adj + 1
                    if not marked[nex]:
                        # print("adj ", nex)
                        queue.append(nex)
                        marked[nex] = True
            cnt -= 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Graph:
    """an un-directed graph."""

    def __init__(self, v):
        self.__adj = [[] for i in range(v)]

    def add_edge(self, v, w):
        self.__adj[v].append(w)
        self.__adj[w].append(v)

    def adj(self, v):
        return self.__adj[v]

    def v(self):
        return len(self.__adj)


def main():
    N, M = map(int, input().split())
    G = Graph(N)
    for i in range(M):
        a, b = map(int, input().split())
        G.add_edge(a - 1, b - 1)
    # print(G._Graph__adj)

    Q = int(input())
    v = [0] * (1 + N)
    for query in range(Q):
        vi, di, ci = map(int, input().split())
        marked = [False] * (1 + N)
        cnt = di + 1
        queue = []
        queue.append(vi)
        marked[vi] = True
        while cnt > 0:
            # print("queue ", queue)
            curr_queue = queue.copy()
            queue.clear()
            while len(curr_queue) > 0:
                pop = curr_queue.pop()
                # print("pop ", pop)
                v[pop] = ci
                for adj in G.adj(pop - 1):
                    nex = adj + 1
                    if not marked[nex]:
                        # print("adj ", nex)
                        queue.append(nex)
                        marked[nex] = True
            cnt -= 1

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

nodeid = 0

class node():
    def __init__(self):
        global nodeid
        self.neighbor = []
        self.color = 0
        self.id = nodeid
        nodeid += 1
        self.opid = (-1, 0)
    def add(self, new_neighbor):
        self.neighbor.append(new_neighbor)
    def draw(self, p, d, color, opid):
        if d < 0:
            return
        if self.opid[0] == opid[0] and self.opid[1] > opid[1]:
            return
        else:
            self.opid = opid
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        for n in self.neighbor:
            if p is n:
                continue
            n.draw(self, d-1, color, (opid[0], d-1) )

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

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

Q = int(input())

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

operation.reverse()
super = node()
for i, op in enumerate(operation):
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(super, op[1],op[2], (i,d))

for n in nodes:
    print(n.color)

Submission status: Time Limit Exceeded

Solution code:
def painting(N,A,v,d,c):
	if d < 0:
		return
	if A[v][d] == 0:
		A[v][d] = c
		i = 0
		while i < len(N):
			if 1 in N[v][i:]:
				i = i + N[v][i:].index(1)
			else:
				break
			painting(N,A,i,d-1,c)
			i = i + 1
			
N,M = list(map(int,input().split()))
nodes = [[0]*N for i in range(N)]
dp = [[0]*11 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: Time Limit Exceeded

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

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

Solution code:
import numpy as np

nodeid = 0

class node():
    def __init__(self):
        global nodeid
        self.neighbor = []
        self.color = 0
        self.id = nodeid
        nodeid += 1
    def add(self, new_neighbor):
        self.neighbor.append(new_neighbor)
    def draw(self, p, d, color):
        if d < 0:
            return
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        for n in self.neighbor:
            if p is n:
                continue
            n.draw(self, d-1, color)

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

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

Q = int(input())

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

operation.reverse()
super = node()
for op in operation:
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(super, op[1],op[2])

for n in nodes:
    print(n.color)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

nodeid = 0

class node():
    def __init__(self):
        global nodeid
        self.neighbor = []
        self.color = 0
        self.id = nodeid
        nodeid += 1
    def add(self, new_neighbor):
        self.neighbor.append(new_neighbor)
    def draw(self, d, color):
        if d < 0:
            return
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        for n in self.neighbor:
            n.draw(d-1, color)

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

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

Q = int(input())

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

operation.reverse()

for op in operation:
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(op[1],op[2])

for n in nodes:
    print(n.color)

Submission status: Time Limit Exceeded

Solution code:
def Mea_distance(A,p,v,d,cp):
	if d == 0:
		return -1
	if A[p][v] == 1:
		return 1
	elif 0 < A[p][v]:
		if cp != p:
			A[cp][v] = A[p][v] + 1
			A[v][cp] = A[p][v] + 1
		return A[p][v] + 1
	else:
		K = []
		for ai,a in enumerate(A[p]):
			if a == 1:
				if d > 1:
					k = Mea_distance(A,ai,v,d - 1,p)
					if k > 0:
						K.append(k)
				else:
					return -1
		if K:
			mk = min(K)
			return mk
		else:
			return -1

N,M = map(int,input().split())
distance = [[0]* N for j in range(N)]
for m in range(M):
	a,b = map(int,input().split())
	distance[a-1][b-1] = 1
	distance[b-1][a-1] = 1
Q = int(input())
paint = [list(map(int,input().split())) for i in range(Q)]
paint.reverse()
white = [i for i in range(N)]
Colour = [0] * N
white2 = white[:]
for p in paint:
	v,d,c = p
	for w in white:
		if 0 < Mea_distance(distance,w,v-1,d,w) <= d:
			Colour[w] = c
			white2.remove(w)
	white = white2[:]
	if v-1 in white2:
		Colour[v - 1] = c
		white2.remove(v - 1)
	white = white2[:]
print("\n".join(map(str,Colour)))

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 ):
  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 = queue.Queue()
  vis[ V[ qi ] ] = D[ qi ]
  que.put( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while not que.empty():
    d, u = que.get()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.put( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
vertices,edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for v in range(edges):
    a,b = (int(n) - 1 for n in input().split(" "))
    connect[a].append(b)
    connect[b].append(a)
color = [0 for n in range(vertices)]
trial = int(input())
queue = []
for t in range(trial):
    ver,dep,col = (int(n) for n in input().split(" "))
    ver -= 1
    queue.append([ver,dep,col])
queue.reverse()
dp = [[1 for n in range(11)] for m in range(vertices)]
for q in queue:
    ver,dep,col = q
    newqueue = [ver]
    # print(q)
    if not color[ver]:
        color[ver] = col
    if dp[ver][dep]:
        while dep > 0 and newqueue != []:
            # print(newqueue)
            tempqueue = []
            for q in newqueue:
                dp[q][dep] = 0
                for c in connect[q]:
                    if dp[c][dep - 1]:
                        tempqueue.append(c)
                    if not color[c]:
                        color[c] = col
            newqueue = tempqueue
            # print(queue)
            dep -= 1
for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n,m = map(int, input().split())
a, b = [], []
adj = [[] for _ in range(n)]
for i in range(m):
    _a, _b = map(int, input().split())
    _a -= 1
    _b -= 1
    a.append(_a)
    b.append(_b)
    adj[_a].append(_b)
    adj[_b].append(_a)
q = int(input())
v, d, c = [], [], []
for i in range(q):
    _v, _d, _c = map(int, input().split())
    _v -= 1
    v.append(_v)
    d.append(_d)
    c.append(_c)

color = defaultdict(int)
current_color = None
done = set()
def f(vertex, d):
    if (vertex, d) in done:
        return
    done.add((vertex,d))
    if d == 0:
        color[vertex] = current_color
        return
    for u in adj[vertex]:
        f(u, d - 1)
    f(vertex, d - 1)

for i in range(q-1, -1, -1):
    current_color = c[i]
    f(v[i], d[i])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def paint(v, d, c):
    if (v, d) in memo:
        return
    else:
        memo[(v, d)] = True
    if d == 0:
        color[v] = c
    elif d > 0:
        paint(v, d-1, c)
        for nb in graph[v]:
            paint(nb, d-1, c)

memo = {}
N, M = map(int, input().split())
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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    def _depth_search(color_mapping,grpah,index,counter,limit,color):
        if counter > limit:
            return

        color_mapping[index] = color
        _index = grpah[index]
        counter += 1
        for i in _index:
            _depth_search(color_mapping,grpah,i,counter,limit,color)

    n,m = map(int,raw_input().split())
    ab = [[] for i in range(n)]
    ans = [0 for i in range(n)]

    for i in range(m):
        _a,_b = map(int,raw_input().split())
        ab[_a-1].append(_b-1)
        ab[_b-1].append(_a-1)

    q = int(raw_input())

    for i in range(q):
        v,d,c = map(int,raw_input().split())
        _depth_search(ans,ab,v-1,0,d,c)

    for i in ans:
        print i

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
 
q = int(input())
vv = [None] * q
dd = [None] * q
cc = [None] * q
dp = np.array([[-1 for j in range(11)] for i in range(n)])
for i in range(q):
    vv[i], dd[i], cc[i] = map(int, input().split())
    dp[vv[i] - 1][dd[i]] = i
 
for i in reversed(range(1, 11)):
    for j in range(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 range(n):
    if dp[i][0] == -1:
        print('0')
    else:
        print(cc[dp[i][0]])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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 = np.zeros((n+1, 11), int)
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: Time Limit Exceeded

Solution code:
def recClr(v,d,c):
    if clr[v-1]==0:
        clr[v-1]=c
#        print "recClr",v,d,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

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

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 = map(int, input().split(' '))

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

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

Q = int(input())


vdc = [map(int, 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: Time Limit Exceeded

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)
    [dp(e, d-1, c) for e in dic[v-1]]


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

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

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

Q = int(input())


vdc = [tuple(map(int, 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: Time Limit Exceeded

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 None

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


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

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

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

Q = int(input())


vdc = [tuple(map(int, 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: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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


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

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

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

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = ['0']*N

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


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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


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

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

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

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = ['0']*N

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = c
        return None

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


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

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

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

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

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

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


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

dic = [[] for _ in range(N)]


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

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import defaultdict

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

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

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


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

dic = defaultdict(list)

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

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

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

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


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

dic = {}

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a] = dic.get(a, []) + [b]
    dic[b] = dic.get(b, []) + [a]

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

memo = {}
def dp(v, d, c):
    if memo.get((v, d), False):
        return None

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

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


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

dic = {}

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a] = dic.get(a, []) + [b]
    dic[b] = dic.get(b, []) + [a]

Q = int(input())

vdc = []

for q in range(Q):
    vdc.append(tuple(map(int, input().split(' '))))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


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

Submission status: Time Limit Exceeded

Solution code:
# -*- encoding: utf-8 -*-
N,M = map(int, input().split())
C=[]
for i in range(N):
    C.append(0)
AB=[]
for i in range(M):
    AB.append(list(map(int, input().split())))
nextnodes=[]
for i in range(N):
    nextnodes.append([])
for ab in AB:
    #print("%d,%d,%d" % (N, ab[0], ab[1]))
    nextnodes[ab[0]-1].append(ab[1])
    nextnodes[ab[1]-1].append(ab[0])

Q = int(input())
VDC=[]
maxdist = 0
for i in range(Q):
    vdc = list(map(int, input().split()))
    VDC.append(vdc)
    if vdc[1] > maxdist:
        maxdist = vdc[1]
distset=[]
for i in range(N):
    distset.append([])
    for j in range(maxdist+1):
        distset[i].append(None)

for i in range(Q):
    vdc=VDC[i]
    current = []
    next = []
    done = set()
    v=vdc[0]
    d=vdc[1]
    c=vdc[2]
    if distset[v-1][d] != None:
        for n in distset[v-1][d]:
            C[n-1] = c
        continue

    C[v-1] = c
    #print("i: %d, dist: 0, n: %d, c: %d" % (i, v, c))
    current.extend(nextnodes[v-1])
    done.add(v)
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            if n in done:
                continue
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            next.extend(nextnodes[n-1])
            done.add(n)
        current = next
        next = []
    if distset[v-1][d] == None:
        distset[v-1][d] = done
for i in C:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- encoding: utf-8 -*-
N,M = map(int, input().split())
C=[]
for i in range(N):
    C.append(0)
AB=[]
for i in range(M):
    AB.append(list(map(int, input().split())))
nextnodes=[]
for i in range(N):
    nextnodes.append([])
for ab in AB:
    #print("%d,%d,%d" % (N, ab[0], ab[1]))
    nextnodes[ab[0]-1].append(ab[1])
    nextnodes[ab[1]-1].append(ab[0])

Q = int(input())
VDC=[]
for i in range(Q):
    VDC.append(list(map(int, input().split())))
for i in range(Q):
    vdc=VDC[i]
    current = []
    next = []
    done = set()
    v=vdc[0]
    d=vdc[1]
    c=vdc[2]
    C[v-1] = c
    #print("i: %d, dist: 0, n: %d, c: %d" % (i, v, c))
    current.extend(nextnodes[v-1])
    done.add(v)
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            if n in done:
                continue
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            next.extend(nextnodes[n-1])
            done.add(n)
        current = next
        next = []
for i in C:
    print(i)