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

import sys
input = sys.stdin.readline

def main():
    n,m = map(int,input().split())
    li = [list(map(int,input().split())) for _ in range(m)]

    roots = [[] for _ in range(n)]
    for x,y,z in li:
        roots[x-1].append(y-1)
        roots[y-1].append(x-1)

    ans = 0
    count = 0
    stack = []
    group = [-1] * n

    while count < n:
        a = group.index(-1)
        stack.append(a)
        group[a] = ans
        count += 1
        while stack:
            label = stack.pop(-1)
            for i in roots[label]:
                if group[i] == -1:
                    group[i] = ans
                    stack.append(i)
                    count += 1
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n,m = map(int,input().split())
    li = [list(map(int,input().split())) for _ in range(m)]

    roots = [[] for _ in range(n)]
    for x,y,z in li:
        roots[x-1].append(y-1)
        roots[y-1].append(x-1)

    ans = 0
    count = 0
    group = [-1] * n

    for i in range(n):
        if group[i] == -1:
            stack = [i]
            while stack:
                label = stack.pop(-1)
                for j in roots[label]:
                    if group[j] == -1:
                        group[j] = ans
                        stack.append(j)
            ans += 1

    print(ans)

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

k,s= map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                cnt+=1
print(cnt)

    

### FIXED CODE ###

k,s= map(int,input().split())
cnt=0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-x-y <= k:
            cnt+=1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = [input() for _ in range(n)]
sa = set(a)
res = 0
for i in sa:
    if a.count(i)%2!=0:
        res+=1

print(res)


### FIXED CODE ###

N = int(input())

p = set()
for i in range(N):
    A = input()
    p ^= {A}

print(len(p))
### BUGGY CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki

for i in range(K):
  data = [0]*N
  ruiseki = [0]*N
  for i in range(N):
    first = i-List[i]
    last = i+List[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < N:
      data[last+1] +=-1
  List[0] = data[0]
  for i in range(N-1):
    List[i+1] = List[i] + data[i+1]
  if List.count(N) == N:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)

