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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

def size(x):
    return -par[find(x)]
  
n, m = map(int, readline().split())
par = [-1]*n
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)
    unite(u,v)
    
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
cnt = [0]*n

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

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

Submission status: Time Limit Exceeded

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:
      if cnt == n:
        break    
      now,p,col = que.popleft()
      if p > d:
        break
      for i in g[now]:
          if p <= d and ans[i] == 0:
            ans[i] = col
            cnt += 1
            if cnt == n:
              break           
          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: Time Limit Exceeded

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 p <= d and 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: Time Limit Exceeded

Solution code:
import heapq,sys

input=sys.stdin.readline

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

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

ans=[0]*N
time=[-1]*N


for i in range(Q):
    v,d,c=query[i]
    que=[(0,v,d)]
    heapq.heapify(que)
    while que:
        val,v,di=heapq.heappop(que)
        time[v]=di
        if not ans[v]:
            ans[v]=c
        for nv in edge[v]:
            if di-1>time[nv]:
                time[nv]=di-1
                heapq.heappush(que,(val+1,nv,di-1))

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

Submission status: Time Limit Exceeded

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):
  if dp[v-1][d] == Q:
    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: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(f):
    global n, V
    dist = [None] + [float('inf')] * n
    q = deque()

    q.append(f)
    dist[f] = 0
    while len(q):
        v = q.popleft()
        for c in V[v]:
            if dist[c] != float('inf'):
                continue
            q.append(c)
            dist[c] = dist[v] + 1

    return dist


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

distance = [None] + [[] for _ in range(n)]
for i in range(1, n + 1):
    distance[i] = bfs(i)

color = [0] * n
for i in range(Q):
    vi, di, ci = map(int, input().split())
    for i, d in enumerate(distance[vi][1:]):
        if d <= di:
            color[i] = ci

for c in color:
    print(c)

Submission status: Time Limit Exceeded

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
    if colors[v]==0: #not colored yet
        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: Time Limit Exceeded

Solution code:
#b
#naive (TLE)

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*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)
    
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
    
    #bfs
    queue = [v-1]
    while(d>=0):
        next_queue = []
        for p in queue:
            if colors[p]==0:
                colors[p] = c
            nodes = edges[p]
            next_queue += nodes
        d -= 1
        queue = next_queue

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
E=[]
for _ in range(m):
  E.append(tuple(int(i) for i in input().split()))
q=int(input())
Q=[]
for _ in range(q):
  Q.append(tuple(int(i) for i in input().split()))

DP=[[[0]*2 for i in range(n)] for j in range(11)]
for i in range(q):
  v,d,c=Q[i]
  DP[d][v-1][0]=i+1
  DP[d][v-1][1]=c

for d in range(10)[::-1]:
  for v in range(n):
    if DP[d+1][v][0]>DP[d][v][0]:
      DP[d][v]=DP[d+1][v]
  for e in range(m):
    a,b=E[e]
    a-=1
    b-=1
    if DP[d+1][a][0]>DP[d][b][0]:
      DP[d][b]=DP[d+1][a]
    if DP[d+1][b][0]>DP[d][a][0]:
      DP[d][a]=DP[d+1][b]
for i in range(n):
  print(DP[0][i][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]

graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
query = query[::-1]

dp = [[-1] * (10 + 1) for i in range(n)]
first = [0] * n
def solve(v, d, c):
    if d < 0:
        return
    if dp[v][d] != -1:
        return
      
    dp[v][d] = c
    if first[v] == 0:
        first[v] = c

    solve(v, d - 1, c)
    for u in graph[v]:
        solve(u, d - 1, c)
    return
  

for v, d, c in query:
    v -= 1
    solve(v, d, c)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappop, heappush

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)]
VDC.reverse()

INF = 10 ** 3

color = [-1] * N

def dijkstra(n, d, c):
    dist = [INF] * N
    dist[n] = 0
    que = [(0, n)]

    while que:
        dv, v = heappop(que)
        if dist[v] < dv: continue

        if color[v] < 0: color[v] = c
        if d == dv: continue
        
        for w in edge[v]:
            if dist[w] > dv + 1:
                dist[w] = dv + 1
                heappush(que, (dist[w], w))

