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:
# -*- 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 = []
    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])
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            next.extend(nextnodes[n-1])
        current = next
        next = []
for i in C:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def dp(v, d, c):
    if res[v-1] == 0:
        res[v-1] = c

    if d == 0:
        return None

    if np.all(res > 0):
        return None

    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:
import numpy as np

def dp(v, d, c):
    if res[v-1] == 0:
        res[v-1] = c

    if d == 0:
        return None

    if np.all(res > 0):
        return None



    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(' '))))

vdc.reverse()

res = np.zeros(N)

for q in range(Q):
    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())))
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 = []
    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))
    for ab in AB:
        if ab[0] == v:
            current.append(ab[1])
        if ab[1] == v:
            current.append(ab[0])
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            C[n-1] = c
            #print("i: %d, dist: %d, n: %d, c: %d" % (i, dist+1, n, c))
            for ab in AB:
                if ab[0] == n:
                    next.append(ab[1])
                if ab[1] == n:
                    next.append(ab[0])
        current = next
        next = []
for i in C:
    print(i)

Submission status: Time Limit Exceeded

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)
'''
for ai,a in enumerate(A):
	for k in a:
		print(k)
	print(ai)
'''
Colour = [0] * N
Q = int(input())
for q in range(Q):
	v,d,c = map(int,input().split())
	Colour[v - 1] = c
	if d == 0:
		continue
	for n in range(N):
		if d == 1 :
			if (not A[0][v - 1][n]):
				continue
			else:
				Colour[n] = c
		else:
			if A[d - 1][v - 1][n] or A[d - 2][v - 1][n] > 0:
				Colour[n] = c
	
for C in Colour:
	print(C)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def fuga(graph, start, color, dist, visited, cache={}):
    #print(start, dist)
    if start in cache:
        if cache[start] >= dist:
            return
        cache[start] = dist
    if start not in visited:
        graph[start].color = color
        visited.add(start)
    for n, c in zip(graph[start].to, graph[start].costs):
        if n in visited:
            continue
        if c > dist:
            continue
        #print("to {}, cost{}".format(n, c))
        visited.add(n)
        graph[n].color = color


def hoge(graph, start):
    visited = {start}
    q = deque(zip(graph[start].costs, graph[start].to))
    node = Node()
    while q:
        d, c = q.popleft()        
        node.to.append(c)
        node.costs.append(d)
        if d == 10:
            continue
        for n in graph[c].to:
            if n in visited:
                continue
            visited.add(c)
            q.append((d+1, n))
    return node
    
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[a].costs.append(1)
        graph[b].to.append(a)
        graph[b].costs.append(1)
    ngraph = [Node()]
    for s in range(1, N+1):
        ngraph.append(hoge(graph, s))
    Q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(Q)]
    visited = set()
    for q in reversed(queries):
        v, d, c = q
        fuga(ngraph, v, c, d, visited)
    for i in range(1, N+1):
        print(ngraph[i].color)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
ini=map(int,raw_input().split())
tt=[[] for i in range(ini[0])]
for i in range(ini[1]):
	link=map(int,raw_input().split())
	tt[link[0]-1].append(link[1]-1)
	tt[link[1]-1].append(link[0]-1)
colist=[0 for i in range(ini[0])] 
time=input()
def iron(col,pos,leng):
	colist[pos]=col
	leng-=1
	if leng>=0:
		for i in tt[pos]:
			iron(col,i,leng)
for i in range(time):
	nuru=map(int,raw_input().split())
	iron(nuru[2],nuru[0]-1,nuru[1])
     
