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


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


def init(n_):
    #簡単にするために2のべき乗に揃える
    n = 1
    while n <= n_:
        n *= 2
    return n

#初期化
N = int(input())
n = init(N)
data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        k = (k - 1) // 2
        data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    ans = max(ans, tmp + a)
    # print (data)

print (ans)

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

N = int(input())

power = 1
for i in range(N):
    power *= (i+1)

print(power % (10**9+7))



### FIXED CODE ###

N = int(input())

power = 1
for i in range(N):
    power *= (i+1)
    power = power % (10**9+7)

print(power)
### BUGGY CODE ###

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
ans = 1
for number in huga:
    ans = ans * number


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


### FIXED CODE ###

#intの場合
N = int(input()) #ここで標準入力

#List にしたい時
#intの場合
huga = list(map(int, input().split()))
if 0 in huga:
    print(0)
else:
    ans = 1
    flg = 0
    for number in huga:
        ans = ans * number
        if ans > 10**18:
            flg = 1
            break
    if flg == 0:
        print(ans)
    else:
        print('-1')
### BUGGY CODE ###

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

max = -1
x = 0

while(x < n):
    x += 1
    new = math.floor(a*x/b) - a * math.floor(x/b)
    #print(math.floor(a*x/b), " - ",  a * math.floor(x/b))
    #print(new)
    if max < new:
        max = new


print(max)


### FIXED CODE ###

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

if b <= n:
    x = b-1

new = math.floor(a*x/b) - a * math.floor(x/b)
print(new)
### BUGGY CODE ###

import collections
N = int(input())
s = []
ans = 0
for _ in range(N):
    c = collections.Counter(input())
    ans += s.count(c)
    s.append(c)
print(ans)


### FIXED CODE ###

import collections

