Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, M = map(int, input().split())
Bridge= [[int(i) for i in input().split()] for _ in range(M)]
Parent = [int(i) for i in range(N)]
Rank = [1] * N
 
def find(x):
    if x == Parent[x]: return x
    else:
        Parent[x] = y = find(Parent[x])
        return y
 
def unite(x, y, Total):
    rx, ry = find(x), find(y)
    if rx == ry: return Total
    else:
      Total -= Rank[rx] * Rank[ry]
      if rx > ry:
        Parent[rx] = ry
        Rank[ry] += Rank[rx]
      else:
        Parent[ry] = rx
        Rank[rx] += Rank[ry]
      return Total
 
Total = N * (N - 1) // 2
Ans = str(Total)
for i in reversed(range(1, M)):
    A, B = Bridge[i]
    A -= 1
    B -= 1
    Total = unite(A, B, Total)
    Ans = str(Total) + "\n" + Ans  
 
print(Ans)

### FIXED CODE ###

N, M = map(int, input().split())
Bridge= [[int(i) for i in input().split()] for _ in range(M)]
Parent = [int(i) for i in range(N)]
Rank = [1] * N
 
def find(x):
    if x == Parent[x]: return x
    else:
        Parent[x] = y = find(Parent[x])
        return y
 
def unite(x, y, Total):
    rx, ry = find(x), find(y)
    if rx == ry: return Total
    else:
      Total -= Rank[rx] * Rank[ry]
      if Rank[rx] < Rank[ry]:
        Parent[rx] = ry
        Rank[ry] += Rank[rx]
      else:
        Parent[ry] = rx
        Rank[rx] += Rank[ry]
      return Total
 
Total = N * (N - 1) // 2
Ans = [Total] * M
for i in reversed(range(1, M)):
    A, B = Bridge[i]
    Total = unite(A-1, B-1, Total)
    Ans[i-1] = Total  
 
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

