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

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

for i in range(1, n+1):
  print(a.count(i))



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

for i in range(n-1):
  b[a[i]] += 1

for i in range(1,n+1):
  print(b[i])
### BUGGY CODE ###

from functools import reduce

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

L = [i for i in range(A,B+1)]

print(reduce(lambda x, y: x^y, L))

### FIXED CODE ###

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

def xorsum(m):
  if m==3:
    return 0
  if m==2:
    return 3
  if m==1:
    return 1
  if m==0:
    return 0
  if m==-1:
    return 0
  h=1
  while h<=m:
    h=h*2
  h=h//2
  return xorsum(m-h)^(((m-h+1)%2)*h)

print(xorsum(B)^xorsum(A-1))
### BUGGY CODE ###

from collections import deque


def show_2d_array(array):
    [print(a) for a in array]


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

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


# show_2d_array(cave)


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))
    depth = [0] * N
    depth[p] = 0
    current_depth = depth[p]
    while len(queue) > 0:
        # print(queue)
        q = queue.popleft()
        seen[q] = True
        # print(q)
        for v in tree[q]:
            if not seen[v]:
                depth[v] = depth[q] + 1
                queue.append(v)
                seen[v] = True


    return depth


depth = bfs(cave, 0)

# print("depth", depth)

sign = [0] * N

ans = "Yes"
for i in range(1, N):
    current = i
    found = False
    while not found:
        next = -1
        for j in cave[current]:
            if depth[j] == depth[current]-1:
                if sign[current] <= 0:
                    next = j
                    sign[current] = next
                    break
                else:
                    next = sign[current]
                    break
        if next < 0:
            ans = "No"
            break

        current = next
        if current == 0:
            found = True

print(ans)
if ans == "Yes":
    [print(s+1) for s in sign[1:]]



### FIXED CODE ###

from collections import deque


def show_2d_array(array):
    [print(a) for a in array]


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

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


# show_2d_array(cave)


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))
    depth = [0] * N
    depth[p] = 0
    current_depth = depth[p]
    while len(queue) > 0:
        # print(queue)
        q = queue.popleft()
        seen[q] = True
        # print(q)
        for v in tree[q]:
            if not seen[v]:
                depth[v] = depth[q] + 1
                queue.append(v)
                seen[v] = True


    return depth


depth = bfs(cave, 0)

# print("depth", depth)

sign = [0] * N
ans = "Yes"
for i in range(1, N):
    this_depth = depth[i]
    found = False
    for j in cave[i]:
        if depth[j] == this_depth - 1:
            sign[i] = j
            found = True
            break
    if not found:
        ans = "No"
        break

"""
for i in range(1, N):
    current = i
    found = False
    while not found:
        next = -1
        for j in cave[current]:
            if depth[j] == depth[current]-1:
                if sign[current] <= 0:
                    next = j
                    sign[current] = next
                    break
                else:
                    next = sign[current]
                    break
        if next < 0:
            ans = "No"
            break

        current = next
        if current == 0:
            found = True
"""

print(ans)
if ans == "Yes":
    [print(s+1) for s in sign[1:]]
### BUGGY CODE ###

n = int(input())
A = [*map(int, input().split())]
MOD = (10**9)+7
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans = (ans + A[i]*A[j]%MOD) % MOD
ans = (ans + MOD) % MOD
print(ans)


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
MOD = (10**9)+7
ans = 0

# print(A)

sum_a = [0] * (n+1)
for i in range(n):
    sum_a[i+1] = sum_a[i] + A[i]

# print(sum_a)

for i in range(n):
    ai = A[i]
    ans = (ans + ai*(sum_a[-1] - sum_a[i+1])) % MOD
    # print(sum_a[-1], sum_a[i+1],sum_a[-1] - sum_a[i+1] )

# for i in range(n):
#     for j in range(i+1, n):
#         ans = (ans + A[i]*A[j]%MOD) % MOD
ans = (ans + MOD) % MOD
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
N,T=map(int,raw_input().split())
A=map(int,raw_input().split())

arrmaxv=[]
arrmaxc=[]
for i in xrange(N-1):
    a=A[i:]
    maxv=max(a)
    maxc=a.count(maxv)
    arrmaxv.append((maxv-A[i]))
    arrmaxc.append(maxc)

