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 sys
sys.setrecursionlimit(100000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
for _ in range(m):
    ai,bi=map(int, input().split())
    ai-=1;bi-=1
    e[ai].append(bi);e[bi].append(ai)
Q=int(input())
q=[tuple(map(int, input().split())) for _ in range(Q)]

q.reverse()
color=[0]*n
from collections import deque
que=deque()
used=set()
def dfs(v,d,c):
    if d<0:
        return
    used.add(v)
    if not color[v]:
        color[v]=c
    #que.append((v,d))
    for u in e[v]:
        if u not in used:
            dfs(u,d-1,c)
for v,d,c in q:
    v-=1
    used=set()
    dfs(v,d,c)
    #print(v,d,c,"   ",*color)
for c in color:
    print(c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

for j in range(11):
    npaint = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        if not paint[v]:
            continue

        paint[v].sort(key=lambda p: -p[0])
        pv = []
        for i, d in paint[v]:
            if i in used[v]:
                continue
            if not pv or pv[-1][1] < d:
                pv.append((i, d))
                used[v].add(i)

        if not pv:
            continue

        num[v] = max(num[v], pv[0][0])

        if j == 10:
            break

        for u in G[v]:
            for i, d in pv:
                if d > 0:
                    npaint[u].append((i, d - 1))
    paint = npaint

for v in range(1, N+1):
    if num[v] == -1:
        print(0)
    else:
        print(color[num[v]])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
num = [-1] * (N+1)
color = [0] * (N+1)
paint = [[] for _ in range(N+1)]
for v, d, c, i in queries:
    paint[v].append([i, d, c])

for _ in range(10):
    npaint = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        if not paint[v]:
            continue
        paint[v].sort(key=lambda p: -p[0])
        pv = []
        for i, d, c in paint[v]:
            if not pv or pv[-1][1] < d:
                pv.append((i, d, c))
        if num[v] < pv[0][0]:
            num[v], _, color[v] = pv[0]
        for u in G[v]:
            for i, d, c in pv:
                if d > 0:
                    npaint[u].append([i, d - 1, c])
    paint = npaint

print(*color[1:], sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
num = [-1] * (N+1)
color = [0] * (N+1)
paint = [[] for _ in range(N+1)]
for v, d, c, i in queries:
    paint[v].append([i, d, c])

for _ in range(10):
    npaint = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        paint[v].sort(key=lambda p: -p[0])
        if paint[v] and num[v] < paint[v][0][0]:
            num[v], _, color[v] = paint[v][0]

        for u in G[v]:
            for i, d, c in paint[v]:
                if d > 0:
                    npaint[u].append([i, d - 1, c])
    paint = npaint

print(*color[1:], sep='\n')

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(list)
    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    q = int(readline())
    mat = [[] for _ in range(q)]

    for i in range(q):
        mat[i] = list(map(int, readline().split()))

    paint = [[0, -1, 0] for _ in range(n + 1)]

    for v, d, c in mat[::-1]:
        if d == 0 and paint[v] == -1:
            paint[v][0] = c
            paint[v][1] = 0
            paint[v][2] = v
        else:
            if paint[v][1] >= d:
                continue
            que = deque()
            que.append((v, d, c))
            outer = defaultdict(list)
            visited = [False] * (n + 1)
            while que:
                cur, rem, color = que.popleft()
                visited[cur] = True
                if paint[cur][0] == 0:
                    paint[cur][0] = color
                    paint[cur][1] = rem
                    paint[cur][2] = v
                    if rem == 0:
                        outer[v].append(cur)
                if rem > 0:
                    n_rem1 = rem - 1
                    for nx in edge[cur]:
                        if visited[nx]:
                            continue
                        if paint[nx][0] != 0:
                            if paint[nx][1] >= n_rem1:
                                pass
                            else:
                                if rem > paint[nx][1]:
                                    n_rem2 = rem - paint[nx][1]
                                    par = paint[nx][2]
                                    for out in outer[par]:
                                        que.append((out, n_rem2))
                        else:
                            que.append((nx, n_rem1, color))

    for i in range(1, n + 1):
        print(paint[i][0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    
dp = [[(-1,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
from itertools import product
for i0,i,u in product(range(1,-1,-1), range(0,11), range(n)):
# for i0 in range(10, -1, -1):
    if i==0:
        for i,v,d,_ in qs:
            if i0<=d:
                dp[0][v] = (i,d)
    else:
#     for i in range(1,11):
#         for u in range(n):
        if dp[i-1][u][0]>dp[i][u][0]:
            ind0, d0 = dp[i-1][u]
        else:
            ind0, d0 = dp[i][u]
        for v in ns[u]:
            ind,d = dp[i-1][v]
            if ind>ind0 and d>0:# and i0<=i+d:
                ind0, d0 = ind, d-1
        dp[i][u] = (ind0, d0)
#     print(dp[10])
write("\n".join(map(str, ((qs[dp[10][u][0]][3] if dp[10][u][0]>=0 else 0) for u in range(n)))))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n, m = map(int, readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
q = int(readline())
chk = []
for i in range(q):
  V,D,C = map(int,readline().split())
  chk.append((V,D,C))
  
from collections import deque
ans = [0]*n

def bfs(s,col,d):
  global cnt
  que = deque()
  que.append((s,1,col))
  if ans[s] == 0:
    ans[s] = col
    cnt += 1
  while que:
      now,p,col = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if ans[i] == 0:
            ans[i] = col
            cnt += 1
          if p < d:
            que.append((i,p+1,col))

cnt = 0
for i in chk[::-1]:
  vv,d,cc = i
  bfs(vv-1,cc,d)
  if cnt == n:
    break
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
G = [list() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
Q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(Q)][::-1]
dp = [[Q]*11 for _ in range(n)]
for i, (v, d, _) in enumerate(queries):
  dp[v-1][d] = i
for d in range(10, 0, -1):
  for v in range(n):
    if dp[v][d] < Q:
      dp[v][d-1] = min(dp[v][d-1], dp[v][d])
      for x in G[v]:
        dp[x][d-1] = min(dp[x][d-1], dp[v][d])
queries.append((-1, -1, 0))
color = [queries[dp[v][0]][2] for v in range(n)]
print(*color, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
G = [list() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
Q = int(input())
color = [0]*n
queries = [tuple(map(int, input().split())) for _ in range(Q)]
for v, d, c in reversed(queries):
  v -= 1
  if color[v]: continue
  color[v] = c
  q = deque()
  q.append((v, d))
  while q:
    v, d = q.popleft()
    for x in G[v]:
      if not color[x]:
        color[x] = c
        if d > 1:
          q.append((x, d-1))
print(*color, sep='\n')

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    q = int(input())
    vdc = [list(map(int, input().split())) for _ in [0]*q]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    dist = [[0]*11 for _ in [0]*n]
    dist2 = [0]*n

    for v, d, c in vdc[::-1]:
        v -= 1
        if dist[v][d] != 0:
            continue
        q = [(v, d, c)]
        dist[v][d] = c
        if dist2[v] == 0:
            dist2[v] = c
        while q:
            v, d, c = q.pop()
            for i in g[v]:
                if dist[i][d-1] == 0:
                    dist[i][d-1] = c
                    if dist2[i] == 0:
                        dist2[i] = c
                    if d > 1:
                        q.append((i, d-1, c))
    for i in dist2:
        print(i)


main()

Submission status: Wrong Answer

Solution code:

from collections import deque


def bfs(op):
    global color, V
    reached = [0] * len(color)
    q = deque()

    d = op[1]
    c = op[2]
    q.append(op[0])
    color[op[0]] = c
    while d >= 0 and len(q):
        for v in V[q.popleft()]:
            if reached[v]:
                continue
            q.append(v)
            reached[v] = 1
            color[v] = c
        d -= 1


n, m = map(int, input().split())
V = [None] + [[] for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    V[bi] += [ai]
    V[ai] += [bi]

Q = int(input())
OP = []
for i in range(Q):
    OP.append(list(map(int, input().split())))

color = [None] + [0] * n
for op in OP:
    bfs(op)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if depth[v - 1] == -1:
        ans[v - 1] = c
    depth[v - 1] = d
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if depth[x] == -1:
                ans[x] = c
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if depth[x] == 0:
                continue
            dq += [x]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if depth[v - 1] == -1:
        ans[v - 1] = c
    depth[v - 1] = d
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if depth[x] == -1:
                ans[x] = c
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if depth[x]:
                dq += [x]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    if ans[v - 1] == 0:
        ans[v - 1] = c
    depth[v - 1] = d
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if ans[x] == 0:
                ans[x] = c
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if depth[x]:
                dq += [x]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
depth = [-1] * n
for v, d, c in Q[::-1]:
    if depth[v - 1] >= d:
        continue
    depth[v - 1] = d
    if ans[v - 1] == 0:
        ans[v - 1] = c
    dq += [v - 1]
    while dq:
        u = dq.popleft()
        for x in G[u]:
            if ans[x] == 0:
                ans[x] = c
            if depth[x] >= depth[u] - 1:
                continue
            depth[x] = depth[u] - 1
            if depth[u] - 1 == 0:
                continue
            dq += [x]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

ans = [0] * n
q = I()
Q = LIR(q)
dq = deque()
max_dist = [-1] * n
for v, d, c in Q[::-1]:
    if max_dist[v - 1] >= d:
        continue
    if ans[v - 1] == 0:
        ans[v - 1] = c
    max_dist[v - 1] = d
    dq += [(v - 1, d)]
    while dq:
        u, dist = dq.popleft()
        for x in G[u]:
            if ans[x] == 0:
                ans[x] = c
            if max_dist[x] >= dist - 1:
                continue
            max_dist[x] = dist - 1
            if dist - 1 == 0:
                continue
            dq += [(x, dist - 1)]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(op):
    global color, V
    reached = [0] * len(color)
    q = deque()

    d = op[1]
    c = op[2]
    q.append(op[0])
    color[op[0]] = c
    while d >= 0 and len(q):
        for v in V[q.popleft()]:
            if reached[v]:
                continue
            q.append(v)
            reached[v] = 1
            color[v] = c
        d -= 1


n, m = map(int, input().split())
V = [None] + [[] for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    V[bi] += [ai]
    V[ai] += [bi]

Q = int(input())
OP = []
for i in range(Q):
    OP.append(list(map(int, input().split())))

color = [None] + [0] * n
for op in OP:
    bfs(op)

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

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(op):
    global color, V
    reached = [0] * len(color)
    q = deque()

    d = op[1]
    c = op[2]
    q.append(op[0])
    color[op[0]] = c
    while d and len(q):
        for v in V[q.popleft()]:
            if reached[v]:
                continue
            q.append(v)
            reached[v] = 1
            color[v] = c
        d -= 1


n, m = map(int, input().split())
V = [None] + [[] for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    V[bi] += [ai]
    V[ai] += [bi]

Q = int(input())
OP = []
for i in range(Q):
    OP.append(list(map(int, input().split())))

color = [None] + [0] * n
for op in OP:
    bfs(op)

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

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(op):
    global color
    reached = [0] * len(color)
    q = deque()

    d = op[1]
    c = op[2]
    q.append(op[0])
    color[op[0]] = c
    while d and len(q):
        for v in V[q.popleft()]:
            if reached[v]:
                continue
            q.append(v)
            color[v] = c
        d -= 1


n, m = map(int, input().split())
V = [None] + [[] for _ in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    V[bi] += [ai]
    V[ai] += [bi]

Q = int(input())
OP = []
for i in range(Q):
    OP.append(list(map(int, input().split())))

color = [None] + [0] * n
for op in OP:
    bfs(op)

for c in color:
    print(c)

Submission status: Wrong Answer

Solution code:
#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(11)] for _ in range(n)]        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    colors[v] = c
    checker[v][d] = 1 #checked
    
    dfs(d-1, v, c) #dが低いやつについて全て埋めておく必要がある。もう先着ありで無理ですよ、って宣言。
    
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v-1,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v,c)
    
for i in range(n):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(11)] for _ in range(n)]

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    colors[v] = c
    checker[v][d] = 1 #checked
    
    dfs(d-1, v, c) #dが低いやつについて全て埋めておく必要がある。もう先着ありで無理ですよ、って宣言。
    
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v-1,c)
    
for i in range(n):
    print(colors[i])

Submission status: Wrong Answer

Solution code:
# 写経AC
from collections import deque

N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    VDC[i][0] -= 1

color = [0] * N
# dp[v][d]: 頂点vから距離dは塗装済みか
visited = [[False] * 11 for _ in range(N)]

def bfs(v, d, c):
    """
    頂点vから距離d以下の頂点について
    情報(color, visited)を更新
    """
    que = deque([(v, d - 1)])
    while que:
        n, t = que.popleft()
        for w in edge[n]:
            if visited[w][t]:
                continue
            for dist in range(t + 1):
                visited[w][dist] = True
            if color[w] == 0:
                color[w] = c
            if t - 1 >= 0:
                que.append((w, t - 1))


for v,d,c in reversed(VDC):
    if visited[v][d]: # 既に塗装済み
        continue
    if color[v] == 0:
        color[v] = c
    for dist in range(d + 1):
        # 距離d以下は塗装済み
        visited[v][dist] = True
    
    bfs(v, d, c)

print(*color, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    VDC[i][0] -= 1

color = [0] * N
# dp[v][d]: 頂点vから距離dは塗装済みか
visited = [[False] * 11 for _ in range(N)]

def bfs(v, d, c):
    """
    頂点vから距離d以下の頂点を
    visitedを更新しつつ塗装する
    """
    que = deque([(v, d)])
    while que:
        v, d = que.popleft()
        for w in edge[v]:
            if visited[w][d - 1]:
                continue
            for dist in range(d):
                visited[w][dist] = True
            if color[w] == 0:
                color[w] = c
            if d - 1 > 0:
                que.append((w, d - 1))

for v,d,c in reversed(VDC):
    if visited[v][d]: # 既に塗装済み
        continue
    if color[v] == 0:
        color[v] = c
    for dist in range(d + 1):
        # [0, d]を塗装済みにする
        visited[v][dist] = True
    
    bfs(v, d, c)

print(*color, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

INF = 10**14

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

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    Q = int(input())
    queries = [None] * Q
    dp = [[-1] * 11 for _ in range(N)]
    for i in range(Q):
        v, d, c = map(int, input().split())
        queries[i] = (v, d, c)
    for i in range(Q)[::-1]:
        v, d, c = queries[i]
        dp[v-1][d] = i
    for j in range(10)[::-1]:
        for i in range(N):
            dp[i][j] = max(dp[i][j], dp[i][j+1])
            for nxt in adj[i]:
                if dp[i][j] < dp[nxt][j+1]:
                    dp[i][j] = dp[nxt][j+1]
    for i in range(N):
        x = dp[i][0]
        if x == -1:
            print(0)
        else:
            print(queries[x][2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[list(map(int,input().split())) for _ in range(q)][::-1]
color=[0]*(n+1)
dic={}
for i in range(q):
  v,d,c=arr[i]
  tmp=0
  tq=collections.deque()
  tq.append((v,0,c))
  checked=[0]*(n+1)
  checked[v]=1
  if color[v]==0:
    color[v]=c
  else:
    continue
  while 1:
    if len(tq)==0:
      break
    tv,td,tc=tq.popleft()
    if tv not in dic:
      dic[tv]=d-td
    else:
      if td<=dic[tv]:
        continue
    if td>=d:
      break
    for u in g[tv]:
      if checked[u]==0:
        checked[u]=1
        if color[u]==0:
          color[u]=tc
        tq.append((u,td+1,tc))
for i in range(1,n+1):
  print(color[i])