for i in colist:
	print i

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M = map(int,input().split())
nodes = [[0]* N for j 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
mat1 = np.matrix(nodes)
mat2 = mat1.copy()
A = [mat1.tolist()]
for i in range(10):
	mat2 = mat2.dot(mat1)
	a = mat2.tolist()
	A.append(a)

Colour = [0] * N
Q = int(input())
for q in range(Q):
	v,d,c = map(int,input().split())
	Colour[v - 1] = c
	if d == 0:
		continue
	for n in range(N):
		if d == 1 :
			if A[0][v - 1][n] == 0:
				continue
			else:
				Colour[n] = c
		else:
			if A[d - 1][v - 1][n] + A[d - 2][v - 1][n] > 0:
				Colour[n] = c
	
for C in Colour:
	print(C)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
res = [0]*N
r = [[]for i in range(N)]
for i in range(M):
    a, b = map(int, raw_input().split())
    r[a-1].append(b)
    r[b-1].append(a)
Q = input()
v = [0]*Q
d = [0]*Q
c = [0]*Q
for i in range(Q):
    v[i], d[i], c[i] = map(int, raw_input().split())
def fill(t,c,d):
    n = d
    if n==0:
        return
    n -= 1
    for i in t:
        res[i-1] = c
        if n>0:
            fill(r[i-1],c,n)
for i in range(Q):
    res[v[i]-1]=c[i]
    fill(r[v[i]-1],c[i],d[i])
for i in res:
    print i

Submission status: Time Limit Exceeded

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

q = int(input())
node_color = [0 for _ in range(n + 1)]
for j in range(q):
    v, d, c = map(int, input().split())

    now = [v]
    paint = {v}
    for dist in range(d):
        buff = []
        now = list(set(now))
        for k in now:
            paint |= set(node[k])
            buff.extend(node[k])
        now = buff

    for l in paint:
        node_color[l] = c

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def fuga(graph, start, color, dist, visited):
    #print(start, dist)
    if start not in visited:
        graph[start].color = color
        visited.add(start)
    for n, c in zip(graph[start].to, graph[start].costs):
        if n in visited:
            continue
        if c > dist:
            continue
        #print("to {}, cost{}".format(n, c))
        visited.add(n)
        graph[n].color = color


def hoge(graph, start):
    visited = {start}
    q = deque(zip(graph[start].costs, graph[start].to))
    node = Node()
    while q:
        d, c = q.popleft()
        node.to.append(c)
        node.costs.append(d)
        if d == 10:
            continue
        for n in graph[c].to:
            if n in visited:
                continue
            visited.add(c)
            q.append((d+1, n))
    return node
    
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[a].costs.append(1)
        graph[b].to.append(a)
        graph[b].costs.append(1)
    ngraph = [Node()]
    for s in range(1, N+1):
        ngraph.append(hoge(graph, s))
    Q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(Q)]
    visited = set()
    for q in reversed(queries):
        v, d, c = q
        fuga(ngraph, v, c, d, visited)
    for i in range(1, N+1):
        print(ngraph[i].color)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

e = [np.array([[0 for i in range(n)] for j in range(n)]) for k in range(11)]

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

for i in range(n):
	e[0][i][i] = 1
	e[1][i][i] = 1

for i in range(2,11):
	e[i] = e[i-1].dot(e[1])

# for i in e:
# 	print(i)

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

# for i in e:
# 	print(i)

color = [0 for i in range(n)]
for v,d,c in que:
	for i in range(n):
		if e[d][v-1][i] >= 1:
			color[i] = c

color = list(map(str,color))
print("\n".join(color))

Submission status: Time Limit Exceeded

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):
		G[i][d] |= G[i][d-1]
		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: Time Limit Exceeded

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

q = int(input())
node_color = [0 for _ in range(n + 1)]
for j in range(q):
    v, d, c = map(int, input().split())

    now = [v]
    paint = {v}
    for dist in range(d):
        buff = []
        for k in now:
            paint |= set(node[k])
            buff.extend(node[k])
        now = buff

    for l in paint:
        node_color[l] = c

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

Submission status: Time Limit Exceeded

Solution code:
import collections

if __name__ == '__main__':
    n, m = map(int, input().split())

    routes = collections.defaultdict(list)
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        routes[a].append(b)
        routes[b].append(a)

    matrix = [[None for _ in range(n)] for _ in range(n)]
    for i in range(n):
        cnt = 1
        buffer = set([i])
        matrix[i][i] = 0

        while buffer and not all(matrix[i]):
            temp = set()
            for x in buffer:
                for j in routes[x]:
                    if matrix[i][j] is None:
                        matrix[i][j] = cnt
                        temp.add(j)

            buffer = temp
            cnt += 1

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

        for w in range(n):
            if matrix[v][w] is not None and matrix[v][w] <= d: colors[w] = c

    for color in colors: print(color)

Submission status: Time Limit Exceeded

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

tt=[[] for i in range(ini[0])]

for i in range(ini[1]):
	link=map(int,raw_input().split())
	tt[link[0]-1].append(link[1]-1)
	tt[link[1]-1].append(link[0]-1)

colist=[0 for i in range(ini[0])]

time=input()

def iron(col,pos,leng):
	if colist!=col:
		colist[pos]=col
		leng-=1
		if leng>=0:
			for i in tt[pos]:
				iron(col,i,leng)

for i in range(time):
	nuru=map(int,raw_input().split())
	iron(nuru[2],nuru[0]-1,nuru[1])

for i in colist:
	print i

Submission status: Time Limit Exceeded

Solution code:
input_lines = str(input())