maxv=np.array(arrmaxv)
maxc=np.array(arrmaxc)
idx=np.argwhere(maxv==np.max(maxv))
cnt=maxc[idx]
print(np.sum(cnt))


### FIXED CODE ###

# -*- coding: utf-8 -*-
N,T=map(int,raw_input().split())
A=map(int,raw_input().split())

minv=A[0]
interval=0
cnt=0
for i in A[1:]:
    if i < minv:
        minv=i
    if i-minv > interval:
        interval=i-minv
        cnt=1
    elif i-minv == interval:
        cnt=cnt+1
print(cnt)
### BUGGY CODE ###

n = int(input())

a = [int(x) for x in input().split()]

sum = a[0]

for i in range(1,len(a)):
    sum = sum * a[i]
    if 0 in a:
        sum = 0
        break
    elif sum > 10**18:
        break
    


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

### FIXED CODE ###

n = int(input())

a = [int(x) for x in input().split() ]
sum = a[0]

if 0 in a:
        sum = 0
else:
    for i in range(1,len(a)):
        sum = sum * a[i]
        if sum > 10**18:
            break
        


if sum > 10**18:
    print(-1)
else:
    print(sum)
### BUGGY CODE ###

import queue
def tree(edges,n,q):
    distance = [0]*(n+1)
    for _ in range(0,q):
        p,x = map(int,input().split())
        Q = queue.Queue()
        Q.put(p)
        distance[p] += x
        while (not Q.empty()):
            xx = Q.get()
            for i in range(0,len(edges[xx])):
                distance[edges[xx][i]] += x
                Q.put(edges[xx][i])
    return distance[1:]

def addEdge(edges,u,v):
    edges[u].append(v)
n,q = map(int,input().split())
edges = [[] for i in range(n+1)]
for _ in range(0,n-1):
    u,v = map(int,input().split())
    addEdge(edges,u,v)
print(*tree(edges,n,q))


### FIXED CODE ###

from collections import deque
def tree(edges, n, q):
    distance = [0]*(n+1)
    visited = [0]*(n+1)
    for _ in range(0, q):
        p, x = map(int, input().split())
        distance[p] += x
    Q = deque([])
    Q.append(1)
    visited[1] = 1
    while Q:
        xx = Q.popleft()
        for i in range(0, len(edges[xx])):
            if visited[edges[xx][i]]:
                continue
            distance[edges[xx][i]] += distance[xx]
            Q.append(edges[xx][i])
            visited[edges[xx][i]] = 1
    return distance[1:]
def addEdge(edges, u, v):
    edges[u].append(v)
    edges[v].append(u)
n, q = map(int, input().split())
edges = [[] for i in range(n + 1)]
for _ in range(0, n - 1):
    u, v = map(int, input().split())
    addEdge(edges, u, v)
print(*tree(edges, n, q))
### BUGGY CODE ###

from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
import re
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

n=int(input())
a=[int(x) for x in input().split()]
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=(a[i]*a[j])
        ans%=mod
     
print(ans)

### FIXED CODE ###

from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
import re
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

n=int(input())
a=[int(x) for x in input().split()]
cum_a=[]
for i in range(n):
    if i==0:cum_a.append(a[i])
    else:cum_a.append(cum_a[-1]+a[i])
ans=0
for i in range(n-1):
    ans+=a[i]*(cum_a[n-1]-cum_a[i])
    ans%=mod
     
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
D = []

for i in range(M):
    B, C = map(int, input().split())
    D += [C]*B

D = sorted(D, reverse=True)

for j in range(min(N, len(D))):
    if A[j] <= D[j]:
        A[j] = D[j]
    else:
        break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
D = []
E = []
for i in range(M):
    B, C = map(int, input().split())
    D.append([C, B])
D = sorted(D, reverse = True)

for j in range(len(D)):
    E += [D[j][0]]*D[j][1]
    if len(E) >= N:
        break

F = sorted(A + E, reverse = True)
print(sum(F[0:N]))
### BUGGY CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

tate=[]
yoko=[]

for i in range(m):
    tate.append(hw[i][0])
    yoko.append(hw[i][1])

from collections import Counter
tatec=Counter(tate).most_common()
yokoc=Counter(yoko).most_common()