def dijkstra(s,n,w,cost, pre):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    for i in range(len(pre)):
        d[i] = pre[i]
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(len(pre), n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

n, a, b = map(int, input().split())

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    # x,y,z = map(int,input().split())
    # cost[x][y] = z
    # cost[y][x] = z
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[a-1][b-1] = 1
cost[b-1][a-1] = 1


ANS = []
for i in range(n):
    pre = []
    for j in range(i):
        pre.append(ANS[j][i])

    ANS.append(dijkstra(i, n, n, cost, pre))
# print(ANS)
from functools import reduce
A = reduce(lambda x,y: x+y,ANS)

import collections

c = collections.Counter(A)

for i in range(1, n):
    print(c[i]//2)


### FIXED CODE ###

a, b, c = map(int, input().split())

b = b - 1
c = c - 1
A = []

for i in range(a):
    for j in range(i+1, a):
        A.append(min(abs(i - b) + 1 + abs(j - c), abs(j - i)))
import collections
C = collections.Counter(A)

for i in range(1, a):
    print(C[i])
### BUGGY CODE ###

class ABSsegtree: # 必要な配列の長さN,単位元ie,関数(2項演算)func,を渡す    
    def __init__(self,N,ie,func):
        self.func=func
        self.getLEN=1 # Length of list
        while self.getLEN<N:
            self.getLEN*=2
        self.getsize=self.getLEN*2 # =len(ST)
        self.getLIN=self.getsize-self.getLEN # internal nodes without ST[0]
        self.ST=[ie]*self.getsize

    def update(self,i,x): # i(0-index)にxをいれる
        i+=self.getLIN
        self.ST[i]=x
        while i>1:
            i//=2
            self.ST[i]=self.func(self.ST[2*i],self.ST[2*i+1])
    
    def get_interval(self,a,b): # [a,b)での最小値を求めたい
        a+=self.getLIN
        b+=self.getLIN
        ret=self.func(self.ST[a],self.ST[b-1])
        while a+1<b: # 階層ごとに見る
            if a%2==1:
                ret=self.func(self.ST[a],ret)
                a+=1
            a//=2
            if b%2==1:
                ret=self.func(self.ST[b-1],ret)
            b//=2
        if a==b:
            pass
        else:
            ret=self.func(ret,self.ST[a])
        return ret
      
import fractions

N=int(input())
A=[int(a) for a in input().split()]

ins=ABSsegtree(N,0,fractions.gcd)
for i,a in enumerate(A):
  ins.update(i,a)
ans=0
for i,a in enumerate(A):
  ins.update(i,0)
  ans=max(ans,ins.get_interval(0,N))
  ins.update(i,a)
print(ans)
  

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]

l = [0]
r = [0]
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
    r.append(gcd(r[i],a[-1-i]))

m = 0
for i in range(n):
    m = max(m,gcd(l[i],r[-i-1]))

print(m)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        for k in range(n//b+1):
            if r*i + j*g + b*k == n:
                ans += 1

print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = [0 for i in range(n+1)]
ans[0] = 1
for i in [r,g,b]:
    for j in range(n+1-i):
        ans[j+i] += ans[j]

print(ans[n])
### BUGGY CODE ###

from collections import deque
 
def dfs(friends, x):
    visited = [0] * n
    d = deque([x])
    ans = []
    while d:
        num = d.pop()
        
        #print(num, '->',end='')
        
        if visited[num] == 1:
            #print('x')
            continue
        
        visited[num] = 1
        ans.append(num)
        
        for a in friends[num]:
            d.append(a)
        
    #print()
    return ans
        
if __name__ == "__main__":    
    n, m, k = map(int, input().split())
     
    friends = [[] for _ in range(n)]
    for i in range(m):
        x, y = map(lambda z: int(z) - 1, input().split())
        friends[x].append(y)
        friends[y].append(x)
         
    blocks = [[] for _ in range(n)]
    for i in range(k):
        x, y = map(lambda z: int(z) - 1, input().split())
        blocks[x].append(y)
        blocks[y].append(x)
        
    #print(friends)
    #print(blocks)
    
    label = [-1] * n
    vec_len = []
    num = 0
    for i in range(n):
        if label[i] != -1:
            continue
        
        vec = dfs(friends, i)
        vec_len.append(len(vec))
        for j in vec:
            label[j] = num
        
        num += 1
        
    for i in range(n):
        ans = 0
        ans += vec_len[label[i]]
        ans -= len(friends[i])
        
        for b in blocks[i]:
            if label[i] == label[b]:
                ans -= 1
            
        ans -= 1
        
        print(ans, end=' ')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n 
        self.size = [1] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] = self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
                
n, m, k = map(int, input().split())
friends = [[] for _ in range(n)]
blocks = [[] for _ in range(n)]

for i in range(m):
    x, y = map(lambda x: int(x) - 1, input().split())
    friends[x].append(y)
    friends[y].append(x)

for i in range(k):
    x, y = map(lambda x: int(x) - 1, input().split())
    blocks[x].append(y)
    blocks[y].append(x)

uf = UnionFind(n)
for i in range(n):
    for f in friends[i]:
        uf.union(i, f)

# 自分を除くUnionFind木の大きさ
ans = [uf.size[uf.find(i)] - 1 for i in range(n)]
# 直接的な友達を引く
for i in range(n):
    ans[i] -= len(friends[i])

for i in range(n):
    for b in blocks[i]:
        if uf.same(i, b):
            ans[i] -= 1

print(*ans)
### BUGGY CODE ###

import sys
import copy
def input():
    return sys.stdin.readline()
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))

for i in range(n):
  tmp = copy.copy(a)
  tmp.pop(i)
  print(max(tmp))

### FIXED CODE ###

import sys
import copy
def input():
    return sys.stdin.readline()
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))


A = max(a)
if a.count(A) >= 2:
  for i in range(n):
    print(A)
else:
  index = a.index(A)
  for i in range(index):
    print(A)
  print(sorted(a)[-2])
  for i in range(index+1,n):
    print(A)
### BUGGY CODE ###

cur = []

def recur(n):
    if n > 10 ** 18:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))

### FIXED CODE ###

cur = []