N = int(input_lines.split(' ')[0])
M = int(input_lines.split(' ')[1])

aBAry = []
for i in range(M):
    input_lines = str(input())
    aBAry.append(input_lines.split(' '))
    #print(aBAry)

input_lines = str(input())
Q = int(input_lines)

vDCAry = []
for i in range(Q):
    input_lines = str(input())
    vDCAry.append(input_lines.split(' '))

'''print(N)
print(M)
print(aBAry)
print(Q)
print(vDCAry)'''

answer = [0] * N

linkAry = []
for i in range(N):
    linkNum = []
    for aB in aBAry:
        if int(aB[0]) == i + 1:
            linkNum.append(int(aB[1]))
        if int(aB[1]) == i + 1:
            linkNum.append(int(aB[0]))
    linkAry.append(linkNum)
#print(linkAry)

for vDC in vDCAry:
    #print(vDC)
    vAry = [int(vDC[0])]
    for i in range(int(vDC[1])):
        vAryAfter = []
        for v in vAry:
            #vAryAfter = linkAry[v-1]
            vAryAfter.extend(linkAry[v-1])
            #print(vAryAfter)
        vAry.extend(vAryAfter)
        #print(vAry)
        vAry = list(set(vAry))
    #print(vAry)
    for v in vAry:
        answer[v-1] = int(vDC[2])
    #print(answer)

for ans in answer:
    print(ans)

Submission status: Time Limit Exceeded

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

q = int(input())
node_color = [0 for _ in range(n + 1)]
for j in range(q):
    v, d, c = map(int, input().split())

    now = [v]
    paint = {v}
    for dist in range(d):
        buff = []
        for k in now:
            paint |= set(node[k])
            buff.extend(node[k])
        now.extend(buff)

    for l in paint:
        node_color[l] = c

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

Submission status: Time Limit Exceeded

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

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

tt=[[] for i in range(ini[0])]

for i in range(ini[1]):
	link=map(int,raw_input().split())
	tt[link[0]-1].append(link[1]-1)
	tt[link[1]-1].append(link[0]-1)

colist=[0 for i in range(ini[0])]

time=input()

def iron(col,pos,leng):
	colist[pos]=col
	leng-=1
	if leng>=0:
		for i in tt[pos]:
			iron(col,i,leng)

for i in range(time):
	nuru=map(int,raw_input().split())
	iron(nuru[2],nuru[0]-1,nuru[1])

for i in colist:
	print i

Submission status: Time Limit Exceeded

Solution code:
def floyd(n,d):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k],d[j][i]+d[i][k])
    return d
n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
d = [[float('inf')for j in range(n)]for i in range(n)]
for i in range(n):
    d[i][i] = 0
for i in range(m):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1][b[i]-1] = 1
    d[b[i]-1][a[i]-1] = 1
q = int(input())

v = [0 for i in range(q)]
dist = [0 for i in range(q)]
c = [0 for i in range(q)]

for i in range(q):
    v[i],dist[i],c[i] = map(int,input().split())
color = [0 for i in range(n)]

d = floyd(n,d)

for i in range(q):
    for j in range(n):
        if d[v[i]-1][j] <= dist[i]:
            color[j] = c[i]
for i in range(n):    
    print(color[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, raw_input().split())
res = [0]*N
a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, raw_input().split())
r = [[]for i in range(N)]
for i in range(M):
    r[a[i]-1].append(b[i])
    r[b[i]-1].append(a[i])
Q = input()
v = [0]*Q
d = [0]*Q
c = [0]*Q
for i in range(Q):
    v[i], d[i], c[i] = map(int, raw_input().split())
def fill(t,c,d):
    n = d
    if n==0:
        return
    n -= 1
    for i in t:
        res[i-1] = c
        if n>0:
            fill(r[i-1],c,n)
for i in range(Q):
    res[v[i]-1]=c[i]
    fill(r[v[i]-1],c[i],d[i])
for i in res:
    print i

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque

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

def fuga(graph, start, color, dist, visited):
    #print(start, dist)
    if start not in visited:
        graph[start].color = color
        visited.add(start)
    for n, c in zip(graph[start].to, graph[start].costs):
        if n in visited:
            continue
        if c > dist:
            continue
        #print("to {}, cost{}".format(n, c))
        visited.add(n)
        graph[n].color = color