for k in range(600000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    #print(index)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)
ans = -2
for k in range(10000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    #print(index)

if ans == -2:
    print(N*(N-1)//2)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())

for i in range(q):
  a, b, c = input().split()
  if int(a)==1:
    b = int(b)
    s[b-1] = c
  elif int(a)==2:
    b = int(b)
    c = int(c)
    tmp_s = s[b-1:c]
    print(len(set(tmp_s)))


### FIXED CODE ###

n = int(input())
S = list(input())
q = int(input())

import sys
input = sys.stdin.readline

alp = "abcdefghijklmnopqrstuvwxyz"
appr = {a:[] for a in alp}

import bisect

for i, a in enumerate(S):
  appr[a].append(i+1)
#print(appr)
for i in range(q):
  inputs = input().split()
  if inputs[0] == '1':
    c = int(inputs[1])
    a = inputs[2]
    if S[c-1]==a:
      continue
    else:
      old = S[c-1]
      S[c-1] = a
      del_idx = bisect.bisect_left(appr[old], c)
      del appr[old][del_idx]
      in_idx = bisect.bisect_left(appr[a], c)
      appr[a].insert(in_idx, c)
  else:
    l, r = map(int, inputs[1:])
    res = 0
    for a in appr:
      l_idx = bisect.bisect_left(appr[a], l)
      if l_idx<len(appr[a]):
        if appr[a][l_idx]<=r:
          res += 1
    print(res)
    
#print(appr)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    G = [0] * m
    ans = 0
    for i in range(m):
        G[i] = list(map(int, input().split()))
    for i in range(1, n+1):
        f = 0
        for j in range(m):
            if i < G[j][0] or G[j][1] < i:
                f = 0
                break
            else:
                f = 1
        if f == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    l = []
    r = []
    ans = 0
    for i in range(m):
        a, b = map(int, input().split())
        l.append(a)
        r.append(b)
    ml = max(l)
    mr = min(r)
    for i in range(1, n+1):
        if i >= ml and i <= mr:
            ans += 1
    print(ans)


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

#C
import numpy as np

N = int(input())
P = np.array(list(map(int, input().split())))
ans = 0

for i in range(N):
    min_to_i = np.min(P[:i+1])
    if min_to_i >= P[i]:
        ans += 1
        
print(ans)

### FIXED CODE ###

#C
N = int(input())
P = list(map(int, input().split()))
ans = 0
min_num = 10**6

for i in range(N):
    min_num = min(min_num, P[i])
    if min_num >= P[i]:
        ans += 1
        
print(ans)
### BUGGY CODE ###

input = raw_input
N,K = map(int, input().strip().split(" "))
H = list(map(int, input().strip().split(" ")))

dp = [[0]*K for i in range(N)]

for i in range(1,N):
    for j in range(1, K+1):
        jj = max(0, i-j)
        dp[i][j-1] = min(dp[jj]) + abs(H[i]-H[jj])
print(min(dp[N-1]))


### FIXED CODE ###

input = raw_input
N,K = map(int, input().strip().split(" "))
H = list(map(int, input().strip().split(" ")))

dp = [[0]*K for i in range(N)]

for i in range(1,N):
    for j in range(1, K+1):
        jj = max(0, i-j)
        dp[i][j-1] = dp[jj][0] + abs(H[i]-H[jj])
    dp[i][0] = min(dp[i])
print(min(dp[N-1]))
### BUGGY CODE ###

#親ー子の順に書かれてるか否かめっちゃ重要なのになあ
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for i in range(n-1):
  a,b = (map(int,input().split()))
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
mom = [-1 for _ in range(n)]
mom[0] = 'luca'
child = [[] for _ in range(n)]
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if mom[y] == -1:
        now.append(y)
        mom[y] = x
        child[x].append(y)
#print(peer)
#print(mom)
#print(child)
pq = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  p -= 1
  pq[p] += x
now = [0]
ans = pq
while now != []:
  last = now
  now = []
  for x in last:
    for y in child[x]:
      ans[y] += ans[x]
    now += child[x]
print(' '.join(list(map(str,ans))))

### FIXED CODE ###

#親ー子の順に書かれてるか否かめっちゃ重要なのになあ
n,q = map(int,input().split())

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

pq = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  p -= 1
  pq[p] += x

now = [0]
ans = pq
now = [0]
mom = [0 for _ in range(n)]
mom[0] = 1
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if mom[y] == 0:
        now.append(y)
        mom[y] = 1
        ans[y] += ans[x]

print(' '.join(list(map(str,ans))))
### BUGGY CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0

for i in range(2**len(A)):  # 空集合を除く場合はrange(1, 2**len(list1))
    list2 = []
    for j in range(len(A)):
        if (i >> j) &1 == 1:
            list2.append(A[j])
    if len(list2) == 2:
        ans += list2[0]*list2[1]
#        print(ans)
#    print(list2)
    ans = ans%mod
print(ans)


### FIXED CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
v = sum(A)
for i in range(N-1):
    v -= A[i]
    ans += A[i]*v
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = input()
RL = []
GL = []
BL = []
for i in range(1, n + 1):
    word = s[i - 1]
    if word == "R":
        RL.append(i)
    elif word == "G":
        GL.append(i)
    else:
        BL.append(i)
ans = 0
for r in RL:
    for g in GL:
        for b in BL:
            delta1 = abs(r - g)
            delta2 = abs(g - b)
            delta3 = abs(b - r)
            if delta1 == delta2:
                continue
            if delta2 == delta3:
                continue
            if delta3 == delta1:
                continue
            ans += 1
print(ans)


### FIXED CODE ###

# from bisect import bisect_left

n = int(input())
s = input()
RL = []
GL = []
BL = []
for i in range(1, n + 1):
    word = s[i - 1]
    if word == "R":
        RL.append(i)
    elif word == "G":
        GL.append(i)
    else:
        BL.append(i)
nagasa_r = len(RL)
nagasa_g = len(GL)
nagasa_b = len(BL)
SBL = set(BL)
ans = 0
if nagasa_b == 0 or nagasa_g == 0 or nagasa_r == 0:
    ans = 0
else:
    out_count = 0
    for r in RL:
        for g in GL:
            bigger = max(r, g)
            smaller = min(r, g)
            delta = bigger - smaller
            if (r + g) % 2 == 0:
                outnumber = [bigger + delta, smaller - delta, (r + g) // 2]
            else:
                outnumber = [bigger + delta, smaller - delta]
            for num in outnumber:
                if num in SBL:
                    out_count += 1
            ans += nagasa_b
    ans -= out_count
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
if a[0] >= 0:
    sym = True
else:
    sym = False
for i in range(1, n):
    if sym:
        while sum(a[0:i+1]) >= 0:
            a[i] -= 1
            count += 1
        sym = False
    else:
        while sum(a[0:i+1]) <= 0:
            a[i] += 1
            count += 1
        sym = True
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt1 = 0
cnt2 = 0
total = 0
for i in range(len(a)):
    total += a[i]
    if i % 2 == 0:
        if total >= 0:
            cnt1 += 1 + total
            total -= 1 + total
    else:
        if total <= 0:
            cnt1 += 1 - total
            total += 1 - total
total = 0
for i in range(len(a)):
    total += a[i]
    if i % 2 != 0:
        if total >= 0:
            cnt2 += 1 + total
            total -= 1 + total
    else:
        if total <= 0:
            cnt2 += 1 - total
            total += 1 - total
print(min(cnt1, cnt2))
### BUGGY CODE ###

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

if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
    if result>10**18:
        result=-1
    print(result)

### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
### BUGGY CODE ###

from itertools import product
from collections import deque

def state_brute_force(state, count):
    state_list = [state for _ in range(count)]
    for s in product(*state_list):
        yield s


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

ans = 0

pop_l = deque.popleft
pop_r = deque.pop
add_l = deque.appendleft
add_r = deque.append

stop_condition = sum([item for item in D if item > 0])
if stop_condition > 0:
    for cmb in state_brute_force([pop_l, pop_r, add_l, add_r], K):
        q = deque(D)
        now = []
        value = 0
        for operation in cmb:
            if operation == add_l or operation == add_r:
                if len(now) == 0:
                    break
                item = min(now)
                now.remove(item)
                operation(q, item)
            if operation == pop_l or operation == pop_r:
                if len(q) == 0:
                    break
                now.append(operation(q))
        value = max(value, sum(now))
        ans = max(ans, value)
        if ans == stop_condition:
            break

print(ans)




### FIXED CODE ###

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

ans = 0

for left in range(K + 1):
    for right in range(K - left + 1):
        if left + right > N:
            break
        items = list(D[0:left])
        items.extend(D[::-1][0:right])
        dis = K - (left + right)
        i = 0
        items = sorted(items, reverse=True)
        while True:
            ans = max(ans, sum(items))
            if i < dis and len(items) > 0:
                i += 1
                items.pop()
                continue
            else:
                break

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

n = int(input())
s = list(input())
ans = len(s)
if min(s.count("#"),s.count("."))==0:
     ans = 0
else:
     for i in range(n):
          ans = min(ans,s[:i].count("#")+s[i:].count("."))

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
anslist = [s.count(".")]
for i in range(0,n):
     ans = anslist[-1]
     if s[i] == "#":
          ans += 1
     else:
          ans -= 1
     anslist.append(ans)
print(min(anslist))
### BUGGY CODE ###

A, B, K = map(int, input().split())

for _ in range(K):
	if A >= 1:
		A -= 1
	elif B >= 1:
		B-= 1

print(A, B)		

### FIXED CODE ###

A, B, K = map(int, input().split())

if A >= K:
	print(A - K, B)
else:
	print(0, max(0, B - (K - A)))
### BUGGY CODE ###

import math

N=int(input())
A = list(map(int,input().split()))
cnt=[0]*(N+1)
for i in range(1,N+1):
	cnt[i-1]=(A.count(i))
ans=0
for i in range(1,N+1):
	if cnt[i-1]==0:
		ans+=0
	else:
		ans+=cnt[i-1]*(cnt[i-1]-1)//2

for i in range(0,N):
	point=A[i]
	deff=(cnt[point-1]*(cnt[point-1]-1))//2-((cnt[point-1]-1)*(cnt[point-1]-2))//2
	print(ans-deff)

### FIXED CODE ###

import math

N=int(input())
A = list(map(int,input().split()))
cnt=[0]*(N+1)
for i in range(0,N):
	cnt[A[i]-1]+=1
ans=0
for i in range(0,N+1):
	if cnt[i]==0:
		ans+=0
	else:
		ans+=cnt[i]*(cnt[i]-1)//2

for i in range(0,N):
	point=A[i]
	deff=(cnt[point-1]*(cnt[point-1]-1))//2-((cnt[point-1]-1)*(cnt[point-1]-2))//2
	print(ans-deff)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
x=list(range(n))
x[n-1]=0
#print(x)
i=n-2
j=1
y=[]
while i!=-1:
    j=1
    while j!=k+1 and j+i!=n:
        y.append(abs(a[i]-a[j+i])+x[j+i])
        #print(a[i])
        #print(a[j+i])
        j+=1

    #print(y)
    x[i]=min(y)
    #print(x)
    y=[]

    i-=1
print(x[0])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
x=list(range(n))
x[n-1]=0
#print(x)
i=n-2
j=1
y=[]
while i!=-1:
    j=1
    while j!=k+1 and j+i!=n:
        y.append(abs(a[i]-a[j+i])+x[j+i])
        #print(a[i])
        #print(a[j+i])
        j+=1

    #print(y)
    x[i]=min(y)
    #print(x)
    y=[]

    i-=1
print(x[0])
### BUGGY CODE ###

n,k = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [float('inf')]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        m = i + j
        if m < n:
            dp[m] = min(dp[m],dp[i] + abs(h[i]-h[m]))

print(dp[n-1])
    

### FIXED CODE ###

n,k = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [float('inf')]*n
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        m = i + j
        if m < n:
            dp[m] = min(dp[m],dp[i] + abs(h[i]-h[m]))

print(dp[-1])
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
count = 0
alr = []
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#' and (h,w) not in alr:
            que = deque()
            que.append((h,w,True))
            alr.append((h,w))
            alr2 = [(h,w)]
            while que:
                hn,wn,black = que.popleft()
                black = not black
                for i in range(4):
                    if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and (hn+h1[i],wn+w1[i]) not in alr2:
                        if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                            if (hn+h1[i],wn+w1[i]) not in alr:
                                count += 1
                            que.append((hn+h1[i],wn+w1[i],black))
                            alr2.append((hn+h1[i],wn+w1[i]))
                        elif black and S[hn+h1[i]][wn+w1[i]] == '#':

                            que.append((hn+h1[i],wn+w1[i],black))
                            alr2.append((hn+h1[i],wn+w1[i]))
print(count)
                        

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
blacklist = []
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            blacklist.append((h,w))
ans = 0
alr = [[0 for i in range(W)] for j in range(H)]
h1 = [0,0,1,-1]
w1 = [1,-1,0,0]
for h,w in blacklist:
    if alr[h][w] == 0:
        bcount = 1
        wcount = 0
        que = deque()
        que.append((h,w,True))
        alr[h][w] = 1
        while que:
            hn,wn,black = que.popleft()
            black = not black
            for i in range(4):
                if 0 <= hn+h1[i] <= H-1 and 0 <= wn+w1[i] <= W-1 and not alr[hn+h1[i]][wn+w1[i]]:
                    if (not black) and S[hn+h1[i]][wn+w1[i]] == '.':
                        wcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
                    elif black and S[hn+h1[i]][wn+w1[i]] == '#':
                        bcount += 1
                        que.append((hn+h1[i],wn+w1[i],black))
                        alr[hn+h1[i]][wn+w1[i]] = 1
        ans += wcount*bcount
print(ans)
### BUGGY CODE ###

import sys


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
slis = [int(s[-1*i:]) if i != 0 else 0  for i in range(len(s)+1)]
amari = [i % 2019 for i in slis]
sset = set(amari)
ans = 0
for i in sset:
    m = amari.count(i)
    ans += m*(m-1)//2
print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict as de


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

s = ns()
digit = 1
ans = 0
num = 0
amari = de(int)
amari[0] = 1
"""
大筋のやり方は
https://drken1215.hatenablog.com/entry/2020/04/29/171300
を参照。

「この下のfor文について」
1211400を考える。
1万の桁を考えるとき
digit = 10000
digit = 1924 mod 2019
11400 = 10000 + 1400 = 1924 + 1400 = ans mod 2019
つまり、ある桁までの2019のあまりはその一つ下の桁までのあまりと
その桁の数*桁のあまりを足したもののあまりである
"""

for i in s[::-1]:
    num = num + int(i) * digit
    num %= 2019
    digit *= 10
    digit %= 2019
    amari[num] += 1

for j in amari.values():
    ans += j*(j-1)//2

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        link[a[i]-1].append([b[i]-1, cost[i]])
        link[b[i]-1].append([a[i]-1, cost[i]])

    def dfs(v, c, p):
        for nv in link[v]:
            if nv[0] == p:
                continue
            cost[nv[0]] = c + cost[nv[0]]
            dfs(nv[0], cost[nv[0]], v)
        return

    dfs(0, cost[0], -1)

    print(*cost)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p):
    for u in link[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)

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

ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

dfs(0, -1)

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

def solve():
    n = int(input())
    p = [int(x) for x in input().split()]

    ans = 0
    seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
    reserved = [[True for j in range(n)] for i in range(n)]

    vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for i in range(n**2):
        v = p[i]-1
        x, y = v//n, v % n
        reserved[x][y] = False
        ans += seat[x][y]
        q = [(x, y)]
        while q:
            x, y = q.pop()
            for dx, dy in vec:
                x1 = x+dx
                y1 = y+dy
                if 0 <= x1 < n and 0 <= y1 < n and seat[x1][y1] > seat[x][y] + reserved[x][y]:
                    seat[x1][y1] = seat[x][y] + reserved[x][y]
                    q.append((x1, y1))
    print(ans)


solve()


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


print(ans)