from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N = int(input())
s = [" ".join(sorted(list(input()))) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for i in c.values():
    if i > 1:
        ans += cmb(i, 2)
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
li=[list(map(lambda x:int(x)+1,input().split())) for _ in range(m)]
s=set(range(li[0][0],li[0][1]+1))
for i in li:
  s = s & set(range(i[0],i[1]+1))
print(len(s))

### FIXED CODE ###

n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
l = s[0][0]
r = s[0][1]
for item in s:
  if item[0] > l:
    l = item[0]
  if item[1] < r:
    r = item[1]
if r-l+1 > 0:
  print(r-l+1)
else:
  print(0)
### BUGGY CODE ###

S=input()
Q=int(input())
for i in range(Q):
    temp=input().split()
    if len(temp)==1:
        S=S[::-1]
    else:
        if int(temp[1])==1:
            S="".join([temp[2],S])

        if int(temp[1])==2:
            S="".join([S,temp[2]])
			
print(S)


### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

Nfact = [1]
NfactRev = []
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
    if A.count(i) == 2:
        Double = [j for j, x in enumerate(A) if x == i]
NfactRev.append(Pow(Nfact[N+1], mod-2))
for i in range(1, N+1):
    NfactRev.append(NfactRev[i-1] * (N+2-i) % mod)
NfactRev.append(1)

doublearray = N - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[-(N+2-i)] * NfactRev[-(i+1)] % mod
    if i <= doublearray+1:
        double = Nfact[doublearray] * NfactRev[-(doublearray-i+2)] * NfactRev[-i] % mod
    else:
        double = 0
    print(whole - double)

### FIXED CODE ###

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9
num = [-1 for i in range(N)]
for i, a in enumerate(A):
    if num[a-1] == -1:
        num[a-1] = i
    else:
        Double = [num[a-1], i]

Nfact = [1]
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
NfactRev = [Pow(Nfact[N+1], mod-2)]
for i in range(1, N+1):
    NfactRev.append(NfactRev[i-1] * (N+2-i) % mod)
NfactRev.append(1)
NfactRev.reverse()

doublearray = N + 1 - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[N+1-i] * NfactRev[i] % mod
    if i <= doublearray:
        double = Nfact[doublearray-1] * NfactRev[doublearray-i] * NfactRev[i-1] % mod
    else:
        double = 0
    print((whole - double) % mod)
### BUGGY CODE ###

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

count = 0
for l in range(N):
    total = 0
    xor = 0
    for r in range(l, N):
        total += A[r]
        xor ^= A[r]
        if total == xor:
            count += 1
        else:
            break

print (count)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = []
C = []

count = 0
for a in A:
    if a != 0:
        if count != 0:
            B.append(0)
            C.append(count)
        B.append(a)
        C.append(1)
        count = 0
    else:
        count += 1
if count != 0:
    B.append(0)
    C.append(count)

# print (A)
# print (B)
# print (C)
N = len(B)

count = 0
for l in range(N - 1):
    tmp = C[l] #スタート地点の数
    tmp_count = 0
    total = B[l]
    xor = B[l]
    for r in range(l + 1, N):
        total += B[r]
        xor ^= B[r]
        if total == xor:
            tmp_count += C[r]
        else:
            break
    # print (tmp_count, tmp)
    count += tmp_count * tmp
    count += (tmp * (tmp + 1)) // 2
    # print (count)

count += (C[-1] * (C[-1] + 1)) // 2

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

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

if N%K == 0:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:

    for i in range(18):
        k = K*(10**(17-i))
        while N>=k:
            k=k+K*(10**(17-i))
        k = k-K*(10**(17-i))
    k = k+K
    if k-N<N-(k-K):
        print(k-N)
    else:
        print(N-(k-K))


### FIXED CODE ###

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

if N%K == 0:
    print(0)

elif N<K and N<=K-N:
    print(N)

elif N<K and N>K-N:
    print(K-N)

elif N>K:
    if K-(N%K)>N%K:
        print(N%K)
    else:
        print(K-(N%K))
### BUGGY CODE ###

number = int(input())
score = list(map(int,input().split()))
cancel = 0
for i in range(number):
    if score.count(score[i]) != 1:
        cancel = 1
        break
if cancel == 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

number = int(input())
score = list(map(int,input().split()))
score.sort()
cancel = 0
for i in range(number-1):
    if score[i] == score[i+1]:
        cancel = 1
        break
if cancel == 1:
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
counter=0
for t in range(N):
  for i in range(t+1,N):
    for p in range(i+1,N):
      if L[p]<L[t]+L[i] and L[t]<L[i]+L[p] and L[i]<L[p]+L[t]:
        counter+=1
print(counter)

### FIXED CODE ###

import bisect
counter=0
N=int(input())
L=sorted(list(map(int,input().split())))
for a in range(N-2):
  for b in range(a+1,N-1):
    k=bisect.bisect_left(L,L[a]+L[b])
    counter+=k-b-1
print(counter)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

total = sum(A)

for i in range(Q):
    A = [C[i] if x == B[i] else x for x in A]
    print(sum(A))


### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

max_num = max(max(A), max(B), max(C))

NUM = [0] * (max_num + 1)

num_list = []

for a in A:
    NUM[a] += 1

total = sum(A)

for i in range(Q):

    total += (C[i] - B[i]) * NUM[B[i]]
    NUM[B[i]], NUM[C[i]] = 0, NUM[B[i]] + NUM[C[i]]

    print(total)
### BUGGY CODE ###

s = input()
n = int(input())
for i in range(n):
    q = input().split()
    if len(q) == 1:
        s = s[::-1]
    else:
        if q[1] == "1":
            s = q[2] + s
        else:
            s = s + q[2]

print(s)

### FIXED CODE ###

str = input()
Q = int(input())
left = []
right = []
flag = 1
for _ in range(Q):
    line = input().split()
    op1 = int(line[0])
    if op1 == 1:
        flag = -flag
    else:
        op2 = int(line[1])
        char = line[2]
        if (op2 == 1 and flag == 1) or (op2 == 2 and flag == -1) :
            left.append(char)
        else:
            right.append(char)

if flag == -1:
    right.reverse()
    str = str[::-1]
    str = "".join(right) + str
    str += "".join(left)
else:
    left.reverse()
    str = "".join(left) + str
    str += "".join(right)

print(str)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

MOD = 1000000007


def main():
    n, m = [int(i) for i in input().split()]
    a = [int(input()) for _ in range(m)]
    steps = [0] * (n + 1)
    steps[0] = 1

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now]
                steps[next_] %= MOD
    print(steps[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 1000000007


def main():
    n, m = [int(i) for i in input().split()]
    a = {int(input()) for _ in range(m)}
    steps = [0] * (n + 1)
    steps[0] = 1

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now] % MOD
                steps[next_] %= MOD
    print(steps[-1])


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

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

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

F = []
for i in range(K+1):
    count = 0
    for j in range(N):
        count += i^A[j]
    F.append(count)
print(max(F))

### FIXED CODE ###

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

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

B = [0]*41

for i in range(N):
    for j in range(41):
        if (A[i]>>j) & 1 == 1:
            B[j] += 1
#print(B)

C = [0]*41
for i in range(41):
    if (K>>i) & 1 == 1:
        C[i] += 1
#print(C)
D =[]
for i in range(40,-1,-1):
    count = 0
    if C[i] == 1:
        count += B[i]*2**i
        for k in range(40,i,-1):
            if C[k] == 0:
                count += B[k]*2**k
            else:
                count += (N-B[k])*2**k
        for j in range(i):
            if N-B[j] >= B[j]:
                count += (N-B[j])*2**j
            else:
                count += B[j]*2**j
    D.append(count)
score = 0
for i in range(41):
    if C[i] == 0:
        score += B[i]*2**i
    else:
        score += (N-B[i])*2**i
D.append(score)
#print(D)
print(max(D))
### BUGGY CODE ###

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

for i in range(q):
    cnt = 0
    l, r = map(int, input().split())
    for i in range(l-1, r-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                cnt += 1
    print(cnt)

### FIXED CODE ###

N,Q=map(int,input().split()) 
S=input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[i for i in range(1,N+1)]
for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        if b in A:
            A.remove(b)
    elif H[b-1]>H[a-1]:
        if a in A:
            A.remove(a)
    else:
        if a in A:
            A.remove(a)
        if b in A:
            A.remove(b)

print(len(A))

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[i for i in range(N)]
B=[]
for i in range(M):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        B.append(b)
    elif H[b-1]>H[a-1]:
        B.append(a) 
    else:
        B.append(a)
        B.append(b)

B=list(set(B))
print(len(A)-len(B))
### BUGGY CODE ###

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

result = n
for i in range(n):
    temp = s[:i].count("W") + s[i:].count("E")
    if temp < result:
        result = temp

print(result)

### FIXED CODE ###

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

result = s[1:].count("E")
temp = result
for i in range(n-1):
    if s[i] == "W":
        temp += 1
    if s[i+1] == "E":
        temp -= 1
    if temp < result:
        result = temp

print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

# お約束
INF = float("inf")
MOD = int(1e9 + 7)

N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

sum_val = [0] * N
for p, x in PX:
	p, x = p - 1, x
	sum_val[p] += x

edges = [[] for _ in range(N)]
for a, b in AB:
	a, b = a - 1, b - 1
	edges[a] += [b]
	edges[b] += [a]

visited = [False] * N
vals = [0] * N

def dfs(v, p, add_val):
	global visited, vals
	visited[v] = True
	vals[v] = add_val + sum_val[v]
	for n in edges[v]:
		if visited[n]: continue
		dfs(n, v, add_val + sum_val[v])

dfs(0, -1, 0)
for v in vals:
	print(v)


### FIXED CODE ###

import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def int1(n):
    return int(n) - 1
def input():
    return next(args)
def parse(*params):
    if len(params) == 1:
        return params[0](next(args))
    return tuple(p(v) for p, v in zip(params, next(args).split()))
def debug(*v):
    if __debug__:
        print(*v, file=sys.stderr)

# エントリーポイント
def main():
    N, Q = parse(int, int)
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = parse(int1, int1)
        edges[a] += [b]
        edges[b] += [a]
    vals = [0] * N
    for _ in range(Q):
        p, x = parse(int1, int)
        vals[p] += x

    counter = [0] * N
    que = [(0, 0)]
    alr = [False] * N
    while que:
        v, x = que.pop()
        alr[v] = True
        counter[v] += x + vals[v]
        for n in edges[v]:
            if not alr[n]:
                que.append((n, counter[v]))

    for v in counter:
        print(v)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split("\n"))
    main()
### BUGGY CODE ###

import sys

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

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B.sort()
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)