def hoge(graph, start):
    visited = {start}
    q = deque(zip(graph[start].costs, graph[start].to))
    node = Node()
    while q:
        d, c = q.popleft()
        if c in visited:
            continue
        visited.add(c)
        node.to.append(c)
        node.costs.append(d)
        if d == 10:
            continue
        for n in graph[c].to:
            if n in visited:
                continue
            q.append((d+1, n))
    return node
    
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[a].costs.append(1)
        graph[b].to.append(a)
        graph[b].costs.append(1)
    ngraph = [Node()]
    for s in range(1, N+1):
        ngraph.append(hoge(graph, s))
    Q = int(input())
    queries = [[int(i) for i in input().split()] for _ in range(Q)]
    visited = set()
    for q in reversed(queries):
        v, d, c = q
        fuga(ngraph, v, c, d, visited)
    for i in range(1, N+1):
        print(ngraph[i].color)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Solution code:
import numpy as np
N,M = map(int,input().split())
nodes = [[0 for i in range(N)] for j 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
mat1 = np.matrix(nodes)
mat2 = mat1.copy()
A = [mat1.tolist()]
for i in range(10):
	mat2 = mat2.dot(mat1)
	a = mat2.tolist()
	A.append(a)
Colour = [0] * N
Q = int(input())
for q in range(Q):
	v,d,c = map(int,input().split())
	Colour[v - 1] = c
	if d == 0:
		continue
	for n in range(N):
		if d == 1 :
			if A[0][v - 1][n] == 0:
				continue
			else:
				Colour[n] = c
		else:
			if A[d - 1][v - 1][n] + A[d - 2][v - 1][n] > 0:
				Colour[n] = c
	
for C in Colour:
	print(C)

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])

Hen=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    Hen.append((int(hyo[0]) , int(hyo[1])))


#隣を保持する
tonari=list(range(0,N,1))
for idx in range(0,N,1):
    tonari[idx]=[]

for (a,b) in Hen:
    tonari[a-1].append(b-1)
    tonari[b-1].append(a-1)

Q=int(input())
Nuri=[]
for idx in range(0,Q,1):
    mozir=input()
    hyo=mozir.split(' ')
    Nuri.append((int(hyo[0])-1 , int(hyo[1]) , int(hyo[2])))

Nuri.reverse()

ans=list(range(0,N,1))
for idx in range(0,N,1):
    ans[idx]=0

for (tyu,dist,iro) in Nuri:
    if ans[tyu]==0:
        #色塗り
        ans[tyu]=iro
    miru=[tyu]
    scaned=[tyu]
    for idx in range(0,dist,1):
        mirunext=[]
        for tenn in miru:
            mirunext.extend(tonari[tenn])

        #remove dup
        mirunext_cands=list(set(mirunext))
        miru=[]
        for cand in mirunext_cands:
            if ans[cand]==0:
                #色塗り
                ans[cand]=iro
            if not (cand in scaned):    
                miru.append(cand)
        scaned.extend(miru)


#出力
for tenn in ans:
    print(tenn)

Submission status: Time Limit Exceeded

Solution code:
inf = 100
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):
	for d in range(1,11):
		for j in G[i][d-1]:
			G[i][d] |= G[j][1]

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

Solution code:
from collections import defaultdict,  deque

visited = [False]*(10**6 + 1)
color = [0]*(10**6 + 1)
level = [None]*(10**6 + 1)

class Graph:
  
    def __init__(self,vertices):
        self.V= vertices
        self.graph = defaultdict(list)
  
    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
        
    def rmvEdge(self, u, v):
        for index, key in enumerate(self.graph[u]):
            if key == v:
                self.graph[u].pop(index)
        for index, key in enumerate(self.graph[v]):
            if key == u:
                self.graph[v].pop(index)
                
def BFS(graph, start, colorTemp, depth):
    queue = deque()
    queue.append(start)
    color[start] = colorTemp
    visited[start] = True
    level[start] = 0
    while queue:
        s = queue.popleft()
        if level[s] >= depth:
            break
        for i in graph[s]:
            if not visited[i]:
                level[i] = level[s] + 1
                queue.append(i)
                color[i] = colorTemp
                visited[i] = True
    
n, m = map(int, raw_input().split())

g = Graph(n)

for _ in xrange(m):
    a, b = map(int, raw_input().split())
    g.addEdge(a, b)

q = int(raw_input())

for _ in xrange(q):
    v, d, c = map(int, raw_input().split())
    visited = [False for i in xrange(n+1)]
    level = [0 for i in xrange(n+1)]
    BFS(g.graph, v, c, d)
    #print color[1: n+1]

for i in xrange(1, n+1):
    print color[i]

Submission status: Time Limit Exceeded

Solution code:
#coding=UTF-8


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])

Hen=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    Hen.append((int(hyo[0]) , int(hyo[1])))


#隣を保持する
tonari=list(range(0,N,1))
for idx in range(0,N,1):
    tonari[idx]=[]

