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: Wrong Answer

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("fatal error.{} has drawed {}. but it will be drawed {}".format(self.id, self.color, color))
            return
        else:
            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:
    nodes[op[0]-1].draw(op[1],op[2])

for n in nodes:
    print(n.color)

Submission status: Wrong Answer

Solution code:
def Mea_distance(distance,p,v,d,cp,i):
	if d == 0:
		return -1
	if distance[p][v] == 1:
		r = 1
	if 0 < distance[p][v]:
		if i > 0:
			distance[cp][v] = distance[p][v] + 1
			distance[v][cp] = distance[p][v] + 1
		return distance[p][v] + 1
	else:
		K = []
		for ai,a in enumerate(distance[p]):
			if a == 1:
				if d > 1:
					k = Mea_distance(distance,ai,v,d - 1,p,i + 1)
					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,0) <= 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: Wrong Answer

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 )

exit()

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: Wrong Answer

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 ]
exit()
for i in range( N ):
  print( col[ i ] )

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def main():
    def _dinamic_programming(color_mapping,grpah,index,counter,limit,color,index_buffer):
        if counter > limit:
            return

        if index in index_buffer:
            return

        index_buffer.append(index)
        color_mapping[index] = color
        _index = grpah[index]
        counter += 1
        for i in _index:
            _dinamic_programming(color_mapping,grpah,i,counter,limit,color,index_buffer)

    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())
        index_buffer = []
        _dinamic_programming(ans,ab,v-1,0,d,c,index_buffer)

    for i in ans:
        print i

main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
edges += [[i, i] for i in range(n)]

q = int(input())
color = [0] * q
dp = [[0 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, color[i] = map(int, input().split())
    dp[d][v - 1] = i
 
for i in reversed(range(1, 11)):
    for u, v in edges:
        dp[i - 1][u] = max(dp[i - 1][u], dp[i][v])
        dp[i - 1][v] = max(dp[i - 1][v], dp[i][u])
 
print(*[color[dp[0][i]] for i in range(n)], sep = '\n')

Submission status: Wrong Answer

Solution code:
def recClr(v,d,c):
    if visited[v-1] >= d:
        return
    else:
        visited[v-1]=d
    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
visited=[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: Wrong Answer

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):
        if j == 0:
            distset[i].append(set([j+1]))
        elif j == 1:
            distset[i].append(set(nextnodes[i]))
            distset[i][j].add(j+1)
        else:
            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: Wrong Answer

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):
        if j == 0:
            distset[i].append(set([j+1]))
        elif j == 1:
            distset[i].append(set(nextnodes[i]))
        else:
            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: Wrong Answer

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)

print(res)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def main():
    n,m = LI()
    e = collections.defaultdict(set)
    for _ in range(m):
        a,b = LI()
        e[a-1].add(b-1)
        e[b-1].add(a-1)
    r = [0] * n

    q = I()
    qq = sorted([[_] + LI() for _ in range(q)], reverse=True)
    f = [-1] * n
    for _,v,d,c in qq:
        v -= 1
        if f[v] >= v:
            continue
        if r[v] == 0:
            r[v] = c
        q = [v]
        for nd in range(d-1,-1,-1):
            t = []
            for p in q:
                for vv in e[p]:
                    if f[vv] >= nd:
                        continue
                    f[vv] = nd
                    t.append(vv)
                    if r[vv] == 0:
                        r[vv] = c
            q = t

    return '\n'.join(map(str, r))



print(main())

Submission status: Wrong Answer

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 vdc in VDC:
    current = []
    next = []
    v=vdc[0]
    d=vdc[1]
    c=vdc[2]
    C[v-1] = c
    for ab in AB:
        if ab[0] == v:
            current.append(ab[1])
    for dist in range(d):
        if len(current) == 0:
            break
        for n in current:
            C[n-1] = c
            for ab in AB:
                if ab[0] == n:
                    next.append(ab[1])
        current = next
        next = []
for i in C:
    print(i)

Submission status: Wrong Answer

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




data = [list(map(int, input().split())) for _ in range(Q)]
data.reverse()
color_d = [-1]*(N+1)

for v, d, c in data:
    if color_d[v] >= d:
        pass
    # BFS
    deq = deque([v])
    if color[v] != 0:
        color[v] = c
    color_d[v] = d
    while len(deq) > 0:
        s = deq.popleft()
        for t in G[s]:
            if color_d[t] >= color_d[s] - 1:
                pass
            else:
                color_d[t] = color_d[s] - 1
                if color[t] == 0:
                    color[t] = c
                if color_d[t] > 0:
                    deq.append(t)
                