### FIXED CODE ###

import sys

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

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [None] * (H * W + 1)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B[H * W] = (0, (-1, -1))
B = sorted(B, key=lambda x: x[0])
costs = [0] * (H * W + 1)
for i in range(H * W, 0, -1):
    if i + D <= H * W:
        costs[i] = costs[i + D] + abs(B[i][1][0] - B[i + D][1][0]) + abs(B[i][1][1] - B[i + D][1][1])

for i in range(int(input())):
    l,r = [int(_) for _ in input().split()]
    print(costs[l] - costs[r])
### BUGGY CODE ###

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

for i in range(M):
  L, R = map(int, input().split())
  pass_card = [i for i in range(L, R+1)]
  if  i == 0:
    ans = pass_card
  elif i > 0:
    ans = set(ans) & set(pass_card)

print(len(ans))

### FIXED CODE ###

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

L_list = []
R_list = []
for i in range(M):
  L, R = map(int, input().split())
  L_list.append(L)
  R_list.append(R)

L = max(L_list)
R = min(R_list)

if R < L:
  print(0)
else:
  print(R - L + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,t = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]

dp1 = [[0 for i in range(n+1)] for j in range(t+1)]
dp2 = [[0 for i in range(n+1)] for j in range(t+1)]

q = 0
for i in range(1,n+1):
    q = max(q,data[i-1][0])
    dp2[1][i] = q