def recur(n):
    if n > 10 ** 10:
        return
    cur.append(n)
    for i in range(10):
        if abs(n % 10 - i) <= 1:
            recur(10 * n + i)

for i in range(1, 10):
    recur(i)
cur.sort()
n = int(input())
print((cur[n - 1]))
### BUGGY CODE ###

def anagram( w1, w2 ):
    letters = [0]*256
    for c in w1:
        letters[ord(c)] += 1
    
    for i in range(len(w2)):
        letters[ord(w2[i])] -= 1
        if letters[ord(w2[i])] < 0:
            return False
    
    return True


n = int( input() )
s = []
for i in range(n):
    s.append(input())

cnt = 0
for i in range(n):
    for j in range(i+1,n):
        if anagram( s[i], s[j] ):
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int( input() )
s = []
for i in range(n):
    s.append("".join(sorted(list(input()))))

cnt = 0
words = Counter(s)
for i in words.values():
    cnt += i*(i-1)//2

print(cnt)
### BUGGY CODE ###

X = int(input())

for a in range(0 , 10**3 , 1):
  for b in range(0 , X+1 , 1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue
      
for a in range(0 , 10**3 , 1):
  for b in range(0 , -X , -1):
    if(a**5-b**5==X):
      print(a, b)
      exit()
    else:
      continue

### FIXED CODE ###

X = int(input())
 
for a in range(-119 , 120 , 1):
  A = a**5
  for b in range(-119 , 120 , 1):
    B = b**5
    if(A-B==X):
      print(a, b)
      exit()
    else:
      continue
### BUGGY CODE ###

import numpy as np

n = int(input())
s = input()

dp = np.zeros((30009, 4, 1009), dtype=np.bool)

dp[0][0][0] = True

for i in range(n):  # i: どの桁にいるか
    for j in range(4):  # j: 何文字残すか
        for k in range(1000):  # k: 残すと決まった数字
            if dp[i][j][k] == False:
                continue
            dp[i + 1][j][k] = True
            if j <= 2:
                dp[i + 1][j + 1][k * 10 + int(s[i])] = True
cnt = 0
for i in range(1000):
    if dp[n][3][i]:
        cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    t = "{:0=3}".format(i)
    p = 0
    for j in range(N):
        if S[j] == t[p]:
            p += 1
        if p == 3:
            break
    if p == 3:
        ans += 1

print(ans)
### BUGGY CODE ###

n,k=list(map(int,input().split()))
candles=list(map(int,input().split()))
rows=[]
minimum=[]
for i in range(n-k+1):
        new=candles[i:i+k]
        l_r=abs(new[0])+abs(new[-1]-new[0])
        r_l=abs(new[-1])+abs(new[-1]-new[0])
        minimum.append(min(l_r,r_l))

print(min(minimum))

### FIXED CODE ###

N, K, *x = map(int, open(0).read().split())
ans = 1e9
for i in range(N - K + 1):
    l = x[i]
    r = x[i + K - 1]
    ans = min(ans, abs(l) + (r - l), abs(r) + (r - l))
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(1, n):
    for j in range(i+a[i-1], n+1):
        if j-i == a[i-1]+a[j-1]:
            c += 1
            
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = {}
r = {}
for i in range(n):
    if i+1+a[i] in l:
        l[i+1+a[i]] += 1
    else:
        l[i+1+a[i]] = 1
        
    if i+1-a[i] in r:
        r[i+1-a[i]] += 1
    else:
        r[i+1-a[i]] = 1

c = 0
for i in range(2, n):
    if i in l and i in r:
        c += l[i]*r[i]
print(c)
### BUGGY CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))
ans = []

sum = 0
for i in range(1, n + 1):
    tmp = numlist.count(i)
    sum += int(tmp * (tmp - 1) / 2)

for i in numlist:
    print(sum - numlist.count(i) + 1)


### FIXED CODE ###

n = int(input())
numlist = list(map(int, input().split(" ")))

import collections

numcount=collections.Counter(numlist)


sum = 0
for i in numcount.values():
    sum += int(i * (i - 1) / 2)

for i in numlist:
    print(sum - numcount[i] + 1)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
As.insert(0, 0)
Ans = [0 for _ in range(N + 1)]
Ans[N] = As[N]
for i in range(N - 1, 0, -1):
    k = 2
    s = 0
    while True:
        p = k * i
        if p > N:
            break
        s += Ans[p]
        k += 1
    Ans[i] = 0 if s % 2 == As[i] else 1
M = sum(Ans)
print(M)
if M > 0:
    bs = ""
    for i in range(1, N + 1):
        if Ans[i] != 0:
            bs += "%d " % i
    bs = bs.rstrip(" ")
    print(bs)

### FIXED CODE ###

N = int(input())
As = list(map(bool, map(int, input().split())))
As.insert(0, False)
Ans = [False for _ in range(N + 1)]
Ans[N] = As[N]
for i in range(N - 1, 0, -1):
    p = i * 2
    s = False
    while p <= N:
        s ^= Ans[p]
        p += i
    Ans[i] = s ^ As[i]
M = sum(Ans)
print(M)
if M > 0:
    c = True
    for i in range(1, N + 1):
        if Ans[i]:
            if c:
                c = False
            else:
                print(" ", end="")
            print(i, end="")
    print("")
### BUGGY CODE ###

N, K = map(int, input().split())

LR = [map(int, input().split()) for _ in range(K)]
MOD = 998244353
dic = []
for l, r in LR:
    tmp = [x for x in range(l, r+1)]
    dic += tmp
dic.sort()
dp = [0]*(N+1)
dp[1] = 1
n = len(dic)
cnt = 0
t = []
for i in range(2, N+1):
    tmp = i-1
    while cnt < n:
        if dic[cnt] <= tmp:
            t.append(dic[cnt])
            cnt += 1
        else:
            break
    for s in t:
        dp[i] += dp[i-s]
        dp[i] %= MOD
print(dp[-1])


### FIXED CODE ###

def main():
    N, K = map(int, input().split())

    LR = [list(map(int, input().split())) for _ in range(K)]
    MOD = 998244353

    dp = [0]*(N+1)
    S = [0]*(N+1)
    dp[1] = 1
    S[1] = 1

    for i in range(2, N+1):
        for l, r in LR:
            if i-l < 0:
                continue
            else:
                dp[i] += S[i-l] - S[max(i-r-1, 0)]
        dp[i] %= MOD
        S[i] = S[i-1] + dp[i]
    print(dp[-1]%MOD)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C)]for _ in range(R)]

    for i in range(R):
        for j in range(C):
            v = items[i][j]

            #上から入るパターン
            dp[i][j][0] = max(dp[i-1][j])
            if v:
                dp[i][j][1] = dp[i][j][0]+v
            
            #左から入ってくるパターン
            if j > 0:
                for k in range(4):
                    #このマスのアイテムをとらないパターン
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                    if v and k>0:
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v)

    print(max(dp[-1][-1]))
