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

import time
st = time.time()
import random
import math
d = int(input())
c = [int(i) for i in input().split()]
s = []
for i in range(d):
    s.append([int(j) for j in input().split()])
t = []

for i in range(d):
    t.append(math.floor(26 * random.random()))

tmp = -1
while time.time() - st < 1.99:
    tmp_d = math.floor(d * random.random())
    old = t[tmp_d]
    t[tmp_d] = math.floor(26 * random.random())
    last = [-1] * 26
    satis = 0
    for i in range(d):
        satis += s[i][t[i]]
        last[t[i]] = i;
        for j in range(26):
            satis -= c[j] * (i - last[j])
    if satis > tmp:
        tmp = satis
    else:
        t[tmp_d] = old

for i in range(d):
    print(t[i] + 1)
#print(time.time()-st)


### FIXED CODE ###

import random
import math
d = int(input())
c = [int(i) for i in input().split()]
s = []
for i in range(d):
    s.append([int(j) for j in input().split()])
t = []

for i in range(d):
    print(math.ceil(26 * random.random()))
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

data = []

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if i * j * k <= K:
                data.append(A[i] + B[j] + C[k])
                
data.sort()
data.reverse()
for i in range(K):
    print(data[i])

### FIXED CODE ###

import heapq as hq

X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

pri = []
data = []
hq.heapify(pri)

A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

hq.heappush(pri, [-A[0]-B[0]-C[0],0,0,0])
data.append([0,0,0])

for i in range(K):
    s = pri[0][1]
    t = pri[0][2]
    u = pri[0][3]
    if s+1 <= X-1:
        if [s + 1, t, u] not in data:
            data.append([s+1, t, u])
            hq.heappush(pri, [-A[s+1]-B[t]-C[u],s+1,t,u])
    if t+1 <= Y-1:
        if [s, t+1, u] not in data:
            data.append([s, t+1, u])
            hq.heappush(pri, [-A[s]-B[t+1]-C[u],s,t+1,u])
    if u+1 <= Z-1:
        if [s, t, u+1] not in data:
            data.append([s, t, u+1])
            hq.heappush(pri, [-A[s]-B[t]-C[u+1],s,t,u+1])
    print(hq.heappop(pri)[0] * -1)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    if s >= x:
        for y in range(k + 1):
            if s >= x + y:
                for z in range(k + 1):
                    if x + y + z == s:
                        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        if s >= x + y:
            if k >= s - (x + y):
                count += 1
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
s={j for j in range(l,r+1)}
for i in range(1,m):
    l,r=map(int,input().split())
    s=s & {j for j in range(l,r+1)}
    if len(s)==0:
        break
print(len(s))

### FIXED CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
s=[l,r]
for i in range(1,m):
    l,r=map(int,input().split())
    if s[0]<l:
        s[0]=l
    if s[1]>r:
        s[1]=r

    if s[1]-s[0]<0:
        s=[0,-1]
        break
print(s[1]-s[0]+1)
### BUGGY CODE ###

n,m,q = map(int,input().split(" "))
LR_2d = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    L,R = map(int,input().split(" "))
    LR_2d[L-1][R-1] += 1
LR_2dsum = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    LR_2dsum[i][0] = LR_2d[i][0]
    for j in range(1,n):
        LR_2dsum[i][j] = LR_2dsum[i][j-1] + LR_2d[i][j]
for i in range(q):
    ans = 0
    p_i,q_i = map(int,input().split(" "))
    for j in range(p_i-1,q_i):
        if p_i == 1:
            ans_j = LR_2dsum[j][q_i-1]
        else:
            ans_j = LR_2dsum[j][q_i-1] - LR_2dsum[j][p_i-2]
        ans += ans_j
    print(ans)

### FIXED CODE ###

