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

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m = map(int, input().split())
r=[[0 for i in range(n)]for i in range(n)]
start = [0, 0]
#print(bfs(h, w, m, start))
for i in range(m):
    a,b=map(int, input().split())
    r[a-1][b-1]=b-1
    r[b-1][a-1]=a-1
#print(r)

def bfs(n,r,start):
    #始点に対して終点"g"に着けるか判定

    from collections import deque
    d = [0 for i in range(n)]
    visited=[False for i in range(n)]
    flg = True
    queue=deque([0])
    dd=0
    while queue:
        now=queue.popleft()
        visited[now]=True
        #print(now)
        for i in r[now]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                d[i]=now
    for i in range(n):
        if not visited:
            flg=False
    #print(d)
    if flg:
        print("Yes")
        for i in range(1,n):
            print(d[i]+1)
    else:
        print("No")
    return "Yes" if flg else "No"

bfs(n,r,start)
#print(d)
"""
    a = queue.Queue()
    a.put(start)
    while not a.empty():
        na, nb = map(int, a.get())
        if m[hh][ww] == "g":
            flg = True
            break

        for i in range(4):
            nx, ny = ww+dx[i], hh+dy[i]
            if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                a.put([ny, nx])
                d[ny][nx] = 1
"""

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n,m = map(int, input().split())
    r=[[]for i in range(n)]
    start = [0, 0]
    #print(bfs(h, w, m, start))
    for i in range(m):
        a,b=map(int, input().split())
        r[a-1].append(b-1)
        r[b-1].append(a-1)
    #print(r)
    
    from collections import deque
    d = [0 for i in range(n)]
    visited=[False for i in range(n)]
    flg = True
    queue=deque([0])
    dd=0
    while queue:
        now=queue.popleft()
        visited[now]=True
        #print(now)
        for i in r[now]:
            if visited[i]:
                continue
            queue.append(i)
            visited[i]=True
            d[i]=now

    print("Yes")
    for i in range(1,n):
        print(d[i]+1)


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

