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:
#!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 d <= dp[x]:
            return
        dp[x] = d
        f[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 : -1)
    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: 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())
if n>2000 or m>2000 or q>2000:
  print(-1)
else:
  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: Wrong Answer

Solution code:

n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

while len(Q) > 0:
    node, dis, col = Q.pop(0)
    
    if used[node][dis] == True:
        continue
        
    used[node][dis] = True
    
    if color[node] == 0:
        color[node] = col

    if dis > 0:
        if node in g:
            for v in g[node]:
                Q.append([v, dis-1, col])
    
for x in color:
    print(x)

Submission status: Wrong Answer

Solution code:
n, m  = map(int, input().split())
g     = {}
level = [-1 for _ in range(n)]
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []
temp = []

for lev in range(q):
    node, dis, col = map(int, input().split())
    temp.append([node-1, dis, col, lev])

for  x in temp[::-1]:
    Q.append(x)
    
while len(Q) > 0:
    p = Q.pop(0)
    node, dis, col, lev = p[0], p[1], p[2], p[3]
    
    if lev > level[node]:
        level[node] = lev
        color[node] = col
        
        if node in g:
            for v in g[node]:
                if dis - 1 >= 0 and level[node] > level[v]:
                    Q.append([v, dis-1, col, lev])
for x in color:
    print(x)

Submission status: Wrong Answer

Solution code:
n, m  = map(int, input().split())
g     = {}
level = [-1 for _ in range(n)]
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for lev in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col, lev])
    
while len(Q) > 0:
    p = Q.pop(0)
    node, dis, col, lev = p[0], p[1], p[2], p[3]
    
    if lev > level[node]:
        level[node] = lev
        color[node] = col
        
        if node in g:
            for v in g[node]:
                if dis - 1 >= 0 and level[node] > level[v]:
                    Q.append([v, dis-1, col, lev])
for x in color:
    print(x)

Submission status: Wrong Answer

Solution code:
n, m  = map(int, input().split())
g     = {}
level = [-1 for _ in range(n)]
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for lev in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col, lev])
    
while len(Q) > 0:
    p = Q.pop(0)
    node, dis, col, lev = p[0], p[1], p[2], p[3]
    
    if lev > level[node]:
        level[node] = lev
        color[node] = col
        
        if node in g:
            for v in g[node]:
                if dis - 1 >= 0 and color[node] != color[v]:
                    Q.append([v, dis-1, col, lev])
for x in color:
    print(x)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
Q=int(input())
X=[[int(i) for i in input().split()] for i in range(Q)]
color=[0]*Q
dp=[[-1]*N for i in range(11)]
for i in range(Q-1,-1,-1):
    v, d, c=X[i]
    v=v-1
    color[i]=c
    dp[d][v]=i

for d in range(10,0,-1):
    for x in range(N):
        for y in table[x]:
            dp[d-1][y]=max(dp[d][x],dp[d-1][y])
for i in range(N):
    s=-1
    for d in range(11):
        s=max(s,dp[d][i])
    if s==-1:
        print(0)
    else:
        print(color[s])

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()

    if n > 2000:
        exit()

    G = defaultdict(list)
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    q = II()
    Q = [LI() for _ in range(q)]

    color = [0] * n
    for v, d, c in Q:
        v -= 1
        q = deque()
        q.append((v, 0))
        visited = set()
        color[v] = c
        while q:
            v, dist = q.popleft()
            if dist >= d:
                break
            for to in G[v]:
                if to in visited:
                    continue
                visited.add(to)
                color[to] = c
                q.append((to, dist + 1))

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


main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()

    if n > 2000:
        exit()

    G = defaultdict(list)
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    q = II()
    Q = [LI() for _ in range(q)]
    # Q.reverse()

    color = [0] * n
    for v, d, c in Q:
        v -= 1
        q = deque()
        q.append((v, d))
        visited = set()
        while q:
            v, dist = q.pop()
            visited.add(v)
            color[v] = c
            if dist <= 0:
                continue
            for to in G[v]:
                if to in visited:
                    continue
                q.append((to, dist - 1))

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


