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

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        d_ = dp[(i+1)>>1][:]
        if i <= m:
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
        V.append(v)
        W.append(w)
        dp.append(d_)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    dp = [[[0.0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    def rec(i,j,k):
        #global res
        if dp[i][j][k] > 0.0:
            return dp[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0.0
        res = 0.0
    
        if i > 0.0: res += rec(i-1,j,k)*i
        if j > 0.0: res += rec(i+1,j-1,k)*j
        if k > 0.0: res += rec(i,j+1,k-1)*k
        res += N
        res *= 1.0/(i+j+k)
        dp[i][j][k] = res
        return res
    
    one = a.count(1)
    two = a.count(2)
    three = a.count(3)
    
    #print(dp)
    print(rec(one,two,three))
    #print(dp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
### BUGGY CODE ###

N=int(input())
Alist=list(map(int,input().split()))
ans=1
for i in range(N):
  ans=ans*Alist[i]

if ans>10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N=int(input())
Alist=list(map(int,input().split()))
Alist.sort()
ans=1
err=0
for i in range(N):
  ans=ans*Alist[i]
  if ans>10**18:
    print(-1)
    err=1
    break
if err==0:
  print(ans)
### BUGGY CODE ###

n, m = map(int,input().split())
ans = 0
while n >= 1 and m >= 2:
    n -= 1
    m -= 2
    ans += 1
if n < 1:
    ans += (m // 4)
print(ans)

### FIXED CODE ###

n, m = map(int,input().split())
print((min(n * 2, m) + m) // 4)
### BUGGY CODE ###


def abc096_d():
    import numpy as np

    n= int(input())
    nums = np.array([2, 3, 5, 7] + [i for i in range(11, 55555, 2) if i % 3 > 0 and i % 5 > 0 and i % 7 > 0])
    primes = np.array([], dtype=int)

    for val in nums:
        mod = val % nums
        if np.sum(mod == 0) == 1:
            primes = np.append(primes, val)

    ans = np.random.choice(primes,n)
    return ans


print(abc096_d())

### FIXED CODE ###

def abc096_dx():
    n = int(input())
    primes = [2, 3]

    for num in range(5, 55555, 2):
        is_prime = True
        for i in range(1, len(primes)):
            if primes[i] ** 2 > num:
                break
            if num % primes[i] == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)

    ans = []
    for num in primes:
        if num % 5 == 1:
            ans.append(str(num))
        if len(ans) == n:
            break
    return " ".join(ans)
print(abc096_dx())
### BUGGY CODE ###

def solve(N,K,A):
    for i in range(K):
        arr = [0] * (N + 1)

        for ind,j in enumerate(A):
            arr[max(ind-j,0)] += 1
            arr[min(ind+j+1, N)] -= 1

        A[0] = arr[0]
        for k in range(N-1):
            A[k+1] = A[k] + arr[k+1]

        if arr[0] ==N and arr[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = solve(n,k,a)
    print(*ans)



### FIXED CODE ###

import numpy as np
from numba import njit

@njit('i8,i8,i8[::1]',cache=True)
def solve(N,K,A):
    for i in range(K):
        br = np.zeros(N+1, dtype=np.int64)

        for ind, rux in enumerate(A):
            br[max(ind-rux,0)] += 1
            br[min(ind+rux+1,N)] -= 1
        A = br.cumsum()[:-1]

        if br[0] == N and br[-1] == -N:
            return A
    return A


if __name__ == "__main__":
    n,k = map(int, input().split())
    a = np.array(list(map(int, input().split())),dtype=np.int64)
    ans = solve(n,k,a)
    print(*ans)
### BUGGY CODE ###

N = int(input())
X = int(input(),2)
for i in range(1,N+1):
    xi = X ^ (1<<(N-i))
    ans = 0
    while xi > 0:
        xi %= (str(bin(xi)).count('1'))
        ans += 1
    print(ans)
    ans = 0

### FIXED CODE ###

N=int(input())
X=input()
Y=int(X,2)
Z=Y
C=X.count('1')
if C==1:
  for i in range(N):
    if X[i]=='1':
      print(0)
    elif i==N-1:
      print(2)
    else:
      print(1)
  exit()
Y,Z=Y%(C+1),Z%(C-1)
def f(x):
  if x==0:
    return 0
  return 1+f(x%bin(x).count('1'))
 
for i in range(N):
  if X[i]=='1':
    print(1+f((Z-pow(2,N-i-1,C-1))%(C-1)))
  else:
    print(1+f((Y+pow(2,N-i-1,C+1))%(C+1)))
### BUGGY CODE ###

from collections import deque

def resolve():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))

    q = deque()
    diffs = set()

    for i in range(n):
        if bb[i] != aa[i]:
            diffs.add(i)

        bef_i = i-1 if i > 0 else n-1
        aft_i = i+1 if i < n-1 else 0
        if bb[i] > aa[i] and bb[i] > bb[bef_i] + bb[aft_i]:
            q.append(i)

    count = 0

    while len(q) > 0:
        i = q.popleft()

        bef_i = i-1 if i > 0 else n-1
        bef2_i = bef_i-1 if bef_i > 0 else n-1
        aft_i = i+1 if i < n-1 else 0
        aft2_i = aft_i+1 if aft_i < n-1 else 0

        while bb[i] > aa[i] and bb[i] > bb[bef_i] + bb[aft_i]:
            bb[i] = bb[i] - bb[bef_i] - bb[aft_i]
            count += 1

        if bb[i] == aa[i]:
            diffs.remove(i)

        if bb[bef_i] > aa[bef_i] and bb[bef_i] > bb[bef2_i] + bb[i]:
            q.append(bef_i)

        if bb[aft_i] > aa[aft_i] and bb[aft_i] > bb[aft2_i] + bb[i]:
            q.append(aft_i)

    if len(diffs) > 0:
        print(-1)
        return

    print(count)
resolve()

### FIXED CODE ###

from collections import deque

def resolve():
    n = int(input())
    aa = list(map(int, input().split()))
    bb = list(map(int, input().split()))

    q = deque()
    diffs = set()

    for i in range(n):
        if bb[i] != aa[i]:
            diffs.add(i)

        bef_i = i-1 if i > 0 else n-1
        aft_i = i+1 if i < n-1 else 0
        if bb[i] > aa[i] and bb[i] > bb[bef_i] + bb[aft_i]:
            q.append(i)

    count = 0

    while len(q) > 0:
        i = q.popleft()

        bef_i = i-1 if i > 0 else n-1
        bef2_i = bef_i-1 if bef_i > 0 else n-1
        aft_i = i+1 if i < n-1 else 0
        aft2_i = aft_i+1 if aft_i < n-1 else 0

        count += (bb[i] - aa[i]) // (bb[bef_i] + bb[aft_i])
        bb[i] = (bb[i] - aa[i]) % (bb[bef_i] + bb[aft_i]) + aa[i]

        if bb[i] == aa[i]:
            diffs.remove(i)

        if bb[bef_i] > aa[bef_i] and bb[bef_i] > bb[bef2_i] + bb[i]:
            q.append(bef_i)

        if bb[aft_i] > aa[aft_i] and bb[aft_i] > bb[aft2_i] + bb[i]:
            q.append(aft_i)

    if len(diffs) > 0:
        print(-1)
        return

    print(count)
resolve()
### BUGGY CODE ###

from functools import cmp_to_key
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
*C, = map(int, input().split())

Q = [tuple(map(int, input().split())) for _ in range(P)]
Q = [(i, l, r) for i, (l, r) in enumerate(Q)]

block = int(N**0.5)


def compare(a, b):
    _, la, ra = a
    _, lb, rb = b
    if (la-1)//block != (lb-1)//block:
        return -1 if (la-1)//block < (lb-1)//block else 1
    return -1 if ra < rb else 1


Q.sort(key=cmp_to_key(compare))

ans = [0]*P
cl = cr = 0
S = dict()
S[C[0]] = set([0])
cnt = 1
for i, l, r in Q:
    l -= 1
    r -= 1
    while cl < l:
        x = C[cl]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cl)
        cl += 1

    while l < cl:
        x = C[cl-1]
        if x in S:
            S[x].add(cl-1)
        else:
            S[x] = set([cl-1])
            cnt += 1
        cl -= 1

    while cr < r:
        x = C[cr+1]
        if x in S:
            S[x].add(cr+1)
        else:
            S[x] = set([cr+1])
            cnt += 1
        cr += 1

    while r < cr:
        x = C[cr]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cr)
        cr -= 1

    ans[i] = cnt

print('\n'.join(map(str, ans)))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-sum(A, r)

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


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

import heapq

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

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

b = [0] * m
c = [0] * m
for i in range(m):
    b[i], c[i] = map(int,input().split())

#print(a)

heapq.heapify(a)
#print(a)

for j in range(m):
    for k in range(b[j]):
        if a[0] > c[j]:
            break
        else:
            heapq.heappushpop(a,c[j])

print(sum(a))

### FIXED CODE ###

import heapq

from operator import itemgetter

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

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
#print(a)

heapq.heapify(a)
#print(a)

d = 0
count = 0

for j in range(len(info)):
    for k in range(info[j][0]):
        if a[0] > info[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,info[j][1])
            count += 1
        if count >= n:
            d = 1
            break
    if d == 1:
        break

print(sum(a))
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7


class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

    def __str__(self):
        return str(self.num)

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [ModInt(1, mod)]
        self.inverse = [ModInt(1, mod)]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * ModInt(i, mod))
            self.inverse.append(self.inverse[-1] * ModInt(i, mod).inverse())

    def comb(self, n, k):
        if k < 0 or n < k:
            return ModInt(0, self.mod)

        return self.fact[n] * self.inverse[k] * self.inverse[n-k]


mx = min(k, n - 1)
comb = Combination(n, mod)
ans = ModInt(0, mod)

for i in range(mx + 1):
    ans += comb.comb(n, i) * comb.comb(n - 1, i)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 2 * 2 * 10 ** 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


mx = min(k, n - 1)
ans = 0
for i in range(mx + 1):
    ans += cmb(n, i, mod) * cmb(n - 1, n - i - 1, mod)
    ans %= mod

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

import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

def solve(A):
    A = [abs(x-y) for x,y in zip(A,A[1:])]
    n = len(A)
    coef = 1
    for i in range(n-1):
        coef = coef ^ (coef << 1)
    coef = map(int, bin(coef)[2:])
    if 1 in A:
        B = [x % 2 for x in A]
        ans = reduce(xor, starmap(mul, zip(B,coef)))
    else:
        B = [x // 2 for x in A]
        ans = reduce(xor, starmap(mul, zip(B,coef)))*2
    return ans 

print(solve(A))



### FIXED CODE ###

import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

A = [abs(x-y) for x,y in zip(A,A[1:])]
n = len(A)
# Lucas
coef = [((n-1)&k)==k for k in range(n)]
if 1 in A:
    B = [x % 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))
else:
    B = [x // 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))*2

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

from functools import reduce
from fractions import gcd
from collections import Counter


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
l = least_common_multiple(list(c.keys()))
ans = 0
MOD = 10**9+7
for k, v in c.items():
    ans = (ans + l // k * v) % MOD
print(ans)


### FIXED CODE ###

from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)
### BUGGY CODE ###

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

def calc():
    total = 0
    for i in range(N):
        a = nums[i]
        b = sum(nums[i+1:])
        total += a*b
    return total

print(calc() % (1000000000+7))


### FIXED CODE ###

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

total = 0
sums = []
tmp = 0

for i in range(1, N):
    tmp += nums[N-i]
    sums.append(tmp)

for i in range(N-1):
    a = nums[i]
    b = sums[N-(i+2)]
    total += a*sums[N-(i+2)]

print(total % (1000000000+7))
### BUGGY CODE ###

n = int(input())
a = []
hist = []
for i in range(n):
    a.append(int(input()))
pos = 1
count = 0
while True:
    if pos == 2:
        print(count)
        break
    if pos in hist:
        print(-1)
        break
    hist.append(pos)
    pos = a[pos-1]
    count += 1

### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
ans = 0
turn = 1
while True:
    if a[turn-1] == 2:
        ans += 1
        break
    if a[turn-1] == 0:
        ans = -1
        break
    next_turn = a[turn-1]
    a[turn-1] = 0
    ans += 1
    turn = next_turn

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

N = int(input())
ns = [int(input()) for _ in range(N)]

def is_prime(n):
  for m in range(2, n):
    if n % m == 0:
      return False
  return True

print(len([n for n in ns if is_prime(n)]))

### FIXED CODE ###

N = int(input())
ns = [int(input()) for _ in range(N)]

#primes = set()
#def is_prime(n):
#  if n in primes:
#    return True
#
#  for m in range(2, n):
#    if is_prime(m) and n % m == 0:
#      return False
#
#  primes.add(n)
#  return True

# Proof:
# if n < d ^ 2 and n mod d = 0;
# n = ad (a in N)
# ad < d ^ 2
# a < d
# QED

def is_prime(n):
  if n < 2: return False
  if n == 2: return True
  if n % 2 == 0: return False

  d = 3
  while d ** 2 <= n:
    if n % d == 0:
      return False
    d += 2
  return True

print(len([n for n in ns if is_prime(n)]))
### BUGGY CODE ###

#B - Frog 2
#
#

n,k=map(int,input().split())
h = list(map(int,input().split()))
#h[i]は足場[i+1]の高さ

dp = [0]*n

#dp[n-1]まで埋めれば良い

for i in range(n):
    ck=[]
    for j in range(1,k+1):
        #足場i+1までにたどり着くためのコストを考える
        #i~i-k（c[i-1]~c[i-k-1]）の足場からの飛び移り方を考える
        if i-j >= 0:
            ck.append(dp[i-j]+abs(h[i]-h[i-j]))
    if len(ck) ==0:
        dp[i] = 0
    else:
        dp[i] = min(ck)
print(dp[n-1])

### FIXED CODE ###

#B - Frog 2
#TLE
#

n,k=map(int,input().split())
h = list(map(int,input().split()))
#h[i]は足場[i+1]の高さ

dp = [0]*n

#dp[n-1]まで埋めれば良い

for i in range(1,n):
    c_min=float("inf")
    c_kh=float("inf")
    for j in range(1,k+1):
        #足場i+1までにたどり着くためのコストを考える
        #i~i-k（c[i-1]~c[i-k-1]）の足場からの飛び移り方を考える
        if i-j >= 0:
            c_kh = dp[i-j]+abs(h[i]-h[i-j])
            if c_kh < c_min:
                c_min = c_kh
        dp[i] = c_min
print(dp[n-1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort()
#print(ki)

kid = deque(ki)
#print(kid)

ver = []
for i in range(N):
    ver.append([0,False])
 
for i in range(Q):
    ver[co[i][0]-1][0] += co[i][1]

ver[0][1] = True
#print(ver)


while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

for i in range(N):
    print(ver[i][0],end=' ')


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


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

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

counter = 0
for i in range(n):
  for j in range(i):
    if P[i] > P[j]:
      break
  else:
    counter += 1
print(counter)

### FIXED CODE ###

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

min_val = P[0]
counter = 0
for i in range(n):
  min_val = min(P[i], min_val)
  if min_val == P[i]:
    counter += 1
print(counter)
### BUGGY CODE ###

n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0
keys = []

def get_key(n1, n2):
  if n1 > n2:
    return str(n2) + '-' + str(n1)
  return str(n1) + '-' + str(n2)

for _ in range(n - 1):
  a, b = map(int, input().split())
  keys.append(get_key(a - 1, b - 1))
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [root]
checked = set()
result = {}

while len(queue) > 0:
  node = queue.pop(0)
  # print(node + 1)
  ks = list(range(color_num))
  for node2 in G[node]:
    key = get_key(node, node2)
    if key in result:
      ks.pop(result[key])
  for node2 in G[node]:
    if node2 not in checked:
      key = get_key(node, node2)
      result[key] = ks.pop(0)
      queue.append(node2)
  checked.add(node)

for k in keys:
  print(result[k] + 1)


### FIXED CODE ###

n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0

for i in range(n - 1):
  a, b = map(int, input().split())
  G[a - 1].append((b - 1, i))
  G[b - 1].append((a - 1, i))
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [(root, -1)]
checked = set()
answer = [-1] * (n - 1)

while len(queue) > 0:
  node, c = queue.pop(0)
  color = 1
  for node2, index in G[node]:
    if node2 not in checked:
      if color == c:
        color = c + 1
      answer[index] = color
      color += 1
      queue.append((node2, answer[index]))
  checked.add(node)
print('\n'.join(map(str, answer)))