n=int(input())
s=str(input())
ans=[]
for i in range(0,n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      ans.append(s[i]+s[j]+s[k])
ans=list(set(ans))
print(len(ans))

### FIXED CODE ###

n=int(input())
s=str(input())
ans=0
i=0
while i<1000:
  temp=i//100
  cnt=0
  k=0
  for j in range(0,n):
    if temp==int(s[j]):
      cnt=cnt+1
      k=j
      break
  if cnt==0:
    i=i+100
  else:
    temp=(i-(i//100)*100)//10
    for j in range(k+1,n):      
      if temp==int(s[j]):
        cnt=cnt+1
        k=j
        break
    if cnt==1:
      i=i+10
    else:
      temp=i%10
      i=i+1
      for j in range(k+1,n):
        if temp==int(s[j]):
          ans=ans+1
          break
print(ans)
### BUGGY CODE ###

n = int(raw_input())

def fib(N):
    if N in [0, 1]:
        return 1
    else:
        return fib(N-1) + fib(N-2)

print fib(n)

### FIXED CODE ###

n = int(raw_input())
a = 1
b = 1
for i in range(n-1):
    tmp = a
    a = b
    b += tmp
print b
### BUGGY CODE ###

import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    return -1


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

if start == -1:
    print(0)
else:
    print((M - start) // cycle + 1)



### FIXED CODE ###

import fractions, sys
input = sys.stdin.buffer.readline


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        if X > M:
            print(0)
            exit()
            return
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    print(0)
    exit()
    return


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

print((M - start) // cycle + 1)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array([int(x) for x in input().split()])

cost = np.full(N, 0)
for i in range(1, N):
    gaps = np.abs(h[max(0, i-K):i] - h[i]) + cost[max(0, i-K):i]
    cost[i] = np.min(gaps)
    
print(int(cost[N-1]))

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
hights = np.array(list(map(int,input().split())))
steps=np.array([0]*N)
steps[0]=0

for i in range(1, N):
    gaps = hights[max(0, i-K):i] - hights[i]
    gaps = np.abs(gaps)
    gaps += steps[max(0, i-K):i]
    steps[i] = np.min(gaps)
    
print(int(steps[N-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

x=[0]*(10**5)
for i in range(n):
    x[a[i]-1]+=a[i]


for _ in range(q):
    b,c=map(int,input().split())
    if x[b-1]!=0:
        x[c-1]+=x[b-1]//b*c
        x[b-1]=0
        print(sum(x))
    else:
        print(sum(x))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

ans=sum(a)

x=[0]*(10**5+10)
for i in a:
    x[i]+=1


for _ in range(q):
    b,c=map(int,input().split())
    ans+=x[b]*c-x[b]*b
    print(ans)
    x[c]+=x[b]
    x[b]=0
### BUGGY CODE ###

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

R_max = -10**9
for i in range(n-1):
    for j in range(i+1, n):
        if R[j] - R[i] > R_max:
            R_max = R[j] - R[i] 
print(R_max)

### FIXED CODE ###

n = int(input())
R = [int(input()) for i in range(n)]
minx = R[0]
maxx = -10**9
for i in range(1, n):
    if R[i] - minx > maxx:
        maxx = R[i] - minx
    if R[i] < minx :
        minx = R[i]
print(maxx)
### BUGGY CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  zeros = [0] * 60
  for i in range(N):
    x = A[i]
    x = bin(x)[2:]
    x = x.zfill(60)
    for j in range(59, -1, -1):
      if x[j] == '0':
        zeros[j] += 1
      else:
        ones[j] += 1
  # print(ones)
  # print(zeros)

  res = 0
  for i in range(N):
    x = A[i]
    x = bin(x)[2:]
    x = x.zfill(60)
    for j in range(60):
      if x[-j - 1] == '0':
        res += ones[-j - 1] * 2 ** j
        res %= MOD
        zeros[-j - 1] -= 1
      else:
        res += zeros[-j - 1] * 2 ** j
        res %= MOD
        ones[-j - 1] -= 1
  print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_b

N, K = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

dp = [0] * (N)
dp[0] = 0

# 参考：https://atcoder.jp/contests/dp/submissions/10181844
for i in range(1, N):
    tmp = [dp[k] + abs(h[i] - h[k]) for k in range(max(0, i - K), i)]
    dp[i] = min(tmp)
print(dp[-1])


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_b

def main():
    N, K = map(int, input().split())
    h = [int(x) for x in input().split()]

    dp = [0] * (N)
    dp[0] = 0

    # 参考：https://atcoder.jp/contests/dp/submissions/10181844
    for i in range(1, N):
        tmp = [dp[k] + abs(h[i] - h[k]) for k in range(max(0, i - K), i)]
        dp[i] = min(tmp)
    print(dp[-1])


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

import sys
n=int(input())
print(0)
l=input()
L=0
if l=='Vacant':
  sys.exit()
print(n-1)
r=input()
R=n-1
if r=='Vacant':
  sys.exit()

while True:
  print((L+R)//2)
  x=input()
  X=(L+R)//2
  if x=='Vacant':
    sys.exit()
  if ((X-L)%2==1 and x==l) or ((X-L)%2==0 and x=!l):
    r=x;R=X
  else:
    l=x;L=X

### FIXED CODE ###

import sys
n=int(input())
print(0)
l=input()
L=0
if l=='Vacant':
  sys.exit()
print(n-1)
r=input()
R=n-1
if r=='Vacant':
  sys.exit()

while True:
  print((L+R)//2)
  x=input()
  X=(L+R)//2
  if x=='Vacant':
    sys.exit()
  if ((X-L)%2==1 and x==l) or ((X-L)%2==0 and x!=l):
    r=x;R=X
  else:
    l=x;L=X
### BUGGY CODE ###

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

a = 0
b = 0
c = 0
cnt = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      b = 0
      a = 0
      for x in range(n):
        if a == 0:
          if int(s[x]) == i:
            a = 1
        elif b == 0:
          if int(s[x]) == j:
            b = 1
        elif c == 0:
          if int(s[x]) == k:
            cnt += 1
            break    
        

print(cnt)

### FIXED CODE ###

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

li = [[] for _ in range(10)]

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

a = 0
b = 0
c = 0
cnt = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      b = 0
      a = 0
      
      if len(li[i]) > 0:
        a = li[i][0]
          
        for d in li[j]:
            if d > a:
                b = d
                break
        else:
            break
        
        for e in li[k]:
            if e > b:
                cnt += 1
                break
        

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

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  if a[i] % 2 == 0:
    b.append(a[i])
a = b
count = 0
while True:
  if len(a) == 0:
    break
  i = a.index(max(a))
  a[i] /= 2
  count += 1
  if a[i] % 2 == 1:
    a.remove(a[i])
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
  while a[i] % 2 == 0:
    count += 1
    a[i] = a[i]//2
print(count)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
anslist = [[0]*N for i in range(N)]
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			anslist[i][j] = kk
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

ans = []
for ai, bi in ab:
	ans.append(anslist[ai-1][bi-1])

print(K,*ans,sep='\n')

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
# anslist = [[0]*N for i in range(N)]
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

print(K)
for ai, bi in ab:
	print(Kpre[bi-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
AB=[(a,b) for a,b in zip(A,B)]
AB.sort(key=lambda x:x[1])
AI=[(i,AB[i][0]) for i in range(N)]
AI.sort(key=lambda x:x[1])
sigma=[AI[i][0] for i in range(N)]
ASort=sorted(A)
BSort=sorted(B)
g=0
for i in range(N):
    if ASort[i]>BSort[i]:
        g=1
        break
counter=0
if g==0:
    index=list(range(N))
    used=[]
    for i in index:
        if not(i in used):
            start=i
            used.append(i)
            now=sigma[start]
            used.append(now)
            counter+=1
            if counter==2:
                break
            while start!=now:
                now=sigma[now]
                used.append(now)
if counter!=2 or g==1:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.array(list(map(int,input().split())))

AB=np.array([(A[i],B[i]) for i in range(N)])
AB=AB[np.argsort(AB[:,1])]

AI=np.array([[i,AB[i,0]] for i in range(N)])
AI=AI[np.argsort(AI[:,1])]

sigma=AI[:,0]
ASort=AI[:,1]
BSort=AB[:,1]

g=0
f=0
for i in range(N):
    if ASort[i]>BSort[i]:
        g=1
        break

counter=1
start=0
now=sigma[start]
while start!=now:
    now=sigma[now]
    counter+=1
    
if N==counter:
    f=1
    for i in range(N-1):
        if BSort[i]>=ASort[i+1]:
            f=0
            break

if f==0 and g==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
X = input()

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで
one = [0]*N

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1
for i in range(N):
    if X[i] == "1":
        one[i] = c-1
    else:
        one[i] = c+1
#print(one)

b1 = bin_num = int(X, 2)

for i in range(N):
    if X[i] == "0":
        B1 = b1 + 2**(N-1-i)
    else:
        B1 = b1 - 2**(N-1-i)
    #print(B1)
    if B1 == 0:
        print(0)
        continue
    else:
        B2 = B1%one[i]
    x = format(B2, 'b')
    #print(x)
    S = len(str(x))

    c2 = 0
    for j in range(S):
        if x[j] == "1":
            c2 += 1

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

### FIXED CODE ###

N = int(input())
X = input()

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = []
plus = sum(l)
for i in range(n):
    
    minus = 0
    
    for j in range(1,n,2):  
        
        minus += l[(i+j)%n]
    ans.append(plus-2*minus)

print(*ans)


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = []
plus = sum(l)
minus = 0
for j in range(1,n,2):  
        
    minus += l[(j)%n]
ans.append(plus-2*minus)
for i in range(1,n):
    ans.append(2*l[i-1]-ans[i-1])

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

import sys
sys.setrecursionlimit(int(1e6))

N = int(input())

M_sum = 0
for i in range(1, N):
    M_sum  += i

M_sum += N % 1
print(M_sum)


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e6))

N = int(input())

n = N - 1
if bool(n%2):
    ans = (n//2) * (n) + n
else:
    ans = (n//2) * (n+1)

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

def get_anti_key(n: int):
    prime_factors = []
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            prime_factors.append((k, cnt))
    if n != 1:
        prime_factors.append((n, 1))
    anti_key = 1
    for key, cnt in prime_factors:
        anti_key *= key ** ((3 - cnt) % 3)
    return anti_key


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


# 立方数のリスト
pow3 = [i ** 3 for i in range(2, 50)]

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    for div in pow3:
        while s[i] % div == 0:
            s[i] //= div

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = get_anti_key(key)
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


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


primes = make_prime_numbers(int((10 ** 10) ** (1 / 3) + 20))
pow2 = set([i ** 2 for i in range(10 ** 5 + 10)])
to_anti = {}

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s in pow2:
        to_anti[s[i]] = anti * int(tmp_s ** 0.5)
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

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

import sys
sys.setrecursionlimit(10**9)

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

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

if m%3==1:
    print("Second")
else:
    print("First")

### FIXED CODE ###

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

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

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

if m%3==1:
    print("Second")
else:
    print("First")
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

visited = [False] * N
def dfs(v, acc):
    if visited[v]:
        return
    visited[v] = True
    count[v] += acc
    for u in adj[v]:
        dfs(u, count[v])

dfs(0, 0)
print(" ".join(map(str, count)))

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

visited = [False] * N
def dfs(v):
    visited[v] = True
    for u in adj[v]:
        if visited[u]:
            continue
        count[u] += count[v]
        dfs(u)

dfs(0)
print(*count)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
L=[]
for i in range(n):
  if i%2==n%2:L.append(l[i])
  else:L.insert(0,l[i])
for j in range(n):
  print(L[j],end=' ')

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l1=[];l2=[]
for i in range(n):
  if i%2==n%2:l1.append(l[i])
  else:l2.append(l[i])
l2.reverse()
for j in range(len(l1)):
  l2.append(l1[j])
for j in range(n):
  print(l2[j],end=' ')
### BUGGY CODE ###

from collections import deque

s = deque(input())
q = int(input())

flg_reverse = False


def query_1():
    global flg_reverse
    if flg_reverse is True:
        flg_reverse = False
    else:
        flg_reverse = True



def query_2(s, a, b):
    global flg_reverse
    if flg_reverse is False:
        if a == 2:
            s.append(b)
        elif a == 1:
            s.appendleft(b)
    else:
        if a == 1:
            s.append(b)
        elif a == 2:
            s.appendleft(b)


for i in range(q):
    array = list(input().split())
    if len(array) == 1:
        query_1()
    else:
        query_2(s, int(array[1]), array[2])

if flg_reverse is False:
    for i in s:
        print(i, end='')
else:
    for i in range(len(s)-1, -1, -1):
        print(s[i], end='')



### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())
flg = 1
for i in range(q):
    array = input().split(' ')
    if array[0] == '1':
        flg *= -1
    elif array[0] == '2':
        if array[1] == '1' and flg == 1 or array[1] == '2' and flg == -1:
            s.appendleft(array[2])
        else:
            s.append(array[2])

s = list(s)
if flg == -1:
    s = s[::-1]

s = ''.join(s)
print(s)
### BUGGY CODE ###

n = int(input())
s = input()
r_list = []
g_list = []
b_list = []
cnt = 0
for i, j in enumerate(s):
    if j == 'R':
        r_list.append(i + 1)
    if j == 'G':
        g_list.append(i + 1)
    if j == 'B':
        b_list.append(i + 1)
for r in r_list:
    for g in g_list:
        for b in b_list:
            if r * 2 != g + b and g * 2 != r + b and b * 2 != r + g:
                cnt += 1
print(cnt)


### FIXED CODE ###

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

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
print(ans)