n,m,q = map(int,input().split(" "))
LR_2d = [[0 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    L,R = map(int,input().split(" "))
    LR_2d[L][R] += 1

LR_2dsum = [[0 for i in range(n+1)] for i in range(n+1)]
for j in range(1,n):
    LR_2dsum[0][j] = LR_2dsum[0][j-1] + LR_2d[0][j]
for i in range(1,n+1):
    for j in range(1,n+1):
        LR_2dsum[i][j] = LR_2dsum[i-1][j] + LR_2dsum[i][j-1] - LR_2dsum[i-1][j-1] + LR_2d[i][j]

for i in range(q):
    p_i,q_i = map(int,input().split(" "))
    ans = LR_2dsum[p_i-1][p_i-1] - LR_2dsum[p_i-1][q_i] - LR_2dsum[q_i][p_i-1] + LR_2dsum[q_i][q_i]
    print(ans)
### BUGGY CODE ###

from collections import Counter

def main()->None:
    # a_iに１を足すか、１引くか、何もしないかの操作を行って、ある整数個数最大化をする
    # x を決めるとgreedyに決まる。
    # どうやってxを決めるのか。
    N = int(input())
    a = list(map(int, input().split()))
    set_a = set(a)
    max_count = 0
    for a_compo in set_a:
        X = a_compo
        tmp_count = 0
        for i in a:
            if abs(X - i) <= 1:
                tmp_count += 1
        if tmp_count > max_count:
            max_count = tmp_count
    print(max_count)

if __name__ == "__main__":
    #import time
    #start = time.time()
    main()
    #print("time:{}".format(time.time() - start))

### FIXED CODE ###

import sys


def main()->None:
    N = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    max_a = max(a)
    # print(max_a)
    l = [0 for _ in range(max_a+2)] # 配列の初期化、固定長、位置が配列の数字で要素がカウント
    for i in a:
        l[i] += 1
    res = 0
    for i in range(0, max_a+1):
        tmp = l[i-1]+l[i]+l[i+1]
        res = max(res, tmp)
    print(res)


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

N, K = map(int, input().split(' '))
h = [int(val) for val in input().split(' ')] + [0]*K
dp = [0]*1 + [float('inf')]*(len(h)+K)
for i in range(N):
    for j in range(1, K+1):
        cost = dp[i] + abs(h[i]-h[i+j])
        if cost < dp[i+j]:
            dp[i+j] = cost
print(dp[N-1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split(' '))
h = np.array(list(map(int, input().split(' '))))
dp = np.zeros(len(h), dtype=int)
for i in range(1, len(h)):
    start = max(0, i-K)
    dp[i] = min(dp[start:i] + np.abs(h[i] - h[start:i]))
print(dp[-1])
### BUGGY CODE ###

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

ret = 1
for a in A:
    ret *= a

if len(str(ret)) >= 19 and ret != 10**18:
    print(-1)
else:
    print(ret)


### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit(0)
    
ret = 1
for a in A:
    ret *= a
    if len(str(ret)) >= 19 and ret != 10 ** 18:
        print(-1)
        exit(0)
    

if len(str(ret)) >= 19 and ret != 10**18:
    print(-1)
else:
    print(ret)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]

while n > abs(n-k):
    n = abs(n-k)
    if k == 1:
        n = 0
        break

print(n)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]

while n > abs(n-k):
    if k == 1:
        n = 0
        break
    elif n%k == 0:
        n = 0
        break

    if n > k:
        n = n%k
    else:
        n = abs(n-k)    
    

print(n)
### BUGGY CODE ###

import bisect
n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort()
ans=0

while(m):
  m-=1
  now=a.pop()
  ind=bisect.bisect_left(a,int(now/2))
  a.insert(ind,int(now/2))

print(sum(a))

### FIXED CODE ###

import heapq as hp
n,m=[int(x) for x in input().rstrip().split()]
a=[-int(x) for x in input().rstrip().split()]

hp.heapify(a)
a.sort()

while(m):
  
  m-=1
  now=hp.heappop(a)
  now=-((-now)//2)
  hp.heappush(a,now)
  
print(-sum(a))
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
def bfs(root):
    q=deque([root])
    visited=[(0,0) for _ in range(n)]
    visited[root]=(0,-1)
    while q:
        p=q.popleft()
        dp,pp=visited[p]
        for c in edge[p]:
            dc,cp=visited[c]
            if dc<dp+1:
                visited[c]=(dp+1,p)
                q.append(c)
    return visited
visited=bfs(root)
#print(visited)
for d,i in visited:
    print(i+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n,m=map(int,input().split())
s=set()
edge=[[] for _ in range(n)]
edgerev=[[] for _ in range(n)]
for _ in range(n+m-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edgerev[b].append(a)
    s.add(b)
for i in range(n):
    if i not in s:
        root=i
        break
visited=[False]*n
to=[] #topological order
def dfs(root):
    if visited[root]:
        return
    visited[root]=True
    for i in edge[root]:
        dfs(i)
    to.append(root)
dfs(root)
to=to[::-1]
#print(to)
result=[0]*n
for i in range(n):
    result[to[i]]=i #頂点の順番
#print(result)
#print(edgerev)
for i in range(n):
    if not edgerev[i]:
        print(0)
        continue
    order=-1
    for j in edgerev[i]:
        if order<result[j]:
            ans=j
            order=result[j]
    print(ans+1)
### BUGGY CODE ###

N,Ma,Mb=map(int,input().split())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
M=401
dp=[[[10**4 for cb in range(M)]for ca in range(M)]for i in range(N+1)]
for i in range(N):
    a[i],b[i],c[i]=map(int,input().split())
dp[0][0][0]=0
for i in range(N):
    for ca in range(M):
        for cb in range(M):
            if ca+a[i]<M and cb+b[i]<M:
                dp[i+1][ca+a[i]][cb+b[i]]=min([dp[i+1][ca+a[i]][cb+b[i]],dp[i][ca][cb]+c[i]])
            dp[i+1][ca][cb]=min([dp[i][ca][cb],dp[i+1][ca][cb]])
ans=10**4
for i in range(1,M):
    for j in range(1,M):
        if i*Mb==j*Ma:
            if dp[N][i][j]<ans:
                ans=dp[N][i][j]
if ans!=10**4:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N,Ma,Mb=map(int,input().split())
a=[0 for i in range(N)]
b=[0 for i in range(N)]
c=[0 for i in range(N)]
M=401
dp=[[[10**4 for cb in range(M)]for ca in range(M)]for i in range(N+1)]
for i in range(N):
    a[i],b[i],c[i]=map(int,input().split())
dp[0][0][0]=0
for i in range(N):
    for ca in range(M):
        for cb in range(M):
            if dp[i][ca][cb]==10**4:
                continue
            dp[i+1][ca][cb]=min([dp[i+1][ca][cb],dp[i][ca][cb]])
            dp[i+1][ca+a[i]][cb+b[i]]=min([dp[i+1][ca+a[i]][cb+b[i]],dp[i][ca][cb]+c[i]])
ans=10**4
for i in range(1,M):
    for j in range(1,M):
        if i*Mb==j*Ma:
            if dp[N][i][j]<ans:
                ans=dp[N][i][j]
if ans!=10**4:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def main():
  n = int(input())
  l = list(map(int,input().split()))
  cnt = 0
  for i in range(n):
    for j in range(i+1,n):
      for k in range(j+1,n):
        if l[i]<l[j]+l[k] and l[j]<l[k]+l[i] and l[k]<l[i]+l[j]:
          cnt += 1
  print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def solve(string):
    n, *l = map(int, string.split())
    l.sort(reverse=True)
    nums = 0
    for i, a in enumerate(l[:-2]):
        j, k = i + 1, n - 1
        while (j < k):
            if (a < l[j] + l[k]):
                nums += k - j
                j += 1
            else:
                k -= 1
    return str(nums)
 
 
if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
### BUGGY CODE ###

def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True
    
def like2017_1tox(x):
    cnt=0
    for i in range(1,x+1,+2):
        # print(i)
        if is_prime(i):
            if is_prime((i+1)//2):
                cnt+=1   
    return cnt
    
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(like2017_1tox(b)-like2017_1tox(a-1))


### FIXED CODE ###

from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i+1)//2)
    
table=[0,0]
for i in range(2,10**5):
    table+=table[i-1]+like2017(i),
        
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    print(table[b]-table[a-1])
# print(table)
### BUGGY CODE ###

n, p = map(int, input().split())
out=1
for i in range(2,p+1):
    while p%(i**n)==0:
        p = p//(i**n)
        out *= i
        
    if p < i**n:
        break
print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

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

v = 0
for i in range(n):
    v += wv[i][1]


dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for j in range(v+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i+1][j],dp[i][j-wv[i][1]]+wv[i][0])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
ans = 0
for i in range(v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

### FIXED CODE ###

from pprint import pprint

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

lim = 1
for i in range(n):
    lim += wv[i][1]

dp = [[float('inf')] * lim for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(lim):
        if j - wv[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j - wv[i][1]] + wv[i][0], dp[i][j])
        else:
            dp[i+1][j] = min((dp[i][j], dp[i+1][j]))

ans = float('inf')

for i in reversed(range(lim)):
    if dp[-1][i] <= w:
        ans = min(i, ans)
        break
print(ans)
### BUGGY CODE ###

N = int(input())
P = [int(x) for x in input().split()]
count = 0
for i in range(len(P)):
  m = P[i]
  subm = min(P[:i+1])
  if m == subm:
    count += 1
print(count)
  

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
count = 0
minut = 3*10**5
for i in range(len(P)):
  m = P[i]
  if m < minut:
    minut = m
  if m == minut:
    count += 1
print(count)
### BUGGY CODE ###

s=input()
n=len(s)
li_p=[1]*n
li_pp=li_p

for i in range(n):
    li_tmp=[0]*n
    for j in range(n):
        if s[j]=='R':
            li_tmp[j+1]+=li_p[j]
        else:
            li_tmp[j-1]+=li_p[j]
    
    #print(li_tmp)
    
    if li_tmp==li_p:
        print(' '.join(map(str, li_tmp)))
        break
    
    elif li_tmp==li_pp:
        #print(i)
        if i%2:
            print(' '.join(map(str, li_tmp)))
        else:
            print(' '.join(map(str, li_p)))
        break
            
    li_pp=li_p
    li_p=li_tmp
    

### FIXED CODE ###

S=input()+'R'
ans=[0]*(len(S)-1)

Rf=1
Rc,Lc=0,0
for i,s in enumerate(S):
    if s=='R':
        if Rf:
            Rc+=1
        else:
            #print(x,Rc,Lc)
            
            if Rc%2:
                if Lc%2:
                    ans[x]+=(Rc+Lc)//2
                    ans[x+1]+=(Rc+Lc)//2
                else:
                    ans[x]+=(Rc+Lc)//2 + 1
                    ans[x+1]+=(Rc+Lc)//2
            else:
                if Lc%2:
                    ans[x]+=(Rc+Lc)//2
                    ans[x+1]+=(Rc+Lc)//2 + 1         
                else:
                    ans[x]+=(Rc+Lc)//2
                    ans[x+1]+=(Rc+Lc)//2
            
            Rc,Lc=0,0
            Rc+=1
            Rf=1
    else:
        Lc+=1
        if Rf:
            Rf=0
            x=i-1
        else:
            pass

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

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

A.sort()

def comb(x, y):
    p = 1
    d = 1
    for i in range(y):
        p *= x - i
        d *= y -i
    return p // d

ans = []
max_val = 0
mid = 0
for i in range(n):
    diff = min(A[mid], A[i]-A[mid])
    is_finished = False
    while mid < i:
        if diff > min(A[mid+1], A[i]-A[mid+1]):
            if max_val < comb(A[i], A[mid]):
                ans = [A[i], A[mid]]
                max_val = comb(*ans)
            is_finished = True
            break
        mid += 1
    if not is_finished and max_val < comb(A[i], A[mid-1]):
        ans = [A[i], A[mid-1]]
        max_val = comb(*ans)
print(*ans)


### FIXED CODE ###

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

A.sort()

def comb(x, y):
    p = 1
    d = 1
    for i in range(y):
        p *= x - i
        d *= y -i
    return p // d

diff = -1
ans = [A[n-1], -1]
for a in A[:n-1]:
    new_diff = min(a, A[n-1]-a)
    if diff < new_diff:
        diff = new_diff
        ans[1] = a
print(*ans)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
tmp = []
for i in range(1,n+1):
  tmp.append(s[:i].count('AC'))
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
tmp=[0]
l,cnt=0,0
r=2
while r<=n:
  if 'AC' == s[l:r]:
    cnt+=1
    l=r
    tmp.append(cnt)
    tmp.append(cnt)
    r+=2
  else:
    tmp.append(cnt)
    l+=1
    r+=1
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])
### BUGGY CODE ###

N = int(input())
# = map(int, input().split())
P = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

count = 0

for i in range(N):
    if P[N-1-i] == min(P):
        count += 1
        del P[N-1-i]
    else:
        del P[N-1-i]

print(count)


### FIXED CODE ###

N = int(input())
# = map(int, input().split())
P = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

count = 0
minimum = 300000

for i in range(N):
    if P[i] == 1:
        count += 1
        break
    if P[i] < minimum:
        count += 1
        minimum = P[i]

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

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

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

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

N = INT()
ab = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

edge = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

K = 0
for i in graph:
	K = max(K, len(graph[i]))
color = list(range(1, K+1))

def DFS(i, color_from):  # color_fromからきた色を使わない
	can_use_color = color[:]
	for node in graph[i]:
		if not edge[i][node]:
			use_color = can_use_color.pop()
			if use_color == color_from:
				use_color = can_use_color.pop()
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

print(K)
for a, b in ab:
	print(edge[a-1][b-1])


### FIXED CODE ###

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

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

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

	# edge = [[0]*N for _ in range(N)]
	edge = defaultdict(int)
	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


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

import itertools
from math import factorial
n = int(input())
a = list(map(int,input().split()))
ans = []
for it in itertools.combinations(a,2):
    if it[0] == it[1]:
        ans.append(it[0])
for i in range(n):
    if a[i] in ans:
        print(len(ans)-a.count(a[i])+1)
    else:
        print(len(ans))

### FIXED CODE ###

from collections import Counter
N = int(input())
An = list(map(int, input().split()))
counter = Counter(An)
cnt = 0
for c in counter.values():
    cnt += c * (c-1) // 2
for a in An:
    print(cnt - (counter[a] - 1))
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(max(a)+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],max(a)+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(M)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],M,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)