main()

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()
### BUGGY CODE ###

s = list(input())
a_index = [i for i, x in enumerate(s) if x == 'A']
z_index = [i for i, x in enumerate(s) if x == 'Z']
distance = []

for i in a_index:
    for j in z_index:
        dis = abs(i-j)
        distance.append(dis)

print(max(distance)+1)

### FIXED CODE ###

s = input()

print(s.rfind('Z') - s.find('A') + 1)
### BUGGY CODE ###

import collections
n = input()
a = list(input().split())

# 各数値の重複数辞書
counter = collections.Counter(a)

# 組み合わせ数
def combi(num):
    if num < 2:
        pair = 0
    else:
        pair = int(num * (num-1) / 2)
    return pair

# 各数字を抽出しない時と抽出した時の組み合わせ数
fulldic = dict()
reducedic = dict()
for k, v in counter.items():
    fulldic[k] = combi(v)
    reducedic[k] = combi(v-1)
    
for el in a:
    print(sum(fulldic.values()) - (fulldic[el] - reducedic[el]))


### FIXED CODE ###

import collections
n = input()
a = list(input().split())

# 各数値の重複数辞書
counter = collections.Counter(a)

# 組み合わせ数
def combi(num):
    if num < 2:
        pair = 0
    else:
        pair = int(num * (num-1) / 2)
    return pair