c_1_max=tatec[0][1]
c_1s=[]
for t in tatec:
    if t[1]==c_1_max:
        c_1s.append(t[0])
    else:
        break

c_2_max=yokoc[0][1]
c_2s=[]
for y in yokoc:
    if y[1]==c_2_max:
        c_2s.append(y[0])
    else:
        break

flag=False

for c_1 in c_1s:
    for c_2 in c_2s:
        tmp_flag=0
        for i in range(m):
            h_i=hw[i][0]
            w_i=hw[i][1]
            if h_i!=c_1 or w_i!=c_2:
                tmp_flag+=1
        if tmp_flag==m:
            flag=True


print(max(tatec[0][1]+yokoc[0][1], 1) if flag else max(tatec[0][1]+yokoc[0][1]-1, 1))


### FIXED CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

y_list=[0]*h
x_list=[0]*w

for h_i, w_i in hw:
    y_list[h_i-1]+=1
    x_list[w_i-1]+=1

my_cnt=max(y_list)
mx_cnt=max(x_list)

y_cnt=0
x_cnt=0

my_set=set()
mx_set=set()

for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt:
        my_set.add(h_i-1)
    if x_list[w_i-1]==mx_cnt:
        mx_set.add(w_i-1)

cnt=0
for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt and x_list[w_i-1]==mx_cnt:
        cnt+=1

print(my_cnt+mx_cnt-1 if cnt==len(my_set)*len(mx_set) else my_cnt+mx_cnt)
### BUGGY CODE ###

h, n = [int(i) for i in input().split()]
a, b = [0]*n, [0]*n

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]
    if eff < a[i]/b[i]:
        eff = a[i]/b[i]
        eff_index = i

max_kaisuu = - (-h//a[eff_index])

ans = float('inf')
H = max_kaisuu * b[eff_index]
dp = [[0] * (H+1) for _ in range(n+1)]
# dp[i][j] i番目までの魔法で消費魔力がjを超えないように選んだときのダメージの最大値
for i in range(n):
    for j in range(H+1):
        if j < b[i]:# i番目の魔法消費b[i]がjを超えているので，入れる可能性がない

            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-b[i]]+a[i])# 入れ場合と入れない場合を比較

        if dp[i+1][j] >= h:
            ans = min(ans, j)
            H = j
            continue
print(ans)


### FIXED CODE ###

h, n = [int(i) for i in input().split()]
a, b = [0]*n, [0]*n

eff = 0
eff_index = 0
for i in range(n):
    a[i], b[i] = [int(_) for _ in input().split()]

max_a = max(a)

ans = float('inf')
H = h + max_a
dp = [float('inf')] * (H+1)
# dp[i] iのダメージを与える最小消費魔力
dp[0] = 0
for i in range(H+1):
    for j in range(n):
        if i >= a[j]:
            dp[i] = min(dp[i], dp[i-a[j]]+b[j])

    if i >= h:
        ans = min(ans, dp[i])
print(ans)
### BUGGY CODE ###

def p(n):
 for i in range(2,n):
  if n%i==0:return 0
 return 1
n=int(input())
print(sum([p(int(input()))for _ in range(n)]))

### FIXED CODE ###

import sys
input()
def s():print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin.readlines())))
if'__main__'==__name__:s()
### BUGGY CODE ###

import numpy as np
N=int(input())
A=np.array(input().split(" ")).astype(int)
for s in range(N-1):
    B=np.array(input().split(" ")).astype(int)
    A=np.r_[A,B]
A=A.reshape(N,-1)
SUM=np.sum(A,axis=1)
SUM=sorted(SUM,reverse=True)
SUB=np.sum(A[:,1])
ans=0
for s in range(0,N,2):
    ans+=SUM[s]
    
print(ans-SUB)

### FIXED CODE ###

n=int(input())
ans=0
l=[]
x=0
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
    x-=b

print(sum(map(sum,sorted(l,reverse=1,key=lambda x:sum(x))[::2]))+x)
### BUGGY CODE ###

x, y, z, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
ab = []
for i in range(len(a)):
    for j in range(len(b)):
        ab.append(a[i]+b[j])
ab.sort(reverse = True)
abc = []
k_1 = min([len(ab), k])
for i in range(k_1):
    for j in range(len(c)):
        abc.append(ab[i]+c[j])
