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

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

bestSeq = 0
index2 = -1

for i, b in enumerate(brick):
  seq = 0
  if b == 1:
    if i < index2:
      continue
    seq += 1
    cur = 2
    for j, c in enumerate(brick[i:]):
      if c == cur:
        seq += 1
        cur += 1
        index2 = j
    if seq > bestSeq:
      bestSeq = seq

if bestSeq == 0:
  print(-1)
else:
  print(numN - bestSeq)


### FIXED CODE ###

numN = int(input())
input_line = input().split(' ')
brick = [int(i) for i in input_line]

seq = 0

for i, b in enumerate(brick):
  if b == 1:
    seq += 1
    cur = 2
    for c in brick[i + 1:]:
      if c == cur:
        seq += 1
        cur += 1
    break

if seq == 0:
  print(-1)
else:
  print(numN - seq)
### BUGGY CODE ###

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

Max = 0
for x in range(1, n + 1):
    Max = max(Max, (a * x) // b - a * (x // b))
print(Max)


### FIXED CODE ###

def f(a, b, n):
    if b == 1:
        print(0)
    else:
        Max = 0
        step = 1 if b // a ==  0 else b // a
        for x in range(b // a, n + step, step):
            res = (a * x) // b - a * (x // b)
            if res > Max:
                Max = res
        print(Max)

a, b, n = map(int, input().split()); f(a, b, n)
### BUGGY CODE ###

from collections import deque
N = int(input())
T = sorted(list(set([int(input()) for _ in range(N)])), reverse=True)
ret = 1
while len(T) > 1:
  C = int(max(T) ** 0.5)
  f = False
  for c in range(2, C + 1):
    T_ = deque([])
    for i, t in enumerate(T):
      if t % c == 0:
        T_.append(t // c)
        f = True
      elif t < c:
        ret *= t
      else:
        T_.append(t)
    T = sorted(list(set([t for t in T_ if t >= c])), reverse=True)
    if f:
      ret *= c
      break
  else:
    break
for t in T:
  ret *= t
print(ret)

### FIXED CODE ###

from collections import deque
N = int(input())
T = list(set([int(input()) for _ in range(N)]))
ret = T[0]

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

for t in T[1:]:
  ret = ret * t // gcd(ret, t)
  
print(ret)
### BUGGY CODE ###

import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

n, k = map(int, sys.stdin.readline().split())
w = [int(sys.stdin.readline()) for _ in range(n)]

wsum = sum(w)

p = max(int(math.ceil(wsum / k)), max(w))
pre_f = p -1
pre_s = None

while True:
    if loadable(w, n, k, p, wsum):
        if p - pre_f == 1:
            break
        pre_s = p
        p = int((p + pre_f) /2)
    else:
        pre_f = p
        if pre_s:
            p = int((pre_s + p) / 2)
        else:
            p = math.ceil(p * 1.01)
    
print(p)

### FIXED CODE ###

import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

n, k = map(int, sys.stdin.readline().split())
w = [int(sys.stdin.readline()) for _ in range(n)]

wsum = sum(w)

p = max(int(math.ceil(wsum / k)), max(w))
pre_f = p -1
pre_s = None

while True:
    if loadable(w, n, k, p, wsum):
        pre_s = p
    else:
        pre_f = p

    if pre_s != None and pre_s - pre_f == 1:
            break
    
    if pre_s:
        p = int((pre_s + pre_f) / 2)
    else:
        p = math.ceil(p * 1.01)
    
print(pre_s)
### BUGGY CODE ###

# https://atcoder.jp/contests/hitachi2020/submissions/10704509

def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  # namedtupleやめた,coef,const

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = {0}
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  # le->lt,continue->break,restは狭義単調減少
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/hitachi2020/submissions/10704509

def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 30
    L = 30

    N, T = map(int, input().split())

    ps = []
    coef_0 = []
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0:
            coef_0.append(b + 1)
        else:
            ps.append((a, b))  # namedtupleやめた,coef,const

    ps.sort(key=lambda p: p[0] / (p[1] + 1), reverse=True)
    coef_0.sort()

    dp = [inf] * (L + 1)
    dp[0] = 0
    for coef, const in ps:
        for visited in reversed(range(L)):
            dp[visited + 1] = min(
                dp[visited + 1],
                (dp[visited] + 1) * (coef + 1) + const
            )

    def accumulate(a):
        s = 0
        yield s  # start=x->0
        for x in a:
            s += x
            yield s

    *acc, = accumulate(coef_0)

    ans = {0}
    cnt = len(acc) - 1
    for visited, consumption_time in enumerate(dp):
        rest = T - consumption_time
        if rest < 0: break  # le->lt,continue->break,restは狭義単調減少
        while cnt > 0 and acc[cnt] > rest:  # bisect_right->しゃくとり
            cnt -= 1
        ans.add(visited + cnt)
    print(max(ans))


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

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

calc_A = [0]
calc_B = [0]

for i in range(N):
    calc_A.append(calc_A[i] + A[i])

for j in range(M):
    calc_B.append(calc_B[j] + B[j])

ans = 0

for i in range(N+1):
    j = M
    if calc_A[i] > K:
        break
    while calc_B[j] > K - calc_A[i]:
        if j > 0:
            j -= 1
        else:
            break
    if ans < i + j:
        ans = i + j

print(ans)

### FIXED CODE ###

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

check_A = [0]
check_B = [0]

for a in range(N):
    check_A.append(check_A[a] + A[a])

for b in range(M):
    check_B.append(check_B[b] + B[b])

ans = 0
j = M

for i in range(N+1):
    if check_A[i] > K:
        break
    while check_B[j] > K - check_A[i]:
        j -= 1
    ans = max(ans, i+j)

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

k = input()
K = int(k)
j = 1
count = 0
while True:
    a = 0
    j = str(j)
    for i in range(len(j)):
        a += int(j[i:i+1])
    j = int(j)
    if j/a < 2:
        print(j)
        count += 1
    if count == K:
        break
    j += 1

### FIXED CODE ###

K = int(input())

a = 1
b = 0

def snk(n):
    s = 0
    for i in str(n):
        s += int(i)
    return(n/s)
    
count = 0
while True:
    print(a)
    count += 1
    if snk(a + 10 ** b) > snk(a + 10 ** (b + 1)):
        b += 1
    a += 10 ** b
    if count == K:
        break
### BUGGY CODE ###

N,K=map(int,input().split())
cnt=0
while N//K>=1:
        cnt += 1
print(cnt+1)

### FIXED CODE ###

N,K=map(int,input().split())
cnt=0
for i in range(1,100):
        if N/(K**i)>=1:
                cnt += 1
print(cnt+1)
### BUGGY CODE ###

from scipy.sparse.csgraph import shortest_path
import numpy as np
n, x, y = map(int, input().split())
ans = [0] * (n - 1)
table = []
for i in range(n):
    l = [0] * n
    if i + 1 < n:
        l[i + 1] = 1
    if i - 1 > -1:
        l[i - 1] = 1
    if i == x - 1:
        l[y - 1] = 1
    if i == y - 1:
        l[x - 1] = 1
    table.append(l)
a = shortest_path(np.array(table))
a = a.flatten().tolist()
for i in range(n - 1):
    ans[i] += a.count(i + 1)
ans = list(map(lambda x: x // 2, ans))
ans[-1] = 0
for i in range(n - 1):
    print(ans[i])


### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0] * n
for i in range(1, n + 1):
  for j in range(i + 1, n + 1):
    d = min(j - i, abs(i - x) + abs(j - y) + 1)
    ans[d] += 1
    
for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

n=int(input())
List=list(map(int,input().split()))
ans=[]
for i in range(n):
    if((i%2)!=(n%2)):
        ans.insert(0, List[i])
    else:
        ans.append(List[i])
print(' '.join(map(str,ans)))

### FIXED CODE ###

from collections import deque
n=int(input())
List=input().split()
ans=deque()
for i in range(n):
    if((i%2)!=(n%2)):
        ans.appendleft(List[i])
    else:
        ans.append(List[i])
print(' '.join(map(str,ans)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[1], reverse=True)

def dfs(i, sum, time, remain):
    global answer
    if i == N:
        if time < T and len(remain) >= 1:
            sum += AB[min(remain)][1]
        if sum > answer:
            answer = sum
    else:
        dfs(i+1, sum, time, remain)
        if time < T:
            dfs(i+1, sum + AB[i][1], time + AB[i][0], remain-{i})

answer = 0
dfs(0, 0, 0, set(range(N)))
print(answer)

### FIXED CODE ###

import sys
import numpy as np

n, t = map(int, input().split())
knapsack = np.zeros(t, dtype=np.int64)
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
tmp_ans = 0
for a, b in cuisines:
    tmp_ans = max(tmp_ans, knapsack.max() + b)
    knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b)
print(tmp_ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [tuple(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))


### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: (x[0],x[1]))
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))
### BUGGY CODE ###

N,M=map(int,input().split())
alist=list(map(int,input().split()))

alist.sort()
cblist = []
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
  
cblist.sort(reverse=True)
#print(alist)
#print(cblist)

for (C,B) in cblist:
  for i in range(B):
    alist[i] = max(alist[i],C)
  
  alist.sort()
  
#print(alist)
print(sum(alist))

### FIXED CODE ###

N,M=map(int,input().split())
alist=list(map(int,input().split()))

alist.sort()
cblist = []
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
  
cblist.sort(reverse=True)
#print(alist)
#print(cblist)

index = 0
for (C,B) in cblist:
  for i in range(index,index+B):
    if i == len(alist):
      break
    
    if alist[i] < C:
      alist[i] = C
    else:
      break
      
  index += B
  if index >= len(alist):
    break
  
#print(alist)
print(sum(alist))
### BUGGY CODE ###

from collections import defaultdict
from itertools import combinations
dic = defaultdict(lambda : 0)
n = int(input())
for _ in range(n):
    str = ''.join(sorted(input()))
    dic[str] += 1
count = 0
memos = defaultdict(lambda : 0)
for key in dic.keys():
    value = dic[key]
    if not value in memos.keys():
        x = len([i for i in combinations(range(value),2)])
        memos[value] = x
    else:
        x = memos[value]
    count += x
print(count)

### FIXED CODE ###

from collections import defaultdict
dic = defaultdict(lambda : 0)
n = int(input())
for _ in range(n):
    str = ''.join(sorted(input()))
    dic[str] += 1
count = 0
memos = defaultdict(lambda : 0)
for key in dic.keys():
    value = dic[key]
    if not value in memos.keys():
        x = value*(value-1)/2
        memos[value] = int(x)
    else:
        x = memos[value]
    count += x
print(int(count))
### BUGGY CODE ###

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

re = 1
for i in range(1, M):
    if M % i == 0:
        a = M // i
        if a >= N:
            re = i
        else:
            break
print(re)  

### FIXED CODE ###

def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop() 
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

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

if M == 1:
    print(1)
else:
    re = 1
    fa = factorize(M)
    div_list = divisorize(fa)

    for i in range(len(div_list)):
        num = 1
        for j in range(len(div_list[-1 - i])):
            l = div_list[-1-i][j]
            num *= l[0] ** l[1]
        d = M // num 
        if d >= N and num > re:
            re = num
    print(re)
### BUGGY CODE ###

from bisect import insort_left
from sys import stdin

def main():
    input = stdin.readline
    n = int(input())
    
    d = {}
    ds = d.setdefault
    m = 1
    for i in range(n):
        s = input().rstrip()
        ds(s, 0)
        d[s] += 1
        if m < d[s]:
            m = d[s]
    
    l = []
    for i, j in d.items():
        if j == m:
            insort_left(l, i)
            
    print("\n".join(l))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())

l = [input() for i in range(n)]

c = Counter(l)

ml = c.most_common()
mc = ml[0][1]

ml.sort()

for i in ml:
    if i[1] == mc:
        print(i[0])
### BUGGY CODE ###

n,a,b= map(int,input().split())
sh = sorted([int(input()) for i in range(n)],reverse=True)
sumh = sum(sh)
def nibu(t):
    rt=0
    for i in range(n):
        temp = -1*(-1*max(0,sh[i]-t*b)//(a-b))
        if temp>0:rt+=-1*(-1*max(0,sh[i]-t*b)//(a-b))
        else:break
    return True if t>=rt else False
l=max(sh)//a
r=max(sh)//b+1
while r-l!=1:
    m = (l+r)//2
    if nibu(m):r=m
    else:l=m
print(r)

### FIXED CODE ###

n,a,b= map(int,input().split())
sh = sorted([int(input()) for i in range(n)],reverse=True)
sumh = sum(sh)
def nibu(t):
    rt=0
    for i in range(n):
        temp = -1*(-1*max(0,sh[i]-t*b)//(a-b))
        if temp>0:rt+=-1*(-1*max(0,sh[i]-t*b)//(a-b))
        else:break
        if rt>t:return False
    return True if t>=rt else False
l=max(sh)//a
r=max(sh)//b+1
while r-l!=1:
    m = (l+r)//2
    if nibu(m):r=m
    else:l=m
print(r)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
if q-k<0:
    for i in range(n):
        print('Yes')
else:
    import collections
    c = collections.Counter(a)
    if c.most_common()[0][1]>=k:# and q-c.most_common()[0][1]<=k:
        a=int(c.most_common()[0][0])
        for i in range(n):
            if i+1==a:
                print('Yes')
            else:
                print('No')
    else:
        l=([int(i[0]) for i in c.items() if i[1] > q-k])
        #print(l)
        for i in range(n):
            if l.count(i+1)>0:
                print('Yes')
            else:
                print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[(input()) for l in range(q)]
#if q-k<0:
 #   for i in range(n):
  #      print('Yes')
#else:
import collections
c = collections.Counter(a)
for i in range(n):
    #print(k-c[str(i+1)])
    if q-c[str(i+1)]<k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,q = map(int,input().split())
s = str(input())

for i in range(q):
        t1,t2 = map(int,input().split())
        r1 =s[t1-1:t2]
        print(r1.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []
        minCost = -1

        minI = max(0, i - K)

        for j in range(minI, i):
            cost = dpList[j] + abs(field[i] - field[j])

            if(minCost == -1):
                minCost = cost
            elif minCost > cost:
                minCost = cost

        dpList[i] = minCost

    print(dpList[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []
        minCost = -1

        minS = max(0, i - K)

        for dpJ, fJ in zip(dpList[minS:i], field[minS:i]):
            cost = dpJ + abs(field[i] - fJ)

            if(minCost == -1):
                minCost = cost
            elif minCost > cost:
                minCost = cost

        dpList[i] = minCost

    print(dpList[-1])

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

import itertools
n,k=map(int,input().split())
aa=k/2
a=[]
b=[]
if k%2==0:
    for i in range(1,n+1):
        if i%k==0:
            a.append(i)
        elif i%k==aa:
            b.append(i)
else:
    for i in range(1,n+1):
        if i%k==0:
            a.append(i)
print(len(list(itertools.product(a,repeat=3)))+len(list(itertools.product(b,repeat=3))))


### FIXED CODE ###

import itertools
n,k=map(int,input().split())
aa=k/2
a=[]
b=[]
if k%2==0:
    for i in range(1,n+1):
        if i%k==0:
            a.append(i)
        elif i%k==aa:
            b.append(i)
else:
    for i in range(1,n+1):
        if i%k==0:
            a.append(i)
tot=len(set(a))**3+len(set(b))**3
print(tot)
### BUGGY CODE ###

S = input()
B = []
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    C = []
    A = list(map(str, input().split()))
    if len(A) == 3:
        C.append(A[2])
    if int(A[0]) == 1:
        B = B[::-1]
    else:
        if int(A[1]) == 1:
            B = C + B
        else:
            B.append(A[2])
print(''.join(B))

### FIXED CODE ###

from collections import deque

S = input()
B = deque()
res = 0
for s in range(len(S)):
    B.append(S[s])
Q = int(input())
for q in range(Q):
    A = list(map(str, input().split()))
    if int(A[0]) == 1:
        if res == 0:
            res = 1
        else:
            res = 0
    else:
        if int(A[1]) == 1:
            if res == 0:
                B.appendleft(A[2])
            else:
                B.append(A[2])
        else:
            if res == 0:
                B.append(A[2])
            else:
                B.appendleft(A[2])
if res == 0:
    print(''.join(B))
else:
    B.reverse()
    print(''.join(B))
### BUGGY CODE ###

INF = float('inf')
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N+1)
b = [0] * (M+1)
for i,x in enumerate(A):
    a[i+1] = a[i] + x

for i,x in enumerate(B):
    b[i+1] = b[i] + x

ans = 0
for i, va in enumerate(a):
    if va > K:
        break
    j = M
    while va + b[j] > K:
        #print(va, b[j], ans)
        j -= 1
        if j < 0:
            break
    ans = max(i+j, ans)
print(ans)


### FIXED CODE ###

INF = float('inf')
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = [0] * (N+1)
b = [0] * (M+1)
for i,x in enumerate(A):
    a[i+1] = a[i] + x

for i,x in enumerate(B):
    b[i+1] = b[i] + x

ans = 0
j = M
for i, va in enumerate(a):
    if va > K:
        break
    while va + b[j] > K:
        #print(va, b[j], ans)
        j -= 1
        if j < 0:
            break
    ans = max(i+j, ans)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = tuple(map(int, input().split()))

inf = float("inf")
dp = [inf] * N

dp[0] = 0

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

print(dp[N - 1])

### FIXED CODE ###

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

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

for i,h_now in enumerate(h):
    if i==0:
        continue
    x=max(0,i-K)
    dp[i]=min([dp_i+abs(h_now-h_i) for dp_i,h_i in zip(dp[x:i],h[x:i])])

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

#input()を速い方にしないとTLEになる

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
input = sys.stdin.readline

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = map(int, input().split())
    res[p] += x

dfs(1,-1)
print(*res[1:])


### FIXED CODE ###

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
### BUGGY CODE ###

import numpy as np
N = int(input())
edges = []
count = np.zeros(N)
for _ in range(N-1):
  a, b = map(int, input().split())
  edges.append([a, b])
  count[a-1] += 1
  count[b-1] += 1
  
MAX = int(np.max(count))

color = [0 for _ in range(N-1)]
used = [set() for _ in range(N)]
for _ in range(N-1):
  id = np.argmax(count)
  count[id] = 0
  id += 1
  for k, [i,j] in enumerate(edges):
    if (i != id and j != id) or color[k] != 0:
      continue
    for l in range(MAX):
      c = l+1
      if c in used[i-1] or c in used[j-1]:
        continue
      used[i-1].add(c)
      used[j-1].add(c)
      color[k] = c
      break

print(MAX)
for i in color:
  print(i)


### FIXED CODE ###

N = int(input())
edges = []
node = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  edges += (a-1, b-1),
  node[a-1] += b-1,
  node[b-1] += a-1,

stuck = [(0,0)]
f = [1]+[0]*N
color_dic = dict()
while stuck:
  v, color = stuck.pop()
  i = 0
  for w in node[v]:
    if f[w]:
      continue
    f[w] = 1
    i += 1
    if i == color:
      i += 1
    stuck += (w,i),
    color_dic[v,w] = i

ans = []
for a,b in edges:
  if (a,b) in color_dic:
    ans += color_dic[a,b],
  else:
    ans += color_dic[b,a],

print(max(ans))
for i in ans:
  print(i)