total = sum([combi(v) for v in counter.values()])
for el in a:
    print(total - (counter[el] - 1))
### BUGGY CODE ###

import math
A,B,N= map(int,input().split())
x=[]
AB=A/B
for i in range(1,N+1):
    x.append(math.floor(AB*i)-A*(i//B))
x.sort()
print(x.pop(N-1))

### FIXED CODE ###

import math
A,B,N= map(int,input().split())
x=[]
AB=A/B
if B==1:
    print("0")
elif N<B:
    #x.append(math.floor(AB*N-1)-A*(N//B)
    print(math.floor(AB*N))
else:
    x=[math.floor(AB*N)-A*(N//B)]
    for i in range(N//B):
        x.append(math.floor(AB*((i+1)*B-1))-i)
    print(max(x))
### BUGGY CODE ###

n, k = map(int, input().split())
st = input()
num = 0
state = 0
cumsum = []
for s in st:
    if int(s) == state:
        num += 1
    else:
        cumsum.append(num)
        state = [1, 0][state]
        num = 1
cumsum.append(num)
cumsum = [0] + cumsum # odd 
if len(cumsum) % 2:
    cumsum += [0]
l = min(k * 2, len(cumsum) - 1 - (len(cumsum) % 2))
print(max([sum(cumsum[n: n + l + 1])
           for n in range(0, len(cumsum) - l + 1, 2)]))

### FIXED CODE ###

n, k = map(int, input().split())
st = input()
num = 0
state = 0
cumsum = []
for s in st:
    if int(s) == state:
        num += 1
    else:
        cumsum.append(num)
        state = [1, 0][state]
        num = 1
cumsum.append(num)
cumsum = [0] + cumsum + [0, 0]
if (len(cumsum) % 2) == 0:
    cumsum += [0]
l = min(k * 2, len(cumsum) - 1 - (len(cumsum) % 2))
sumsum = sum(cumsum[:l + 1])
max_sum = sumsum
start_idx = 0
end_idx = l + 1
if len(cumsum) - l + 1 > 3:
    for n in range(2, len(cumsum) - l + 1, 2):
        sumsum = (
            sumsum - sum(cumsum[start_idx: start_idx + 2])
            + sum(cumsum[end_idx: end_idx + 2])
        )
        start_idx += 2
        end_idx += 2
        max_sum = max(max_sum, sumsum)

print(max_sum)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
sum = 0
for i in range(n):
  for j in range(i):
    sum += x[i]*x[j]
print(sum % (pow(10,9)+7))

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
s = (sum(lst)**2 - sum([z**2 for z in lst]))//2
print(s % (pow(10,9)+7))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
    ac = a.copy()
    del ac[i]
    print(max(ac))


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
s, f = sorted(a)[-2:]

for ai in a:
    print(f if ai != f else s)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = [int(a) for a in input().split()]

if A[0] != 0:
    print(0)
    exit()
if A.count(0) != 1:
    print(0)
    exit()

k = max(A)

c = 1
R = [1]
result = 1


for i in range(k):
    R.append(A.count(i + 1))
    c += 1

for j in range(k):
    result *= R[j] ** R[j + 1]
    result %= 998244353

    if result == 0:
        print(0)
        exit()

print(result)








### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
k = max(A)

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

if A[0] != 0 or R[0] != 1:
    print(0)
    exit()

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

    if result == 0:
        print(0)
        exit()

print(result % 998244353)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n):
    cnt = 0
    for j in range(i):
        if p[i] <= p[j]:
            cnt += 1
            if cnt == i:
                ans += 1
print(ans + 1)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
minp = 2*10**5
ans = 0
for i in range(n):
    if minp >= p[i]:
        minp = p[i]
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

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]

def bfs(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if used[node][dis] == True:
            continue
            
        if dis < 0:
            continue
            
        used[node][dis] = True
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

for x in color:
    print(x)


### FIXED 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]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)