for (a,b) in Hen:
    tonari[a-1].append(b-1)
    tonari[b-1].append(a-1)

Q=int(input())
Nuri=[]
for idx in range(0,Q,1):
    mozir=input()
    hyo=mozir.split(' ')
    Nuri.append((int(hyo[0])-1 , int(hyo[1]) , int(hyo[2])))

Nuri.reverse()

ans=list(range(0,N,1))
for idx in range(0,N,1):
    ans[idx]=0

for (tyu,dist,iro) in Nuri:
    if ans[tyu]==0:
        #色塗り
        ans[tyu]=iro
    miru=[tyu]
    for idx in range(0,dist,1):
        mirunext=[]
        for tenn in miru:
            mirunext.extend(tonari[tenn])

        #remove dup
        mirunext_cands=list(set(mirunext))
        miru=[]
        for cand in mirunext_cands:
            if ans[cand]==0:
                #色塗り
                ans[cand]=iro
            miru.append(cand)


#出力
for tenn in ans:
    print(tenn)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,  deque

visited = [False]*(10**6 + 1)
color = [0]*(10**6 + 1)
level = [None]*(10**6 + 1)

class Graph:
  
    def __init__(self,vertices):
        self.V= vertices
        self.graph = defaultdict(list)
  
    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
        
    def rmvEdge(self, u, v):
        for index, key in enumerate(self.graph[u]):
            if key == v:
                self.graph[u].pop(index)
        for index, key in enumerate(self.graph[v]):
            if key == u:
                self.graph[v].pop(index)
                
def BFS(graph, start, colorTemp, depth):
    queue = deque()
    queue.append(start)
    color[start] = colorTemp
    visited[start] = True
    level[start] = 0
    while queue:
        s = queue.popleft()
        if level[s] >= depth:
            break
        for i in graph[s]:
            if not visited[i]:
                level[i] = level[s] + 1
                queue.append(i)
                color[i] = colorTemp
                visited[i] = True
    
n, m = map(int, raw_input().split())

g = Graph(n)

for _ in xrange(m):
    a, b = map(int, raw_input().split())
    g.addEdge(a, b)

q = int(raw_input())

for _ in xrange(q):
    v, d, c = map(int, raw_input().split())
    visited = [False]*(10**6 + 1)
    level = [None]*(10**6 + 1)
    BFS(g.graph, v, c, d)
    #print color[1: n+1]

for i in xrange(1, n+1):
    print color[i]

Submission status: Time Limit Exceeded

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

e = [[[i] for j in range(11)] for i in range(n+1)]

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

for i in range(2,11):
	for j in range(1,n+1):
		e[j][i] = list(e[j][i-1])
		l = tuple(e[j][i])
		for k in l:
			e[j][i].extend((e[k][1]))
		e[j][i] = set((e[j][i]))

# for i in e:
# 	print(i)

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

color = [0 for i in range(n+1)]
for v,d,c in que:
	for i in e[v][d]:
		color[i] = c

color = list(map(str,color))
print("\n".join(color[1:]))

Submission status: Time Limit Exceeded

Solution code:
inf = 100
N, M = map(int, input().split())
WF = [[inf]*N for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().split())
	WF[a-1][b-1] = 1
	WF[b-1][a-1] = 1
for i in range(N):
	WF[i][i] = 0
for k in range(N):
	for i in range(N):
		for j in range(N):
			WF[i][j] = min(WF[i][j], WF[i][k]+WF[k][j])
C = [0]*N
Q = int(input())
for _ in range(Q):
	v, d, c = map(int, input().split())
	for i in range(N):
		if WF[v-1][i] <= d:
			C[i] = c

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

Submission status: Time Limit Exceeded

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

link = [[] for i in range(N)]
color = [0] * N

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

Q = int(input())


def paint(current, history, c, d):
    color[current] = c
    if d > 0:
        for next in link[current]:
            if history[next] < d:
                history[next] = d
                paint(next, history, c, d - 1)


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

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

Submission status: Time Limit Exceeded

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

e = [[[i] for j in range(11)] for i in range(n+1)]

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

for i in range(2,11):
	for j in range(1,n+1):
		e[j][i] = list(e[j][i-1])
		l = tuple(e[j][i])
		for k in l:
			e[j][i].extend((e[k][1]))
		e[j][i] = set((e[j][i]))

# for i in e:
# 	print(i)

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

color = [0 for i in range(n+1)]
for v,d,c in que:
	for i in e[v][d]:
		color[i] = c

color = list(map(str,color))
print("\n".join(color[1:]))