for i in range(1,t+1):
    for j in range(1,n+1):
        if i-data[j-1][0] >= 0:
            dp1[i][j] = max(dp1[i][j-1],dp1[i-data[j-1][0]][j-1]+data[j-1][1])
            dp2[i][j] = max(dp2[i][j-1],dp2[i-data[j-1][0]][j-1]+data[j-1][1],dp1[i-1][j-1]+data[j-1][1])
        else:
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = max(dp2[i][j-1],dp1[i-1][j-1]+data[j-1][1])


print(dp2[t][n])

### FIXED CODE ###

n,t = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]

dp1 = [[0 for i in range(n+1)] for j in range(t+1)]
dp2 = [[0 for i in range(n+1)] for j in range(t+1)]

q = 0
for i in range(1,n+1):
    q = max(q,data[i-1][0])
    dp2[1][i] = q

for i in range(1,t+1):
    for j in range(1,n+1):
        if i-data[j-1][0] >= 0:
            dp1[i][j] = max(dp1[i][j-1],dp1[i-data[j-1][0]][j-1]+data[j-1][1])
            dp2[i][j] = max(dp2[i][j-1],dp2[i-data[j-1][0]][j-1]+data[j-1][1],dp1[i-1][j-1]+data[j-1][1])
        else:
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = max(dp2[i][j-1],dp1[i-1][j-1]+data[j-1][1])


print(dp2[t][n])
### BUGGY CODE ###


#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(N-1)]
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i] =a,b            #色を出力するため

#色の数(各頂点の最大値)
color_max =0
root =0
for i,v in connection.items():
    if color_max < len(v) :
        color_max =len(v)
        root =i         #枝が一番多い所を根 ⇒スタート

#各頂点に色を準備⇒辺の色決定
aa=[]
color =0                                 #辺に塗る色の候補
node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
edge ={}
for a,b in A:
    edge[(a,b)] =-1                   #辺の色 -1で初期化
now_set =set() #=start
now_set.add(root) #=start
next =set()
next_next =set()
passed ={i:False for i in range(1,N+1)}
count =0
while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
    for now in now_set: #幅優先探索
        next =connection[now]
        for nex_2 in next:
            count =0
            if node[now] !=[]:
                color =node[now][-1] +1
            while count < color_max:
                q,color =divmod(color,color_max)
                if color not in node[now] and color not in node[nex_2]:
                    n1,n2=0,0
                    if now > nex_2:
                        n1,n2 =nex_2,now
                    else:
                        n1,n2 =now,nex_2
                    edge[(n1,n2)] =color +1  #辺の色決定
                    node[now]   .append(color)
                    node[nex_2] .append(color)
                    passed[now] =True
                    #colored     =connection[nex_2] - passed
                    if passed[nex_2] ==False:
                        next_next.add(nex_2)  #つながっている頂点（次に探索する）
                    passed[nex_2] =nex_2
                    color   +=1
                    count   +=1
                    break
                else:
                    color +=1
                    count +=1
    now_set     .clear()
    now_set     |=next_next
    next_next   .clear()
    
#出力
print(color_max)
for i in A:
    print(edge[i])

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')