main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()
    
    if n > 2000:
        exit()

    G = defaultdict(list)
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    q = II()
    Q = [LI() for _ in range(q)]
    # Q.reverse()

    color = [0] * n
    for v, d, c in Q:
        v -= 1
        q = deque()
        q.append((v, 0))
        visited = set()
        while q:
            v, dist = q.pop()
            visited.add(v)
            color[v] = c
            if dist == d:
                continue
            for to in G[v]:
                if to in visited:
                    continue
                q.append((to, dist + 1))

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


main()

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, m = LI()

    G = defaultdict(list)
    for _ in range(m):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    q = II()
    Q = [LI() for _ in range(q)]
    # Q.reverse()

    if n > 2000:
        exit()
    color = [0] * n
    for v, d, c in Q:
        v -= 1
        q = deque()
        q.append((v, 0))
        visited = set()
        while q:
            v, dist = q.pop()
            visited.add(v)
            color[v] = c
            if dist == d:
                continue
            for to in G[v]:
                if to in visited:
                    continue
                q.append((to, dist + 1))

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


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] 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())

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

color = [0] * n
depth = [-1] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist <= depth[node]:
        return
    depth[node] = dist
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

if n > 2000 or m > 2000:
    exit()

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())
if q > 2000:
    exit()

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

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

if n > 2000 or m > 2000:
    exit()

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())
if q > 2000:
    exit()

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

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)

Submission status: Wrong Answer

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

col = [0 for _ in range(n)]
def bfs(bs, d, c):
  if d <= 0:
    return bs
  nset = set()
  for b in bs:
    nset = nset.union(set(g[b]))
  _bs = nset.union(bs)
  if bs == _bs or len(_bs) == n:
    return _bs
  else:
    return bfs(_bs, d-1, c)
  
q = int(input())
for _ in range(q):
  v, d, c = map(int, input().split())
  col[v-1] = c
  dd = bfs(set(g[v-1]), d-1, c)
  for b in dd:
    col[b] = c
for c in col:
  print(c)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

if n > 2000 or m > 2000:
    exit()

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())
if q > 2000:
    exit()

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

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

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

for co in color:
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] 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())
v = []
d = []
c = []
for _ in range(q):
    V, D, C = map(int, input().split())
    v.append(V-1)
    d.append(D)
    c.append(C)
v = v[::-1]
d = d[::-1]
c = c[::-1]

color = [0] * n

def dfs(node, dist, dist_max, col):
    if dist > dist_max:
        return
    if color[node] > 0:
        return
    color[node] = col
    for next_node in g[node]:
        dfs(next_node, dist+1, dist_max, col)

for i in range(q):
    dfs(v[i], 0, d[i], c[i])

for co in color:
    print(co)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
q=[list(map(int,input().split())) for i in range(Q)]
C=[]
for i in range(Q):
  v,d,c=q[i]
  dp[v-1][d]=i
  C.append(c)
for d in range(1,10)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""


n, m = map(int, input().split())

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

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        for i in range(d+1):
            dp[v][i] = t
        if d > 0:
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

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

Submission status: Wrong Answer

Solution code:
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
    print(v, d, idx)
    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')

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from scipy.sparse import lil_matrix, csc_matrix, identity
from scipy.sparse.linalg import inv
import numpy as np
import sys

def query(mat, v, d, c, color):
    # acc1 = acc2 = identity(n, format='csc')
    # for i in range(d):
    #     acc1 = acc1 * mat
    #     acc2 = acc2 + acc1

    E = identity(n, format='csc')
    acc2 = inv(E - mat) * (E - mat**(d+1))
    
    vec = acc2.getcol(v-1)
    mask = vec.sign()
    color = color - color.multiply(mask)
    color = color + c*mask
    return color

data = map(int, sys.stdin.read().split())

n = next(data)
m = next(data)
mat = lil_matrix((n, n))

for i in range(m):
    a = next(data)
    b = next(data)
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsc()

q = next(data)
color = csc_matrix([[0] for i in range(n)])

for i in range(q):
    v = next(data)
    d = next(data)
    c = next(data)
    color = query(mat, v, d, c, color)

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

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(d):
        pass
        # acc1 *= mat
    #     acc2 += acc1

