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.

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

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


def paint(v, d, c):
    x, y = dp[v]
    if d <= y:
        return
    if x == 0:
        dp[v] = c, d
    else:
        dp[v] = x, d

    if d == 0:
        return
    for i in G[v]:
        paint(i, d - 1, c)


for v, d, c in reversed(C):
    paint(v, d, c)

for k in dp:
    print(k[0])

Solution (Python):


import sys, math, copy




HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"
MAX = 100001

dp = [0 for i in range(MAX)]
color = [0 for i in range(MAX)]
e = [[] for i in range(MAX)]

def paint(v, d, c):
    if not color[v]:
        color[v] = c
    if dp[v] >= d or d == 0:
        return
    dp[v] = d
    for u in e[v]:
        paint(u, d - 1, c)

def main():
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        e[a].append(b)
        e[b].append(a)
    q = int(input())
    vq, dq, cq = [], [], []
    for i in range(q):
        v, d, c = map(int, input().split())
        vq.append(v)
        dq.append(d)
        cq.append(c)
    assert len(vq) == len(dq) == len(cq) == q

    for i in reversed(range(q)):
        paint(vq[i], dq[i], cq[i])
    for i in range(n):
        print(color[i + 1])


main()

Solution (Python):
import sys
sys.setrecursionlimit(101010)

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    es[a].append(b)
    es[b].append(a)
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

mem = [[0,-1] for i in range(N)] 
def paint(v,d,c):
    mc,md = mem[v]
    if d <= md: return
    mem[v] = [mc if mc else c, d]
    if d == 0: return
    for to in es[v]:
        paint(to,d-1,c)

for v,d,c in reversed(qs):
    paint(v-1,d,c)
for c,d in mem:
    print(c)

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

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

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

memo = [[0] * (10+1) for i in range(N+1)]


def paint(v, d, i):
    
    if memo[v][d]:
        return

    
    memo[v][d] = i

    
    if d == 0:
        return

    
    paint(v, d-1, i)

    
    
    for u in Adj[v]:
        paint(u, d-1, i)



for q in range(Q-1, -1, -1):
    paint(v[q], d[q], q+1)


for i in range(1, N+1):
    
    if memo[i][0] != 0:
        print(c[memo[i][0]-1])
    else:
        print(0)

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

dp = [{-1: -1} for i in range(N)]
mark = {}
Q = int(input())
col = [0]*(Q+1)
col[-1] = 0
C = []
for i in range(Q):
    v, d, c = map(int, input().split())
    col[i] = c
    C.append((v-1, d))

def dfs(v, d, idx):
    if d <= max(dp[v]):
        return
    dp[v][d] = idx
    if d:
        for w in G[v]:
            dfs(w, d-1, idx)

for i in range(Q-1, -1, -1):
    v, d = C[i]
    dfs(v, d, i)
print(*(col[max(e.values())] for e in dp), sep='\n')

Solution (Python):
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


color, depth, graph = [], [], {}
def func(v, d, c):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return
    depth[v] = d
    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

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

    color = [0] * N
    depth = [0] * N
    for i in range(Q - 1, -1, -1):
        func(q[i][0], q[i][1], q[i][2])
    print(*color, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):
import sys


def dfs(v, d, c, e):
    if (dp[v][d] != 0):
        return dp[v][d]

    if (d == 0):
        dp[v][d] = c
        return dp[v][d]

    for u in e[v]:
        dp[u][d-1] = dfs(u, d-1, c, e)

    dp[v][d] = dfs(v, d-1, c, e)
    return dp[v][d]

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

dp = [[0]*11 for i in range(10**5+1)]
e = [[] for i in range(10**5+1)]

N, M = na()
for i in range(M):
    a, b = na()
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    
Q = ni()
qv = [[0,0,0] for i in range(Q)]
for i in range(Q):
    v, d, c = na()
    v -= 1
    qv[Q-1-i][0] = v
    qv[Q-1-i][1] = d
    qv[Q-1-i][2] = c

for i in range(Q):
    dfs(qv[i][0],qv[i][1],qv[i][2],e)

for i in range(N):
    print (dp[i][0])

Solution (Python):
import sys
sys.setrecursionlimit(100000)

n, m = map(int,input().split())
node = [[] for i 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())
vdc = [[0] * 3 for i in range(q)]
for i in range(q):
    vdc[i][0], vdc[i][1], vdc[i][2] = map(int, input().split())
vdc = vdc[::-1]

ans = [0] * (n + 1)
visited = [[0] * 11 for i in range(n + 1)]
def f(v, d, c):
    if d < 0:
        return
    if visited[v][d]:
        return

    visited[v][d] = 1
    if ans[v] == 0:
        ans[v] = c
        

    for x in node[v]: 
        f(x, d - 1, c)

