Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
#L = [list(map(int,input().split())) for i in range(m)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_members(self, x):  # x が属する集合の要素を返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根をリストで返す
        return [i for i, x in enumerate(self.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

#a = [i+1 for i in range(n)]
d = UnionFind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.unite(a,b)

print(d.group_count()-1)

### FIXED CODE ###

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

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[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 False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
#a = [i+1 for i in range(n)]
d = Unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.union(a-1,b-1)
    
L = []
for i in range(n):
    c = d.find(i)
    L.append(c)
#print(L)
print(len(set(L))-1)
x,y,z = map(int,input().split)
new_list = [z,x,y]
print((" ").join(new_list))

### FIXED CODE ###

x,y,z = input().split(" ")
print(z,x,y)
import bisect
n, m = map(int, input().split())
work = [list(map(int, input().split())) for i in range(n)]
dic = {}
for w in work:
    a, b = w[0], w[1]
    if a not in dic.keys():
        dic[a]=[b]
    else:
        index=bisect.bisect_right(dic[a], b)
        dic[a].insert(index, b)
dic_=sorted(dic.items(), key=lambda x:x[0])
res = 0
while m > 0:
    print(dic_)
    flag=True
    for i in range(len(dic_)):
        if dic_[i][0] >= m:
            flag=False
            if i==0:
                break
            res+=dic_[i][1].pop(-1)
    if flag:
        dic_[-1][1].pop(-1)
    m-=1

### FIXED CODE ###

import heapq
from collections import deque

N, M=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:(x[0], x[1]))
for i in range(N):
  AB[i][1]=-AB[i][1]
d=deque(AB)
ans=0
h=[]
for i in range(M+1):
  if not d and not h:
    break
  while d and d[0][0]<=i:
    heapq.heappush(h, d.popleft()[1])
  if h:
    ans-=heapq.heappop(h)
print(ans)
H,W=map(int,input(),split())
h,w=map(int,input().split())
math=H*W
black=h*w+H*w-h*w
white=math-black
print(white)


### FIXED CODE ###

H,W=map(int,input().split())
h,w=map(int,input().split())
math=H*W
black=h*W+H*w-h*w
white=math-black
print(white)
n=int(input())
N=list(range(1,n+1))
print(sum([gcd2(a,b,c) for a,b,c in [[a, b, c] for a in N for b in N for c in N]]))

### FIXED CODE ###

import math

N = int(input())
 
ans = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        tmp = math.gcd(a, b)
        for c in range(1, N + 1):
            ans += math.gcd(tmp, c)
print(ans)
r,g b = input().split()
if (g*10+b)%4%==0:
    print('YES')
else:
    print('No')
    


### FIXED CODE ###

r,g,b=map(int,input().split())
X = r * 100 + g * 10 + b
if X % 4 == 0:
    print('YES')
else:
    print('NO')
nmax=10**9+1
c=[1]*nmax
a=[]
n=int(input())
for i in range(n):
    ai=int(input())-1
    c[ai]=1-c[ai]
    a.append(ai)
    
icnt=0
for i in range(n):
  if c[a[i]]==0:
      icnt=icnt+1
      
print(icnt)
    

### FIXED CODE ###

dicc=dict()

n=int(input())
for i in range(n):
    ai=input()
    if ai in dicc:
        dicc[ai]=1-dicc[ai]
    else:
        dicc[ai]=1
        
icnt=0    
for i in dicc.values():
    icnt=icnt+i
      
print(icnt)
k = int(input())


if k % 2 == 0:
     print((k//2)**2)
else:
     print((k//2)*((k//2)+1)


### FIXED CODE ###

k = int(input())

if k % 2 == 0:
    print((k//2)**2)
else:
    print((k//2)*((k//2)+1))
A,B = list(map(int,input().split()))
S = input()

for i in range(A):
    if S[i] == "-":
        print("No")
        exit()

if S[A] != "-":
    print("No")
    exit()

for i in range(A+1,A+1+B):
    if S[i] == "-":
        print("No")
        exit()

print("Yes")


### FIXED CODE ###

X,Y = list(map(int,input().split()))

cnt = 0
while X <= Y:
    X = X * 2
    cnt += 1
print(cnt)
# C - Snack
from math import gcd
A, B = map(int, input().split())
print(A * B // gcd(A, B))

### FIXED CODE ###

from fractions import *
a, b=map(int, input().split())
print(a * b // gcd(a, b))
H,W=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(H)]
B=[[int(i) for i in input().split()] for j in range(H)]
dp=[[0 for j in range(W)] for i in range(H)]
M=80*80*2+1
dp[0][0]|=1<<(A[0][0]-B[0][0]+M)
dp[0][0]|=1<<(-A[0][0]+B[0][0]+M)

for i in range(H):
    for j in range(W):
        dij=abs(A[i][j]-B[i][j])
        if i>0:
            dp[i][j]|=dp[i-1][j]<<dij
            dp[i][j]|=dp[i-1][j]>>dij
        if j>0:
            dp[i][j]|=dp[i][j-1]>>dij
            dp[i][j]|=dp[i][j-1]<<dij
ans=[]
for i in range(M):
    if (1<<i)&dp[-1][-1]!=0:
        ans.append(abs(i-M))
print(min(ans))


### FIXED CODE ###

H,W=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(H)]
B=[[int(i) for i in input().split()] for j in range(H)]
dp=[[0 for j in range(W)] for i in range(H)]
M=161*161
dp[0][0]|=1<<(A[0][0]-B[0][0]+M)
dp[0][0]|=1<<(-A[0][0]+B[0][0]+M)

for i in range(H):
    for j in range(W):
        dij=abs(A[i][j]-B[i][j])
        if i>0:
            dp[i][j]|=dp[i-1][j]<<dij
            dp[i][j]|=dp[i-1][j]>>dij
        if j>0:
            dp[i][j]|=dp[i][j-1]>>dij
            dp[i][j]|=dp[i][j-1]<<dij
ans=[]
for k in range(2*M+1):
    if (1<<k)&dp[-1][-1]!=0:
        ans.append(abs(k-M))
print(min(ans))
# 0028
import collections
array = [0]*100
i = 0
while True:
    try:
        array[i] = int(input())
        i += 1
    except EOFError:
        break
array = filter(lambda a: a != 0, array)
max = max(array.count())
print(filter(lambda a: array.count(a) == max, array), sep = '\n')

### FIXED CODE ###

# 0028
array = []
while True:
    try:
        a = input()
        array.append(int(a))
    except EOFError: break
s = set(array)
mx = max(sorted(s, reverse=True), key = array.count)
for a in sorted(s, key = array.count, reverse=True):
    print(a)
    if a == mx: break
from collections import deque
import sys

deque_s = deque(list(input()))
kyoto
deque_t = deque(list(input()))
tokyo

for _i in range(len(deque_s)):
    deque_s.rotate()
    if deque_s == deque_t:
        print('Yes')
        sys.exit()

print('No')

### FIXED CODE ###

from collections import deque
import sys

deque_s = deque(list(input()))
deque_t = deque(list(input()))

for _i in range(len(deque_s)):
    deque_s.rotate()
    if deque_s == deque_t:
        print('Yes')
        sys.exit()

print('No')
a=int(input().split())
for i in range(4):
 if a[i]==0:
  print(i)
 else:
  pass

### FIXED CODE ###

a=[]
a=input().split()
for i in range(5):
 if a[i]=='0':
   print(str(i+1))
 else:
   pass
def combi(count):
  if n==1:return 0
  elif n==2:return 1
  else:return int(count*(count-1)/2)


n=int(input())
alis=list(map(int,input().split()))
dick=dict()
for i in range(n):
  p=alis[i]
  dick[p]+=1

point=0
for k,v in dick:
  point+=combi(v)


for i in range(n):
  idx=alis[i]
  minus=dick[idx]-1
  print(point-minus)
  
  
  
  

### FIXED CODE ###

def combi(count):
  if n==1:return 0
  elif n==2:return 1
  else:return int(count*(count-1)/2)
 
 
n=int(input())
alis=list(map(int,input().split()))
dick={st:0 for st in set(alis)}
for i in range(n):
  p=alis[i]
  dick[p]+=1
#print(dick)
point=0
for v in dick.values():
  point+=combi(v)
 
 
for i in range(n):
  idx=alis[i]
  minus=dick[idx]-1
  print(point-minus)
s = input()
count = 0
for i in range(n - 1):
    if s[i:i+2] == "??":
        count += 1
ans = count * 7
print(ans)

### FIXED CODE ###

mod = 10 ** 9 + 7

s = input()
dp = [0] * 13
dp[0] = 1
for i in range(len(s)):
    dp2 = [0] * 13
    for j in range(10):
        if (s[i] == '?') | (s[i] == str(j)):
            for k in range(13):
                dp2[(10 * k + j) % 13] += dp[k]
                dp2[(10 * k + j) % 13] %= mod
    dp = dp2
print(dp[5])
#create date: 2020-07-03 14:00

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    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 same(x, y):
        return find(x) == find(y)
    
    n, m, k = na()
    par = [-1] * n
    fb = [[0] * n for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1; b -= 1
        unite(a, b)
        fb[a][b] = 1
        fb[b][a] = 1
    for i in range(k):
        c, d = na()
        c -= 1; d -= 1
        fb[c][d] = 1
        fb[d][c] = 1
    #print(par, fb)
    for i in range(n):
        ans = 0
        for j in range(n):
            if same(i, j) and fb[i][j]==0 and i != j:
                ans += 1
        print(ans, end=" ")
if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-07-03 14:00

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    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 same(x, y):
        return find(x) == find(y)
    def size(x):
        return -par[find(x)]


    n, m, k = na()
    par = [-1] * n
    friend = [0] * n
    block = [list() for i in range(n)]
    for i in range(m):
        a, b = na()
        a -= 1; b -= 1
        unite(a, b)
        friend[a] += 1
        friend[b] += 1
    for i in range(k):
        c, d = na()
        c -= 1; d -= 1
        block[c].append(d)
        block[d].append(c)
    #print(par, fb)
    for i in range(n):
        ans = size(i) - friend[i] - 1
        for b in block[i]:
            if same(i, b):
                ans -= 1
        print(ans, end=" ")
if __name__ == "__main__":
    main()
from bisect import bisect_left, bisect_right

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

def bsearch_list(a, x):
    l = bisect_left(a, x)
    r = bisect_right(a, x)
    if l < r:
        return list(range(l, r))
    else:
        return []

pair_list = [[i, set()] for i in range(N)]
for t in range(1, 50):
    pow2 = 2 ** t
    if A[-1] * 2 < pow2:
        break
    for i in range(N):
        pair = set(bsearch_list(A, pow2 - A[i])) - {i}
        pair_list[i][1] = pair_list[i][1] | pair
        
pair_list_idx = [p[0] for p in sorted(pair_list, key=lambda x: len(x[1]))]
ans = 0
for i in pair_list_idx:
    if len(pair_list[i][1]) == 0: continue
    another = pair_list[i][1].pop()
    pair_list_idx.remove(another)
    ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)
A, B = map(int, input().split())

if B == 1:
    print(0)
else:
    C = A
    cnt = 1
    while C < B:
        C += A - 1
        cnt += 1

print(cnt)


### FIXED CODE ###

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

if B == 1:
    print(0)
else:
    C = A
    cnt = 1
    while C < B:
        C += A - 1
        cnt += 1
    print(cnt)
# -*- coding: utf-8 -*-

n=int(input())
a=list(map(int, input().split()))
a.sort()
d=[0 for _ in range(8)]

flg=False
minim=-1
for i in range(n):
    if a[i]<400:
        d[0]=1
    elif a[i]<800:
        d[1]=1
    elif a[i]<1200:
        d[2]=1
    elif a[i]<1600:
        d[3]=1
    elif a[i]<2000:
        d[4]=1
    elif a[i]<2400:
        d[5]=1
    elif a[i]<2800:
        d[6]=1
    elif a[i]<3200:
        d[7]=1
    else:
        if flg==False:
            minim=sum(d)
            flg=True
        for j in range(n):
            if d[j]==0:
                d[j]=1
                break

if minim==-1:
    minim=sum(d)
print(minim, " ", sum(d))



### FIXED CODE ###

# -*- coding: utf-8 -*-

n=int(input())
a=list(map(int, input().split()))
a.sort()
d=[0 for _ in range(8)]

flg=False
minim=-1
for i in range(n):
    if a[i]<400:
        d[0]=1
    elif a[i]<800:
        d[1]=1
    elif a[i]<1200:
        d[2]=1
    elif a[i]<1600:
        d[3]=1
    elif a[i]<2000:
        d[4]=1
    elif a[i]<2400:
        d[5]=1
    elif a[i]<2800:
        d[6]=1
    elif a[i]<3200:
        d[7]=1
    else:
        if flg==False:
            minim=sum(d)
            flg=True
        d[0]+=1

if minim==-1:
    minim=sum(d)
elif minim==0:
    minim=1
print(minim,end=' ')
print(sum(d))
import sys
sys.setrecursionlimit(400010)

from sys import stdin
input = stdin.readline
def Tsundoku(i,j,k,n,m,dp,a,b):
    if (i,j) in dp:
        return dp[(i,j)]
    ans1,ans2 = 0,0
    if i<n and k-a[i]>=0:
        ans1 = 1+Tsundoku(i+1,j,k-a[i],n,m,dp,a,b)
    if j<m and k-b[j]>=0:
        ans2 = 1+Tsundoku(i,j+1,k-b[i],n,m,dp,a,b)
    dp[(i,j)] = max(ans1,ans2)
    return dp[(i,j)]
        
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = dict()
ans = Tsundoku(0,0,k,n,m,dp,a,b)
print(ans)


### FIXED CODE ###

from itertools import accumulate

def bs(t):
    l,h = 0,len(b)-1
    while l<=h:
        m = (l+h)//2
        if b[m]<t:
            l=m+1
        elif b[m]>t:
            h=m-1
        else:
            return m
    return h

n,m,k = map(int,input().split())
a = list(accumulate([0]+list(map(int,input().split()))))
b = list(accumulate([0]+list(map(int,input().split()))))
ans = 0
for idx,i in enumerate(a):
    if i<=k:
        #print(idx,bs(k-i))
        ans = max(ans,bs(k-i)+idx)
print(ans)
A,B=list(map(int,input().split(" ")));print([i for i in range(B) if A*i>= B][0])

### FIXED CODE ###

A,B = [int(i) for i in input().split(" ")]

for i in range(B):
    if (i*A)-(i-1) >= B:
        print(i)
        break
n=int(input())
arr=list(map(int,input().split()))
sumv=0
d={}
for i in arr:
    sumv+=i
    try:
        d[i]+=1
    except:
        d[i]=1

q=int(input())

while q:
    
    b,c=map(int,input().split())
    sumv+=(c-b)*d[b]
    try:
        d[c]+=d[b]
    except:
        d[c]=d[b]
    d[b]=0
    print(sumv)


    q-=1


### FIXED CODE ###


n=int(input())
arr=list(map(int,input().split()))
sumv=0
d={}
for i in arr:
    sumv+=i
    try:
        d[i]+=1
    except:
        d[i]=1

q=int(input())

while q:
    
    b,c=map(int,input().split())
    if b in d:
        sumv+=(c-b)*d[b]
   
        try:
            d[c]+=d[b]
        except:
            d[c]=d[b]
    d[b]=0
    print(sumv)


    q-=1
s = input()
K = int(input())
k = []

for i in range(len(s)):
  if s[i] not in k:
    k.append(s[i])
  
if len(s) >= 2:
  for i in range(len(s)-1):
    if s[i] + s[i+1] not in k:
      k.append(s[i] + s[i+1])
    
if len(s) >= 3:
  for i in range(len(s)-2):
    if s[i] + s[i+1] + s[i+2] not in k:
      k.append(s[i] + s[i+1] + s[i+2])
    
if len(s) >= 4:
  for i in range(len(s)-3):
    if s[i] + s[i+1] + s[i+2] + s[i+3] not in k:
      k.append(s[i] + s[i+1] + s[i+2] + s[i+3])
    
if len(s) >= 5:
  for i in range(len(s)-4):
    if s[i] + s[i+1] + s[i+2] +s[i+3] + s[i+4] not in k:
      k.append(s[i] + s[i+1] + s[i+2] +s[i+3] + s[i+4])
    
new = sorted(k)

print(new[K-1])

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if abs(a-c) <= d:
  print("Yes")
elif abs(a-b) <= d and abs(b-c) <= d:
  print("Yes")
else:
  print("No")
a, b = map(int, input().split())
if a* b == 15:
    print("*")
elif a+ b == 15:
    print("+")
else:
    print(x)

### FIXED CODE ###

a, b = map(int, input().split())
if a* b == 15:
    print("*")
elif a+ b == 15:
    print("+")
else:
    print("x")
def main():
    S  = input()
    K  = input()

    cnt = 0
    while S[cnt]=='1':
        cnt = cnt + 1
    
    if K<=cnt:
        print(S[0])
    else:
        print(S[cnt+1])




if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S  = input()
    K  = int(input())

    cnt = 0
    while cnt<len(S) and  S[cnt]=='1':
        cnt = cnt + 1
    
    if K<=cnt:
        print(S[0])
    elif cnt==len(S):
        print(S[cnt-1])
    else:
        print(S[cnt])


if __name__ == '__main__':
    main()
N, x = map(int, input().split())
A = list(map(int, input().split()))

answer = 0
if A[0] > X:
    answer += A[0] - X
    A[0] = X
    
for i in range(N-1):
    diff = A[i] + A[i+1] - X
    if diff > 0:
        answer += diff
        A[i+1] -= diff

print(answer)


### FIXED CODE ###

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

answer = 0
if A[0] > x:
    answer += A[0] - x
    A[0] = x
    
for i in range(N-1):
    diff = A[i] + A[i+1] - x
    if diff > 0:
        answer += diff
        A[i+1] -= diff

print(answer)
a,b,c = map(int, input().split())
print(' '.join(sorted([a,b,c])))


### FIXED CODE ###

n = list(map(int, input().split()))
n = sorted(n)
print(' '.join([str(x) for x in n]))
n = int(input())

count = 0

for i in range(n):
    if i / 0:
        count += 1
    else:
        pass

print(count/n)


### FIXED CODE ###

n = int(input())
 
count = 0
 
for i in range(n):
    if i % 2 != 0:
        count += 1
    else:
        pass
 
print(1-float(count/n))
import math
n = map(int, raw_input().split())
print math.hypot((n[0] - n[2]), (n[1] - n[3]))

### FIXED CODE ###

import math
n = map(float, raw_input().split())
print math.hypot((n[0] - n[2]), (n[1] - n[3]))
import sys
sys.setrecursionlimit(1000000)

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

num = max(one,two,three)

dp = [[[-1]*(three+1) for i in range(N+1)] for i in range(N+1)]

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

print(dp[one][two][three])


### FIXED CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1
    
M = t + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]

su = 0
D[t][d][m] = 1

divTable = [1]
for i in range(1, 10000):
  divTable.append(1.0 / i)


for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(M - i - j, -1, -1):
      y = D[i][j][k]
      if y != 0:
        div = y * divTable[i + j + k]
        if i + j + k != 0:
          su += N * div
        if i >= 1:
          D[i - 1][j + 1][k] += i * div
        if j >= 1: 
          D[i][j - 1][k + 1] += j * div
        if k >= 1:
          D[i][j][k - 1] += k * div

print(su)
N=int(input())
if N%9 == 0:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

N=int(input())
if N%9 == 0:
  print("Yes")
else:
  print("No")
S = input()
print("x"*count(S))

### FIXED CODE ###

S = input()
print("x" * len(S))
n, *w = map(int, open(0).read().split())
c = float("inf")
for i in range(n):
    s = abs(sum(w[:i])-sum(w[i:])):
    c = s if c>s else c
print(c)

### FIXED CODE ###

n, *w = map(int, open(0).read().split())
c = float("inf")
for i in range(n):
    s = abs(sum(w[:i])-sum(w[i:]))
    c = s if c>s else c
print(c)
num_list = input()
key = 'keyence'

i = 0
ans =False
while num_list[i]==key[i]:
    i+=1
n = i

i = -1
while num_list[i]==key[i]:
    i -= 1
    n += 1

if n >= 6:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

num_list = input()
key = 'keyence'
i = 0
l = len(num_list)

n = 0

while num_list[i]==key[i]:
    i+=1
    n +=1
    if n==7:
        print('YES')
        exit()

i = -1
while num_list[i]==key[i]:
    n += 1
    i -= 1
    if n==7:
        print('YES')
        exit()
print('NO')
N=int(input())
H=list(map(int, input().split()))

Hsub=[H[i+1]-H[i] for i in range(N-1)]

output='Yes'
for i in range(N):
  if Hsub>0:
    if H[i]-min(H[i+1])>1:
      output='No'
      
print(output)

### FIXED CODE ###

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

index=N-1
output='Yes'
while index>0:
  if h[index-1]-h[index]>1:
    output='No'
    break
  elif h[index-1]-h[index]==1:
    h[index-1]-=1
  else:
    pass
  index-=1
  
print(output)
def dfs(_v, _u):
  for u in v[_v]:
    if u==_u: continue;
    ans[u]+=ans[_v]
    dfs(u, _v)
        
  
def main():
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1, input().split())
    v[a].append(b)
    v[b].append(a)
  
  for i in range(q):
    p,x=map(lambda x:int(x)-1, input().split())
    ans[p]+=x+1
  
  dfs(0,-1)
  
  print(*ans, sep=' ')
  
if __name__=='__main__':
  n,q=map(int,input().split())
  ans=[0]*n
  v=[[]*n for i in range(n)]
  main()

### FIXED CODE ###

from collections import deque


def main():
  n,q=map(int,input().split())
  node=[[]*n for i in range(n)]
  for i in range(n-1):
    a,b=map(lambda x:int(x)-1,input().split())
    node[b].append(a)
    node[a].append(b)
  
  ans=[0]*n
  for i in range(q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

  root=[0]*n
  edge=[[]*n for i in range(n)]
  root[0]=0
  q=deque([0])
  visited=[False]*n
  visited[0]=True
  
  while q:
    r=q.popleft()
    for e in node[r]:
      if not visited[e]:
        visited[e]=True
        q.append(e)
        root[e]=r
        edge[r].append(e)
  
  
  p=[0]*n
  q=deque(edge[0])
  visited=[False]*n
  while q:
    e=q.popleft()
    p[e]=p[root[e]]+1
    for e2 in edge[e]:
      if not visited[e2]:
        visited[e2]=True
        q.append(e2)
  
  p=sorted(enumerate(p), key=lambda x:x[1])
  for i in range(1,n):
    e=p[i][0]
    r=root[e]
    ans[e]+=ans[r]
    
  print(*ans,sep=' ')


if __name__=='__main__':
  main()