for n in range(1, N+1):
    print(color[n])

Submission status: Wrong Answer

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




data = [list(map(int, input().split())) for _ in range(Q)]
data.reverse()
color_d = [-1]*(N+1)

for v, d, c in data:
    # BFS
    dist = dict()
    deq = deque([v])
    color[v] = c
    color_d[v] = d
    while len(deq) > 0:
        s = deq.popleft()
        for t in G[s]:
            if color_d[t] >= color_d[s] - 1:
                pass
            else:
                color_d[t] = color_d[s] - 1
                if color[t] == 0:
                    color[t] = c
                if color_d[t] > 0:
                    deq.append(t)
                
for n in range(1, N+1):
    print(color[n])

Submission status: Wrong Answer

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]:
			if colist[i]!=col:
				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: Wrong Answer

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))
alive = [True for i in range(N)]
colors = [0 for i in range(N)]
sizes = [-1 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 or not alive[idx]:
            continue
        alive[idx] = False
        for nvi, ndi in nodes[idx].items():
            if nvi != idx:
                nodes[nvi].pop(idx)
            for nvj, ndj in nodes[idx].items():
                if nvi >= nvj:
                    continue
                if nvj in nodes[nvi]:
                    nodes[nvi][nvj] = nodes[nvj][nvi] = min(nodes[nvi][nvj], ndi + ndj)
                else:
                    nodes[nvi][nvj] = nodes[nvj][nvi] = ndi + ndj


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

Submission status: Wrong Answer

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

Q=input()
for i in xrange(Q):
    v,d,c=map(int,raw_input().split())
#    print v,d,c
    tmp=[0]*N
    recClr(v,d,c)
#    print "tmp",tmp
    for j in xrange(len(tmp)):
        if tmp[j]!=0:
            clr[j]=tmp[j]
#    print "clr",clr
#print clr   

for i in clr:
    print i

Submission status: Wrong Answer

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))
alive = [True for i in range(N)]
colors = [0 for i in range(N)]
sizes = [-1 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 or not alive[idx]:
            continue
        alive[idx] = False
        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], ndi + ndj)
                else:
                    nodes[nvi][nvj] = nodes[nvj][nvi] = ndi + ndj


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

Submission status: Wrong Answer

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

    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

    v.reverse()
    d.reverse()
    c.reverse()

    cols = [0] * N
    nuta = [-1] * N

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

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

def bfs(N, Adj, v, d, c, cols, nuta):
    nxts = deque([[v, d]])
    nuta[v] = max(nuta[v], d)

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

        if step <= 0:
            continue

        if cols[u] == 0:
            cols[u] = c

        for w in Adj[u]:
            if nuta[w] < step:
                nuta[w] = step
                nxts.append([w, step - 1])

                if cols[w] == 0:
                    cols[w] = c

    return

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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:
            now.pop(0)
            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: Wrong Answer

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
    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: Wrong Answer

Solution code:
import heapq
from collections import deque

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

def bfs(graph, start, color, dist, visited):
    q = [(0, start)]
    while q:
        d, cur = heapq.heappop(q)
        #print(d, cur)
        if cur in visited:
            continue
        graph[cur].color = color
        visited.add(cur)
        if d == dist:
            continue
        for n, cost in zip(graph[cur].to, graph[cur].costs):
            if n in visited:
                continue
            if d + cost > dist:
                continue
            heapq.heappush(q, (d+cost, n))
    #print("-" * 10)

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
        bfs(ngraph, v, c, d, visited)
    for i in range(1, N+1):
        print(ngraph[i].color)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Q=input()
for i in xrange(Q):
    v,d,c=map(int,raw_input().split())
#    print v,d,c
    tmp=[0]*N
    recClr(v,d,c)
#    print "tmp",tmp
    for j in xrange(len(tmp)):
        if tmp[j]!=0:
            clr[j]=tmp[j]
#    print "clr",clr
#print clr   

for i in clr:
    print i

Submission status: Wrong Answer

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
                        matrix[j][i] = 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: Wrong Answer

Solution code:

N,M=map(int,raw_input().split(' '))
g=[[] for i in range(N+1)]
color=[0]*(N+1)
called=[]

