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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
dp = [INF]*(1<<N)
dp[0] = 0

for _ in range(M):
	a, b = MAP()
	c = LIST()
	d = 0
	for x in c:
		d += 1<<(x-1)

	for j in range(1<<N):
		tmp = j|d
		dp[tmp] = min(dp[tmp], dp[j]+a)

if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
dp = [INF]*(1<<N)
dp[0] = 0

for _ in range(M):
	a, b = MAP()
	c = LIST()
	d = 0
	for x in c:
		d += 1<<(x-1)

	for j in range(1<<N):
		tmp = j|d
		dp[tmp] = min(dp[tmp], dp[j]+a)

if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])
### BUGGY CODE ###

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

bs = 10**9 + 7
sm = 0

for i, ai in enumerate(a):
    sm += (ai * sum(a[(i+1):])) % bs
    sm = sm % bs

print(sm)

### FIXED CODE ###

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

bs = 10**9 + 7
s = sum(a)
sm = 0

for i, ai in enumerate(a):
    s -= ai
    sm += (ai * s) % bs
    sm = sm % bs

print(sm)
### BUGGY CODE ###

from collections import Counter

N = int(input())
As = [int(n) for n in input().split()]

C = Counter(As)

L = [(v * (v - 1) // 2, (v - 1) * (v - 2) // 2, k) for k, v in C.items()]

for i in range(N):
    print(sum([y if z == As[i] else x for x, y, z in L]))

### FIXED CODE ###

from collections import Counter

N = int(input())
As = [int(n) for n in input().split()]

C = Counter(As)

ans = sum(v * (v - 1) // 2 for k, v in C.items())
M = [C[a] - 1 for a in As]

for m in M:
    print(ans - m)
### BUGGY CODE ###

N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        ar1.sort(reverse = True)
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= sum(ar1):
                b = i+1
                break
        print(len(ar1)+b)

### FIXED CODE ###

N = int(input())
A =  []
l1 = input().split()
for i in l1:
    A.append(int(i))
B = []
l2 = input().split()
for i in l2:
    B.append(int(i))
if sum(A) < sum(B):
    print(-1)
else:
    z = 0
    ar1 = []
    ar2 = []
    for i in range(N):
        if A[i] < B[i] :
            ar1.append(B[i] - A[i])
        if A[i] > B[i]:
            ar2.append(A[i] - B[i])
    if len(ar1) == 0:
        print(0)
    else:
        s = sum(ar1)
        ar2.sort(reverse = True)
        temp = 0
        b = 0
        for  i in range(len(ar2)):
            temp += ar2[i]
            if temp >= s:
                b = i+1
                break
        print(len(ar1)+b)
### BUGGY CODE ###

B = []
L = int(input(),2)
c = 0
ans = 0
while(L > 0):
	if L % 2 == 1:
		B.append(c)
	L //= 2
	c += 1
leng = len(B)-1
for i in B:
	ans = (ans + (2**leng)*(3**i))%1000000007
	leng -= 1
print((ans+2**(len(B)))%1000000007)

### FIXED CODE ###

L = input()
length = len(L)
a = 2
b = 1
c = 4
for l in L[1:]:
	if l  == '1':
		a = (a * 3) % 1000000007
		b = (b * 3) % 1000000007
		c = (c * 2) % 1000000007
	else:
		a = (a * 3 - c) % 1000000007
		b = (b * 3) % 1000000007
print((a + b)%1000000007)
### BUGGY CODE ###

a,b=map(int,input().split())
for i in range(1,10**8):
  if int(0.08*i)==a and int(0.1*i)==b:
    print(i)
    exit()
print(-1)

### FIXED CODE ###

a,b=map(int,input().split())
for i in range(1,10**8):
  if int(0.08*i)==a and int(0.1*i)==b:
    print(i)
    exit()
print(-1)
### BUGGY CODE ###

import numpy as np
n, k, q = map(int, input().split())
points = np.full(n, k)
minus = np.full(n, -1)
for i in range(q):
    a = int(input())
    points = np.array(points) + np.array(minus)
    points[a - 1] += 1
for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np
n, k, q = map(int, input().split())
points = np.full(n, k)
z = np.full(n, 0)
points = points - q
for i in range(q):
    a = int(input())
    z[a - 1] += 1
points = points + z
for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max([i, c0, c1, c2])
    return dp[n]


print(count(count(N, A, B), B, A))


### FIXED CODE ###

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


def count(n, a, b):
    a0, a1, a2 = a
    b0, b1, b2 = b
    dp = [0] * (n + 1)
    for i in range(n + 1):
        c0 = dp[i - a0] + b0 if i - a0 >= 0 else 0
        c1 = dp[i - a1] + b1 if i - a1 >= 0 else 0
        c2 = dp[i - a2] + b2 if i - a2 >= 0 else 0
        dp[i] = max(i, c0, c1, c2)
    return dp[n]


print(count(count(N, A, B), B, A))
### BUGGY CODE ###

#E
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
n=int(input())
v=n**2
A=[list(map(lambda x: int(x)-1,input().split())) for _ in range(n)]
Edges=set()
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.add((fr_i*n+fr_j,to_i*n+to_j))
outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in Edges:
    outs[v1].append(v2)
    ins[v2] += 1
q = deque((v1,1) for v1 in range(v) if ins[v1] == 0 and outs[v1])
res = []
while q:
    v1,d = q.popleft()
    res.append((v1,d))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,d+1))
print(res[-1][1] if len(res)==n*(n-1)//2 else -1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import defaultdict,deque
def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

n=int(input())
v=n*(n-1)//2
A=[list(map(lambda x: int(x)-1,input().split())) for _ in range(n)]
Edges=[]
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.append((conv(n,fr_i,fr_j),conv(n,to_i,to_j)))
Outs=defaultdict(list)
In_cnt=defaultdict(int)
for v1,v2 in Edges:
    Outs[v1].append(v2)
    In_cnt[v2]+=1
q=deque((v0,1) for v0 in range(v) if In_cnt[v0]==0)
TopologicalSort=[]
while q:
    v1,d=q.popleft()
    TopologicalSort.append((v1,d))
    for v2 in Outs[v1]:
        In_cnt[v2]-=1
        if In_cnt[v2]==0:
            q.append((v2,d+1))
print(TopologicalSort[-1][1] if len(TopologicalSort)==n*(n-1)//2 else -1)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
tmp=0    
for i in range(N):
    tmp=A[i]
    A[i]=0
    print(max(A))
    A[i]=tmp


### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)] 
B=sorted(A)
for i in A:
    if i==B[-1]:
        print(B[-2])
    else:
        print(B[-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

N = len(s) + 1
M = len(t) + 1


# dp[i][j] := s[i] t[j]までのLCS
dp = [[""]*M for _ in range(N)]


for i in range(1, N):
    for j in range(1, M):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + s[i-1]
        else:
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

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

### FIXED CODE ###

import sys

input = sys.stdin.readline

s = input()[:-1]
t = input()[:-1]

N = len(s) + 1
M = len(t) + 1


# dp[i][j] := s[i] t[j]までのLCS
dp = [[0]*M for _ in range(N)]


for i in range(1, N):
    for j in range(1, M):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

"""
復元
もしdp[i][j] == dp[i][j-1]ならt[j-1]は使われていないことがわかる
もしdp[i][j] == dp[i-1][j]ならs[i-1]は使われていないことがわかる
それ以外の場合、s[i-1], t[j-1]が使われていることがわかる
"""

ans = ""
i = len(s)
j = len(t)

while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans = s[i-1] + ans  # t[j-1] + ansでも同じ
        i -= 1
        j -= 1
print(ans)
### BUGGY CODE ###

import gc
n = int(input())
num = list(map(int,input().split()))

for i in range(1,n+1):
    print(num.count(i))
del num
gc.collect()

### FIXED CODE ###

n = int(input())
num = [0] * n
employee = list(map(int,input().split()))

for i in employee:
    num[i-1] += 1

for j in num:
    print(j)
### BUGGY CODE ###

n,m = [int(i) for i in input().split()]
ab = []
for i in range(m):
  array = list(map(int,input().split()))
  ab.append(array)

w = [[int(i) for i in range(ab[u][0],ab[u][1])] for u in range(m)]
ans = 0
#print(w)
import collections
while True:
  d = [e for row in w for e in row]
  #print(d)
  if d == []:
    print(ans)
    break
  else:
    # collections.Counter使用時は宣言する
    c = collections.Counter(d)
    t = c.most_common()[0][0]
    ans += 1
    w = [i for i in w if not t in i]
    #print(w)

### FIXED CODE ###

from operator import itemgetter

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

# 区間の終端でソート
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a in ab:
    # a が removed より大きい = まだ取り除いてない
    if a[0] > removed:
        #print(a)
        removed = a[1] - 1
        ans += 1

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

K = int(input())
S = 7
i = 1
if (1 <= K) and (K <= (10 ** 6)):
    while True:

        if int(S) % K != 0:
            S = S * 10 + 7
            i += 1
        elif i > K:
            break
        else:
            break
    print(i)
else:
    pass

### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
elif K % 5 == 0:
    print(-1)
else:
    S = 7
    for i in range(K+1):
        if S % K == 0:
            print(i+1)
            break
        else:
            S = S % K
            S = S * 10 + 7
    else:
        print(-1)
### BUGGY CODE ###

N = int(input())

s = [sorted(list(input())) for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1, N):
        if s[i]==s[j]:
            ans+=1

print(ans)


### FIXED CODE ###

import collections
N = int(input())

s = [sorted(list(input())) for i in range(N)]

for i in range(N):
    s[i] = ''.join(s[i])

ans = 0

c = collections.Counter(s)
for v in c.values():
    ans += (1/2) * v * (v-1)

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

import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])


#print(k,s)

cnt = 0
    
x = 0
#xがmax以下がどうかチェック
while x <= k:

#    xが合計よりおおきい
    if x > s:
        
        break
        
    y = 0
    #yがmax以下がどうかチェック
    while y <= k:
        
        
#        print(x,y,y>s,x+y>s,s-x>s*k,s-x-y>k,s-x-y,2*k)
#       yが合計より大きい　あるいは　x+yが合計より大きい
        if (y > s) or (x + y > s) or (s-x>2*k):
        
            break
            
#        if s-x-y>k:
#            
#            continue
#            
            
#        print(x,y,s-x-y,k,s-x-y<=k)    
        if s-x-y <= k:    

            cnt += 1

        y += 1

    x += 1

print(cnt)
    
    


### FIXED CODE ###

def getinputdata():

    array_result = []
    
    data = input()
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result

arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])

cnt = 0

for x in range(0, k + 1):
    
    for y in range(0, k + 1):
        
        z = s-x-y
        
        if z >= 0 and z <= k:
            
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(1,n):
    ans += i
    
print(ans)

### FIXED CODE ###

n = int(input())

print((n-1)*n // 2)
### BUGGY CODE ###

s = input()
k = int(input())

cand_list = []
for i in range(1, len(s)+1):
    for j in range(len(s)):
        cand_list.append(s[j:j+i])

print(sorted(list(set(cand_list)))[k-1])

### FIXED CODE ###

s = input()
k = int(input())

cand_list = []
for i in range(len(s)):
    for j in range(len(s)+1-i):
        _s = s[i:i+j+1]
        cand_list.append(_s)
        cand_list = sorted(set(cand_list))
        if len(cand_list) > k and cand_list[len(cand_list) - 1] == _s:
            cand_list.remove(_s)
            break
        elif len(cand_list) > k:
            cand_list.pop(len(cand_list) - 1)

print(sorted(cand_list)[k-1])
### BUGGY CODE ###

s = input()
n = len(s)
old_length=-1
for i in range(n):
  if old_length==len(s):
    break
  old_length=len(s)
  s=s.replace('01','').replace('10','')
print(n-len(s))

### FIXED CODE ###

s = input()
c1,c2=s.count('0'),s.count('1'),
print(min(c1,c2)*2)
### BUGGY CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
#print(l)
x = []
for i in range(n-1):
    x.append(l[i+1] - l[i])
x  = sorted(x)
#print(x)

z = []
for j in range(n-k):
    z.append(sum(x[j:j+k-1]))
print(min(z))


### FIXED CODE ###

n, k = map(int, input().split())
l = [int(input()) for _ in range(n)]
l = sorted(l)
#print(l)
x = []
for i in range(n-k+1):
    x.append(l[i+k-1] - l[i])
x  = sorted(x)
#print(x)

print(min(x[:k-1]))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

if __name__ == "__main__":
    list = input().split(" ")
    N = int(list[0])
    M = int(list[1])
    for i in range(M):
        if M%(N+i) == 0:
            print(int(M/(N+i)))
            exit()
        if M/(N+i) < 2:
            print(1)
            exit()


### FIXED CODE ###


#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math

if __name__ == "__main__":
    list = input().split(" ")
    N = int(list[0])
    M = int(list[1])
    list = []
    for i in range(1,int(math.sqrt(M)+1)):
        if M%i == 0:
            list.append(i)
    for i in range(len(list)):
        list.append(int(M/list[i]))
    print(max([i for i in list if i <= M // N]))
### BUGGY CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,n+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
    if n<i:break
        
  return ps
  
N,P = map(int,input().split())
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
    

### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
### BUGGY CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
valid = [True] * len(A)
sqrt = A[len(A)-1] // 2
stop = -1
for i in range(len(A)):
    if A[i] > sqrt:
        stop = i
        break
    if valid[i] == False:
        continue
    for j in range(i+1, len(A)):
        if valid[j] == False:
            continue
        if A[j] % A[i] == 0:
            valid[j] = False
        if A[j] == A[i]:
            valid[i] = False
if stop != -1:
    cur = A[stop]
    for i in range(stop+1, len(A)):
        if cur == A[i]:
            valid[i-1] = valid[i] = False
        else:
            cur = A[i]
print(valid.count(True))


### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * maxA

for i in range(len(A)):
    if valid[A[i]-1] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]-1] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j-1] = False

count = 0
for i in range(len(A)):
    if valid[A[i]-1] == True:
        count += 1
print(count)
### BUGGY CODE ###

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j]+=2*dp[i][j]
		dp[i+1][j]%=mod
		if j+a[i]<=s:
			dp[i+1][j+a[i]]+=dp[i][j]
			dp[i+1][j+a[i]]%=mod
print(dp[n][s])

### FIXED CODE ###

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
	for j in range(s+1):
		dp[i+1][j]+=2*dp[i][j]
		dp[i+1][j]%=mod
		if j+a[i]<=s:
			dp[i+1][j+a[i]]+=dp[i][j]
			dp[i+1][j+a[i]]%=mod
print(dp[n][s])
### BUGGY CODE ###

S = input()
N = len(S)
K = int(input())
cnt = {i: [] for i in range(N)}
for i in range(N):
    for j in range(N - i):
        s = S[j:j+i+1]
        l = len(s)
        if s not in cnt[l-1]:
            cnt[l-1].append(s)
ttl = []
for k, v in cnt.items():
    ttl.extend(v)
ttl.sort()
print(ttl[K-1])

### FIXED CODE ###

S = input()
N = len(S)
K = int(input())
cnt = {i: [] for i in range(N)}
for i in range(N):
    for j in range(N - i):
        s = S[j:j+i+1]
        l = len(s)
        if s not in cnt[l-1]:
            cnt[l-1].append(s)
    if i > K:
        break
ttl = []
for k, v in cnt.items():
    ttl.extend(v)
ttl.sort()
print(ttl[K-1])
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = (((P*(P+1)/2))/P)
    kitaichi.append(kitai)
ans = []
for j in range((n-k)+1):
    a = sum(kitaichi[j:j+k])
    ans.append(a)
print(max(ans))


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = 1+P
    kitaichi.append(kitai)
m = [0,]
a = 0
for j in range(n):
    a += kitaichi[j]
    m.append(a)
ans = 0
for l in range(n-k+1):
    temp = m[l+k]-m[l]
    if temp> ans:
      ans = temp
print(ans/2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q = map(int,input().split())
costs = [0]*n
net = [[] for _ in range(n)]
for _ in range(1,n):
	a,b = map(int,input().split())	
	a -= 1
	b -= 1
	net[a].append(b)
	net[b].append(a)
	
for _ in range (q):
	p,x = map(int,input().split())
	p -= 1
	costs[p] += x

def dfs(parents,checked_par):
	for children in net[parents]:
		if children == checked_par:
			continue
		costs[children] += costs[parents]
		dfs(children,parents)
dfs(0,-1)

print(*costs)


### FIXED CODE ###

from collections import deque
n,q = map(int,input().split())
graph = [[] for _ in range(n)]
cnt = [0] * n
already = [False] * n

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1] += x
wait_q = deque()
wait_q.append(0)

while len(wait_q) > 0:
    parent = wait_q.popleft()
    for child in graph[parent]:
        if child == 0:continue
        if already[child] == True:continue
        already[child] = True
        cnt[child] += cnt[parent]
        wait_q.append(child)
print(*cnt)
### BUGGY CODE ###

from functools import lru_cache

@lru_cache()
def pow(i):
    if i==0:
        return 1
    elif i==1:
        return 10

    if i%2==0:
        return pow(i//2)*pow(i//2)
    else:
        return pow(i-1)*10

S=input()
count=[0 for i in range(2019)]
length=len(S)
S=int(S)

for i in range(length+1):
    n=S%pow(i)
    count[n%2019]+=1



retval=0
for key in range(2019):
    retval+=count[key]*(count[key]-1)//2


print(retval)


### FIXED CODE ###

from functools import lru_cache



S=input()
count=[0 for i in range(2019)]
length=len(S)
#S=int(S)
S=S+'0'
S=S[::-1]
_S=0

base=1
for i,s in enumerate(S):
    _S=base*int(s)+_S
    count[_S%2019]+=1
    base*=10
    base=base%2019
    _S=_S%2019



retval=0
for key in range(2019):
    retval+=count[key]*(count[key]-1)//2


print(retval)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, 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.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def max_group_members(self):
        ret = 1
        for r in self.roots():
            ret = max(len(self.members(r)), ret)
        return ret

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
Groups = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    Groups.union(a-1, b-1)

print(Groups.max_group_members())

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


N, M = map(int, input().split())
Groups = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    Groups.union(a-1, b-1)

ans = 0
for i in range(N):
    ans = max(Groups.size(i), ans)

print(ans)