abc.sort(reverse = True)
for i in range(k):
    print(abc[i])

### FIXED CODE ###

import heapq
import sys
x, y, z, k = map(int, input().split())

a, b, c = (sorted(map(int, sys.stdin.readline().split()), reverse=True) for _ in range(3))

abc = {(0,0,0)}

stu = [[-a[0]-b[0]-c[0], 0,0,0]]
heapq.heapify(stu)
result = []
while k > 0:
    out_p, n, m, l = heapq.heappop(stu)
    if n+1<x and not((n+1,m,l) in abc):
        abc.add((n+1,m,l))
        heapq.heappush(stu, [-a[n+1]-b[m]-c[l], n+1, m, l])
    if m+1<y and not((n,m+1,l) in abc):
        abc.add((n,m+1,l))
        heapq.heappush(stu, [-a[n]-b[m+1]-c[l], n, m+1, l])
    if l+1<z and not((n,m,l+1) in abc):
        abc.add((n,m,l+1))
        heapq.heappush(stu, [-a[n]-b[m]-c[l+1], n, m, l+1])
    result.append(-out_p)
    k -= 1
result.sort(reverse=True)
for i in result:
    print(i)
### BUGGY CODE ###

N = int(input())
if N < 1800:
  for n in range(1,3501):
    for w in range(n,3501):
      if (4*n*w-w*N-n*N) != 0:
        h = n*w*N/(4*n*w-w*N-n*N)
        if h == h//1 and h > 0:
          print(int(h),n,w)
          exit()
else:
  for n in range(3500,0,-1):
    for w in range(3500,n,-1):
      if (4*n*w-w*N-n*N) != 0:
        h = n*w*N/(4*n*w-w*N-n*N)
        if h == h//1 and h > 0:
          print(int(h),n,w)
          exit()

### FIXED CODE ###

N = int(input())
for n in range(1,3501):
  for w in range(n,3501):
    if (4*n*w-w*N-n*N) > 0:
      h = n*w*N/(4*n*w-w*N-n*N)
      if h == int(h) and h > 0:
        print(int(h),n,w)
        exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[[0]*N for i in range(N)]
for i in range(N-1):
    arr[val[i][0]-1].add(val[i][1]-1)
    arr[val[i][1]-1].add(val[i][0]-1)
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=set(colall)
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp.pop()
    colarr[min(flag,f)][max(flag,f)]=p
    col[f].add(p)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]
reach={flag}

for i in range(N-1):
    for t in que[i]:
        coltemp=colall^col[t]
        arrtemp=arr[t]^(reach&arr[t])
        que[i+1]=que[i+1] | arrtemp
        reach.add(t)
        for f in arrtemp:
            p=coltemp.pop()
            col[f].add(p)
            colarr[min(t,f)][max(t,f)]=p
print(colmax)
for i in range(N-1):
    print(colarr[val[i][0]-1][val[i][1]-1])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N=int(input())
val=[list(map(int, input().split())) for i in range(N-1)]

arr=[set() for i in range(N)]
col=[set() for i in range(N)]
colarr=[0]*(N-1)
coldict={}
for i in range(N-1):
    a=val[i][0]-1
    b=val[i][1]-1
    arr[a].add(b)
    arr[b].add(a)
    coldict[(a,b)]=i
colmax=0
flag=0
for i in range(N):
    if len(arr[i])>colmax:
        colmax=len(arr[i])
        flag=i
colall=set(range(1,colmax+1))
coltemp=1
arrtemp=set(arr[flag])
for f in arrtemp:
    p=coltemp
    coltemp+=1
    if flag<f:
        colarr[coldict[(flag,f)]]=p
    else:
        colarr[coldict[(f,flag)]]=p
    col[f].add(p)
    arr[f].remove(flag)
que=[set() for i in range(N)]
que[0]=que[0] | arr[flag]

for i in range(N-1):
    for t in que[i]:
        arrtemp=arr[t]
        if len(arrtemp)>0:
            coltemp=1
            que[i+1] |= arrtemp
            for f in arrtemp:
                while(1):
                    if coltemp not in col[t]:
                        break
                    coltemp+=1
                p=coltemp
                coltemp+=1
                col[f].add(p)
                arr[f].remove(t)
                if t<f:
                    colarr[coldict[(t,f)]]=p
                else:
                    colarr[coldict[(f,t)]]=p