def main():
    for v,d,c in VDC:
        dijkstra(v-1, d, c)

    for c in color:
        print(max(c, 0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        tres[y][i] = max(tres[y][i], res[x][i])
  res = tres
#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
  mxd = max(mxd, d)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(mxd):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  #clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
  clean()
#print(qc)

for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
#print(qc)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(x)
      d = max(d, qd[x])
clean()
for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    A = LI()
    A.sort()
    ans = 0
    for i in range(N):
        ans += A[-i*2-2]
    print(ans)
    return

def examB():
    def bfs(n, e, fordfs,D,c,visited,C,cur):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        if not visited[e]:
            C[e] = c
            cur += 1
        visited[e] = True
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            if nowW>=D:
                continue
            for ne in fordfs[now]:
                if not visited[ne]:
                    cur += 1
                    C[ne] = c
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    visited[ne] = True
                    que.append(ne)
        return C, visited, cur
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -=1; b -=1
        V[a].append(b)
        V[b].append(a)
    q = I()
    Q = [[]for _ in range(q)]
    for i in range(q):
        Q[i] = LI()
    C = [0]*N
    visited = [False]*N
    cur = 0
    for v,d,c in Q[::-1]:
        C,visited,cur = bfs(N, v-1, V,d,c,visited,C,cur)
        if cur==N:
            break
    for ans in C:
        print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    A = LI()
    A.sort()
    ans = 0
    for i in range(N):
        ans += A[-i*2-2]
    print(ans)
    return

def examB():
    def bfs(n, e, fordfs,D,c,visited,C):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        if not visited[e]:
            C[e] = c
        visited[e] = True
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            if nowW>=D:
                continue
            for ne in fordfs[now]:
                if not visited[ne]:
                    C[ne] = c
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    visited[ne] = True
                    que.append(ne)
        return C, visited
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -=1; b -=1
        V[a].append(b)
        V[b].append(a)
    q = I()
    Q = [[]for _ in range(q)]
    for i in range(q):
        Q[i] = LI()
    C = [0]*N
    visited = [False]*N
    for v,d,c in Q[::-1]:
        C,visited = bfs(N, v-1, V,d,c,visited,C)
    for ans in C:
        print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Submission status: Time Limit Exceeded

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


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done={v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          done.add(idx)
          for k in g.get(idx,list()):
            if k not in done:
              n_queue.add(k)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        done = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
            done.add(idx)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      done = {v}
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop()
			D[cur] = dd
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop(0)
			D[cur] = dd
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop(0)
			D[cur] = dd
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	n, m, *L = map(int, open(0).read().split())
	AB = L[:2 * m]
	Q = L[2 * m + 1:][::-1]
	G = [[] for _ in range(n)]
	C = [0] * n
	D = [-1] * n
	for a, b in zip(*[iter(AB)] * 2):
		a -= 1
		b -= 1
		G[a] += [b]
		G[b] += [a]
	for c, d, v in zip(*[iter(Q)] * 3):
		q = [(v - 1, d)]
		while q:
			cur, dd = q.pop(0)
			if not C[cur]:
				C[cur] = c
			if not dd:
				continue
			for nxt in G[cur]:
				if D[nxt] >= dd:
					continue
				q.append((nxt, dd - 1))
	print("\n".join(map(str, C)))

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, M, *L = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(L[:2 * M])] * 2):
        E[a].append(b)
        E[b].append(a)

    colors = [0] * (N + 1)
    visited = [False] * (N + 1)

    for v, d, c in reversed(tuple(zip(*[iter(L[2 * M + 1:])] * 3))):
        Q = deque([(d, v)])
        while Q:
            cnt, v = Q.popleft()
            if colors[v] == 0:
                colors[v] = c
            visited[v] = cnt
            if cnt > 0:
                Q.extend((cnt - 1, u) for u in E[v] if visited[u] < cnt)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    def dfs(d,x,c):
        if dp[(d,x)] != None:
            return
        dp[(d,x)] = 1
        if d == 0:
            f[x] = c
        else:
            dfs(d-1,x,c)
            for y in v[x]:
                dfs(d-1,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    dp = defaultdict(lambda : None)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(d,x,c)
    for i in f:
        print(i)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Time Limit Exceeded

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)]
color=[0]*(n+1)
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
  color[v]=c
  while 1:
    if len(tq)==0:
      break
    tv,td,tc=tq.popleft()
    if td>=d:
      break
    for u in g[tv]:
      if checked[u]==0:
        checked[u]=1
        color[u]=tc
        tq.append((u,td+1,tc))
for i in range(1,n+1):
  print(color[i])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    def dfs(k,d,x,c):
        if not f[x]:
            f[x] = c
        if k == d:
            return
        for y in v[x]:
            dfs(k+1,d,y,c)
    n,m = LI()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = I()
    l = LIR(q)
    l = l[::-1]
    for x,d,c in l:
        x -= 1
        dfs(0,d,x,c)
    for i in f:
        print(i)
    return

#C
def C():
    n = I()

    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Time Limit Exceeded

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

n, m = map(int,input().split())
nei =[[i] for i in range(n)]

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

color = [0 for i in range(n)]
#print(nei)
def paint(v,d,c):
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for i in nei[v]:
        paint(i,d-1,c)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2])
    #print(color)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
nei =[[i] for i in range(n)]

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

color = [0 for i in range(n)]
#print(nei)
def paint(v,d,c):
    if color[v] == 0:
        color[v] = c
    if d == 0:
        return
    for i in nei[v]:
        paint(i,d-1,c)

q = int(input())
vbc = [list(map(int,input().split())) for i in range(q)][::-1]

for i in range(q):
    paint(vbc[i][0]-1,vbc[i][1],vbc[i][2])
    #print(color)

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