for v, d, c in vdc:
    f(v, d, c)

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

Solution (Python):
from queue import deque


def paint(s, d, c):
    queue = deque([(d, s)])
    while queue:
        remains, v = queue.popleft()
        if painted[v] >= remains:
            continue
        if colors[v] == 0:
            colors[v] = c
        painted[v] = remains
        if remains:
            queue.extend((remains - 1, u) for u in links[v])


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)]
colors = [0] * (n + 1)
painted = [-1] * (n + 1)
while queries:
    paint(*queries.pop())

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

Solution (Python):
from collections import deque
from collections import defaultdict

G = defaultdict(list)
N, M = map(int, input().split())
color = [0] * (N + 1)

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

Solution (Python):
from collections import deque

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 = deque()
  vis[ V[ qi ] ] = D[ qi ]
  que.append( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while len( que ):
    d, u = que.popleft()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.append( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

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

Solution (Python):
from collections import defaultdict

def paint(v, d, c):
    if color[v] == 0:
        color[v] = c
    if dp[v] >= d or d == 0:
        return
    dp[v] = d
    for nb in graph[v]:
        paint(nb, d-1, c)

N, M = map(int, input().split())
dp = [0] * N
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)

Solution (Python):
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 + 1)
dp = [[0 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, color[i + 1] = map(int, input().split())
    dp[d][v - 1] = i + 1
 
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')

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

Solution (Python):
n, m = map(int, raw_input().split())

g = [[i] for i in xrange(n)]

for _ in xrange(m):
    u, v = map(lambda x: int(x) - 1, raw_input().split())
    g[u].append(v)
    g[v].append(u)

q = input()
c = [None] * q
dp = [[-1 for j in range(n)] for i in xrange(11)]
for i in xrange(q):
    v, d, c[i] = map(int, raw_input().split())
    dp[d][v - 1] = i
 
for i in reversed(range(1, 11)):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in xrange(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print(c[dp[0][i]])

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

g = [[i] for i in range(n)]

for _ in range(m):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)

q = int(input())
c = [None] * q
dp = [[-1 for j in range(n)] for i in range(11)]
for i in range(q):
    v, d, c[i] = map(int, input().split())
    dp[d][v - 1] = i
 
for i in reversed(range(1, 11)):
    dp[i - 1] = [max(dp[i - 1][u], max(dp[i][v] for v in g[u])) for u in range(n)]

for i in range(n):
    if dp[0][i] == -1:
        print('0')
    else:
        print(c[dp[0][i]])

Solution (Python):
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
    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]



clr=[0]*N
visited=[-1]*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)


for i in clr:
    print i

Solution (Python):
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 = [[0]*11 for _ in range(n+1)]
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]])

Solution (Python):
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 = [int(e) for e in input().split(' ')]

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

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

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

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


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

Solution (Python):
import sys
from collections import deque

def solve():
    def rec(v, d, i):
        if dp[v][d]:
            return

        dp[v][d] = i

        if d == 0:
            return

        rec(v, d - 1, i)

        for u in Adj[v]:
            rec(u, d - 1, i)


    N, M = map(int, sys.stdin.readline().split())

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

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

    Q = int(sys.stdin.readline())

    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

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

    dp = [[0]*(10 + 1) for i in range(N)]

    for i in range(Q):
        rec(v[i], d[i], i + 1)

        
            

        

    for i in range(N):
        if dp[i][0] > 0:
            print(c[dp[i][0] - 1])
        else:
            print(0)

if __name__ == '__main__':
    solve()

Solution (Python):

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 = [[-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]])

Solution (Python):
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)]
vdc = [list(map(int, input().split())) for _ in range(q)]

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


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

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

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


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

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

Solution (Python):
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] >= d:
            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())

Solution (Python):
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
    
    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])

Solution (Python):
def dfs(v, d, c):
    if vis[v][d] or d < 0:
        return
    vis[v][d] = 1
    if not color[v]:
        color[v] = c
    for u in E[v]:
            dfs(u, d - 1, c)
n, m = map(int, raw_input().split())
E = [[] for i in xrange(n + 1)]
for i in xrange(m):
    a, b = map(int, raw_input().split())
    E[a].append(b)
    E[b].append(a)
q = input()
operations = [map(int, raw_input().split()) for i in xrange(q)]
operations.reverse()
color = [0] * (n + 1)
vis = [[0] * 11 for i in xrange(n + 1)]
for op in operations:
    dfs(op[0], op[1], op[2])
for i in xrange(1, n + 1):
    print color[i]

Solution (Python):
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):
    if nuta[v] >= d:
        return

    nxts = deque([[v, d]])
    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 - 1:
                nuta[w] = step - 1
                nxts.append([w, step - 1])

    return

if __name__ == '__main__':
    solve()