#    vec = acc2.getrow(v-1)
#    mask = vec.sign()
#    color -= color.multiply(mask)
#    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]
    color = query(mat, v, d, c, color)

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

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    # for i in range(1, d+1):
    #     acc1 *= mat
    #     acc2 += acc1

#    vec = acc2.getrow(v-1)
#    mask = vec.sign()
#    color -= color.multiply(mask)
#    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]
    color = query(mat, v, d, c, color)

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

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

for i in range(q):
    v,d,c = [int(x) for x in input().split()]

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

for i in range(m):
    a, b = [int(x) for x in input().split()]
    mat[a-1, b-1] = 1
    mat[b-1, a-1] = 1
mat = mat.tocsr()

q = int(input())
color = sp.csr_matrix([[0 for i in range(n)]])

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp
import numpy as np

def query(mat, v, d, c, color):
    acc1 = acc2 = sp.identity(n, format='csr')

    for i in range(1, d+1):
        acc1 *= mat
        acc2 += acc1

    vec = acc2.getrow(v-1)
    mask = vec.sign()
    color -= color.multiply(mask)
    color += c*mask
    return color

n, m = [int(x) for x in input().split()]
mat = sp.lil_matrix((n, n))

Submission status: Wrong Answer

Solution code:
import scipy.sparse as sp

Submission status: Wrong Answer

Solution code:
import copy
temp=input().split()
N=int(temp[0])
M=int(temp[1])

ab=[[int(j)-1 for j in input().split()] for i in range(M)]
Q=int(input())
vdc=[[int(j)-1 for j in input().split()] for i in range(Q)]

#color=[-1 for i in range(N)]
chain=[[] for i in range(N)]
for i in range(M):
	chain[ab[i][0]]+=[ab[i][1]]
	chain[ab[i][1]]+=[ab[i][0]]
for i in range(N):
	chain[i]+=[i]

INF=-1000
dp=[[INF for j in range(11)] for i in range(N)]

for i in range(Q):
	dp[vdc[i][0]][vdc[i][1]+1]=i
print(chain)
print(vdc)
print(dp)
for i in range(9,-1,-1):
	for j in range(N):
		tempMax=INF
		for k in chain[j]:
			if tempMax<dp[k][i+1]:
				tempMax=dp[k][i+1]
		if tempMax<dp[k][i]:
			tempMax=dp[k][i]
		dp[j][i]=tempMax
#	for i in range(N)
	
print(dp)
for i in range(N):
	tempMax=max(dp[i])
	if tempMax==INF:
		print(0)
	else:
		print(vdc[tempMax][2]+1)

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
        self.opid = -1
    def add(self, new_neighbor):
        self.neighbor.append(new_neighbor)
    def draw(self, p, d, color, opid):
        if d < 0:
            return
        if self.opid == opid:
            return
        else:
            self.opid = opid
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        for n in self.neighbor:
            if p is n:
                continue
            n.draw(self, d-1, color, opid)

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()
super = node()
for i, op in enumerate(operation):
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(super, op[1],op[2], i)

for n in nodes:
    print(n.color)

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
        self.opid = -1
    def add(self, new_neighbor):
        self.neighbor.append(new_neighbor)
    def draw(self, p, d, color, opid):
        if d < 0:
            return
        if self.opid == opid:
            return
        else:
            self.opid = opid
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        for n in self.neighbor:
            if p is n:
                continue
            n.draw(self, d-1, color, opid)

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()
super = node()
for i, op in enumerate(operation):
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(super, op[1],op[2], i)

for n in nodes:
    print(n.color)

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, p, d, color):
        if d < 0:
            return
        if self.color == 0:
            #print("node[{}] <- {}".format(self.id, color))
            self.color = color
        elif self.color == color:
            return
        for n in self.neighbor:
            if p is n:
                continue
            n.draw(self, 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()
super = node()
for op in operation:
    #print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(super, op[1],op[2])

for n in nodes:
    print(n.color)

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("node[{}] <- {}".format(self.id, color))
            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:
    print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(op[1],op[2])

for n in nodes:
    print(n.color)

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("node[{}] <- {}".format(self.id, color))
            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:
    print("op: v={}, c={}, d={}".format(op[0], op[1], op[2]))
    nodes[op[0]-1].draw(op[1],op[2])

for n in nodes:
    print(n.color)