def paint(v,d,c):
    #print 'call'
    if d==0:
        return
    else:
        called.append(v)
        nextv=[]
        color[v]=c
        for p in g[v]:
            color[p]=c
            nextv.append(p)
        d-=1
        for p in nextv:
            if not(p in called): paint(p,d,c)
    #print color



for _ in range(1,M+1):
    a,b=map(int,raw_input().split(' '))
    if not(b in g[a]):
        g[a].append(b)
        g[b].append(a)

Q=int(raw_input())

for _ in range(Q):
    v,d,c=map(int,raw_input().split(' '))
    paint(v,d,c)
    called=[]

for i in range(1,len(color)):
    print color[i]

Submission status: Wrong Answer

Solution code:
max_n, max_m = map(int, input().split())
v = [[] for x in range(max_n + 1)]
color = ["0" for x in range(max_n + 1)]
def define(a, b):
    v[a].append(b)

for i in range(max_m):
    a, b = map(int, input().split())
    define(a, b)
    define(b, a)

def visit(point, length, col):
    color[point] = col
    if length:
        next_points = v[point]
        for next_point in next_points:
            if not color[next_point] == col:
                visit(next_point, length - 1, col)

q = int(input())
for i in range(q):
    a, b, c = input().split()
    visit(int(a), int(b), c)
print("\n".join(color[1:]))

Submission status: Wrong Answer

Solution code:
max_n, max_m = map(int, input().split())
v = [[] for x in range(max_n + 1)]
color = ["0" for x in range(max_n + 1)]
def define(a, b):
    v[a].append(b)

for i in range(max_m):
    a, b = map(int, input().split())
    define(a, b)
    define(b, a)

def visit(point, length, col):
    color[point] = col
    if length:
        next_points = v[point]
        print(next_points)
        for next_point in next_points:
            if not color[next_point] == col:
                visit(next_point, length - 1, col)

q = int(input())
for i in range(q):
    a, b, c = input().split()
    visit(int(a), int(b), c)
print("\n".join(color[1:]))

Submission status: Wrong Answer

Solution code:

N,M=map(int,raw_input().split(' '))
g=[[] for i in range(N+1)]
color=[0]*(N+1)
called=[]

def paint(v,d,c):
    #print 'call'
    if d==0:
        return
    elif v in called:
        return
    else:
        called.append(v)
        nextv=[]
        color[v]=c
        for p in g[v]:
            color[p]=c
            nextv.append(p)
        d-=1
        for p in nextv:
            paint(p,d,c)
    #print color



for _ in range(1,M+1):
    a,b=map(int,raw_input().split(' '))
    if not(b in g[a]):
        g[a].append(b)
        g[b].append(a)

Q=int(raw_input())

for _ in range(Q):
    v,d,c=map(int,raw_input().split(' '))
    paint(v,d,c)
    called=[]

for i in range(1,len(color)):
    print color[i]

Submission status: Wrong Answer

Solution code:

N,M=map(int,raw_input().split(' '))
g=[[] for i in range(N+1)]
color=[0]*(N+1)

def paint(v,d,c):
    #print 'call'
    if d==0:
        return
    else:
        nextv=[]
        color[v]=c
        for p in g[v]:
            color[p]=c
            nextv.append(p)
        d-=1
        for p in nextv:
            paint(p,d,c)
    #print color



for _ in range(1,M+1):
    a,b=map(int,raw_input().split(' '))
    if not(b in g[a]):
        g[a].append(b)
        g[b].append(a)

Q=int(raw_input())

for _ in range(Q):
    v,d,c=map(int,raw_input().split(' '))
    paint(v,d,c)

for i in range(1,len(color)):
    print color[i]

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
graph = dict()
colors = dict()        
for i in xrange(N):
    graph[i + 1] = []
    colors[i + 1] = 0
for i in xrange(M):
    a, b = map(int, raw_input().split())
    graph[a].append(b)
    graph[b].append(a)

def paint(curNodes, color, colors, remLevel):
    if remLevel == 0:
        return colors
    newCurNodes = []
    for node in curNodes:
        if colors[node] == color:
            continue
        colors[node] = color
        newCurNodes += graph[node]
    newCurNodes = list(set(newCurNodes))
    return paint(newCurNodes, color, colors, remLevel - 1)

Q = int(raw_input())
for i in xrange(Q):
    v, d, c = map(int, raw_input().split())
    colors = paint([v], c, colors, d + 1)
for i in xrange(N):
    print colors[i + 1]

Submission status: Wrong Answer

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 next not in history:
                history.add(next)
                paint(next, history, c, d - 1)


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

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