print(colmax)
for i in range(N-1):
    print(colarr[i])
### BUGGY CODE ###

from bisect import *
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[i][j][k] = dp[i][j-1][k]
      #上から取らない
      dp[i][j][0] = max(dp[i][j][0],max(dp[i-1][j]))
      if item[i-1][j-1]>0:
        #上からとる
        dp[i][j][1] = max(dp[i][j][1],max(dp[i-1][j])+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+item[i-1][j-1])
  ans = max(dp[-1][-1])
  return ans
print(solve())

### FIXED CODE ###

import sys
input = sys.stdin.readline
def solve():
  R, C, K = map(int, input().split())
  item = [[0]*C for _ in range(R)]
  for i in range(K):
    r,c,v = map(int, input().split())
    item[r-1][c-1] = v
  dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4): #横から取らない
        dp[k][i][j] = dp[k][i][j-1]
      #上から取らない
      dp[0][i][j] = max(dp[0][i][j],dp[-1][i-1][j])
      if item[i-1][j-1]>0:
        #上からとる
        dp[1][i][j] = max(dp[1][i][j],dp[-1][i-1][j]+item[i-1][j-1])
        for k in range(1,4): #横から取る
          dp[k][i][j] = max(dp[k][i][j],dp[k-1][i][j-1]+item[i-1][j-1])
      for k in range(1,4):
        dp[k][i][j] = max(dp[k-1][i][j],dp[k][i][j])
  ans = 0
  for k in range(4):
    ans = max(ans,dp[k][-1][-1])
  return ans
print(solve())
### BUGGY CODE ###

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

current = 1
path = [1]

while K > 0:
    if A[current - 1] in path:
        loop = path[path.index(A[current - 1]):]
        path += [loop[(K-1) % len(loop)]]
        break

    path += [A[current - 1]]
    current = A[current - 1]
    K -= 1

print(path[-1])


### FIXED CODE ###

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

current = 1
path = [1]
already = [False] * len(A)

while K > 0:
    if already[current - 1]:
        loop = path[path.index(A[current - 1]):]
        current = loop[(K - 1) % len(loop)]
        break

    path += [A[current - 1]]
    already[current - 1] = True
    current = A[current - 1]
    K -= 1

print(current)
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
A=[]
for i in range(n):
  a,b,c=map(int,input().split())
  A.append([a,b,c])
ans=float("inf")
for i in range(1,2**n):
  key=str(bin(i))[2:].zfill(n)
  xa,xb,price=0,0,0
  for j in range(n):
    if key[j]=="1":
      xa+=A[j][0]
      xb+=A[j][1]
      price+=A[j][2]
  if xa*mb-xb*ma==0:
    ans=min(ans,price)
print(-1 if ans==float("inf") else ans)


### FIXED CODE ###

n,ma,mb=map(int,input().split())
A=[]
for i in range(n):
  a,b,c=map(int,input().split())
  A.append([a,b,c])
DP=[[[float("inf")]*(10*n+1) for _ in range(10*n+1)] for _ in range(n+1)]
DP[0][0][0]=0
for i in range(n):
  a,b,c=A[i][0],A[i][1],A[i][2]
  for j in range(10*(i+1)+1):
    for k in range(10*(i+1)+1):
      if j>=a and k>=b:
        DP[i+1][j][k]=min(DP[i][j-a][k-b]+c,DP[i][j][k])
      else:
        DP[i+1][j][k]=DP[i][j][k]
ans=float("inf")
for i in range(10*n+1):
  for j in range(10*n+1):
    if i*mb==j*ma and i*j!=0:
      ans=min(ans,DP[n][i][j])
print(ans if ans!=float("inf") else -1)
### BUGGY CODE ###

def main():
    from collections import deque
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        par = [-1]*N
        while que:
            u = que.popleft()
            if par[u] != -1:
                if par[u] < u:
                    color[u].discard(edge[(par[u], u)])
                else:
                    color[u].discard(edge[(par[u], u)])
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                par[v] = u
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c
            if all(i != -1 for i in edge.values()):
                return
    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))