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

import sys
sys.setrecursionlimit(10**9)

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

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    comb1=comb1*(n-i+1)//i
    comb2=comb2*(n-i)//i
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

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

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  inv_table = [0]+[1]
  for i in range(2,k+1):
    inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    #comb1=comb1*(n-i+1)//i
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

T1, T2 = MAP()
A1, A2 = MAP()
B1, B2 = MAP()

def calc(a, b):
    cnt = 0
    a1 = a + T1 * A1
    b1 = b + T1 * B1
    if a > b and a1 <= b1 or a < b and a1 >= b1:
        cnt += 1
    a2 = a1 + T2 * A2
    b2 = b1 + T2 * B2
    if a1 > b1 and a2 <= b2 or a1 < b1 and a2 >= b2:
        cnt += 1
    if a == b and a2 == b2:
        print('infinity')
        exit()
    return a2, b2, cnt

a = b = 0
ans = 0
while True:
    a, b, cnt = calc(a, b)
    if cnt == 0:
        break
    ans += cnt
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

T1, T2 = MAP()
A1, A2 = MAP()
B1, B2 = MAP()

# a,bの状態からT1,T2の操作を行った後のa,bと、この操作での交差回数を返す
def calc(a, b):
    cnt = 0
    a1 = a + T1 * A1
    b1 = b + T1 * B1
    if a > b and a1 <= b1 or a < b and a1 >= b1:
        cnt += 1
    a2 = a1 + T2 * A2
    b2 = b1 + T2 * B2
    if a1 > b1 and a2 <= b2 or a1 < b1 and a2 >= b2:
        cnt += 1
    return a2, b2, cnt

# x+1回目の操作でまだ交差するか
def check(x):
    a = (T1 * A1 + T2 * A2) * x
    b = (T1 * B1 + T2 * B2) * x
    _, _, cnt = calc(a, b)
    return cnt >= 1

# 初回で同値に飛んだらその先もずっと繰り返す
a, b, cnt = calc(0, 0)
if a == b:
    print('infinity')
    exit()

# 最後に交差する直前までの操作回数を調べる
res = bisearch_max(-1, 10**18, check)
# 初回でも交差しなければ0
if res == -1:
    print(0)
    exit()

# 直前までの操作では、初回は1回、以降は2回ずつ交差する
ans = max(0, res * 2 - 1)
# 最後に交差する直前までa,bを移動させる
a = (T1 * A1 + T2 * A2) * res
b = (T1 * B1 + T2 * B2) * res
# 最後が1回か2回か確認
_, _, cnt = calc(a, b)
ans += cnt
print(ans)
### BUGGY CODE ###

S = input()

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
M = 10**9+7

for i in range(len(S)):
    if S[i] == "?":
        for k in range(10):
            for j in range(13):
                dp[i+1][(k+j*10)%13] += (dp[i][j]%M)
    else:
        for j in range(13):
            dp[i+1][(int(S[i])+j*10)%13] += (dp[i][j]%M)

ans = dp[-1][5] % M
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

n,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*(w+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(w+1):
        z[i+1][j]=z[i][j]
        if a[i][0]<=j:
            z[i+1][j]=max(z[i+1][j],z[i][j-a[i][0]]+a[i][1])
print max(z[-1])

### FIXED CODE ###

n,w=map(int,raw_input().split())
a=[map(int,raw_input().split()) for _ in xrange(n)]
z=[[0]*(w+1)]
for i in xrange(n):
    z.append(z[-1][:])
    for j in xrange(w+1):
        if a[i][0]<=j:
            z[i+1][j]=max(z[i+1][j],z[i][j-a[i][0]]+a[i][1])
print max(z[-1])
### BUGGY CODE ###

# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
B=[]
if n%2==0:
    for i in range(n):
        if i%2==0:
            B.append(str(A[i]))
        else:
            B.insert(0,str(A[i]))
else:
    for i in range(n):
        if i%2!=0:
            B.append(str(A[i]))
        else:
            B.insert(0,str(A[i]))
print(' '.join(B))

### FIXED CODE ###

# coding: utf-8
n=int(input())
A=list(map(int,input().split()))
B=[0]*n
l=n//2
if n%2==0:
    for i in range(n):
        if i%2==0:
            B[l+i]=str(A[i])
            l=l+i
        else:
            B[l-i]=str(A[i])
            l=l-i
else:
    for i in range(n):
        if i%2==0:
            B[l-i]=str(A[i])
            l=l-i
        else:
            B[l+i]=str(A[i])
            l=l+i
print(' '.join(B))
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
sum=0

for i in range(A,B+1):
    if(i%C!=0 and i%D!=0):
        sum+=1

print(sum)


### FIXED CODE ###

import fractions

A,B,C,D=map(int,input().split())

sum1=(A-1)//C
sum2=B//C
sum3=sum2-sum1
sum1=(A-1)//D
sum2=B//D
sum4=sum2-sum1
num=(C*D)//fractions.gcd(C,D)
sum1=(A-1)//num
sum2=B//num
sum5=sum2-sum1
sum=sum3+sum4-sum5
sum=B-A+1-sum


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

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in list(s):
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
dic = [j for i, j in d.items()]
result = 0
for i in range(1, 2**len(dic)):
    c = 1
    num = i
    for j in dic:
        if num%2==1:
            c *= j
            c %= mod
        num >>= 1
    result += c
    result %= mod

print(result%mod)

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
### BUGGY CODE ###

import math
import sys
N=int(input())
D = list(map(int, input().split()))
M=int(input())
T = list(map(int, input().split()))
new_D=sorted(D)
new_T=sorted(T)
#print(new_D[0])
for i in range(len(T)):
    if new_D.count(new_T[i])==0:
        print("NO")
        sys.exit()
    if new_D.count(new_T[i])>=1:
        new_D.remove(new_T[i])
        #print(new_D.count(new_T[i]))
    
print("YES")

### FIXED CODE ###

import math
import sys
import collections 
N=int(input())
D = list(map(int, input().split()))
M=int(input())
T = list(map(int, input().split()))
new_D=sorted(D)
new_T=sorted(T)
a=collections.Counter(new_D)
b=collections.Counter(new_T)
#print(a[10])
#print(new_D[0])
for i in new_T:
    if a[i]<b[i]:
        print("NO")
        sys.exit()
    
    
print("YES")
### BUGGY CODE ###


n = int(input())

c=0
line=[]

for i in range(n):
    string = list(input())
    string = [[a,string.count(a)] for a in set(string)]
    c+=line.count(string)
    line.append(string)

print(c)

### FIXED CODE ###

n = int(input())

line={}
c=0

for i in range(n):
    string = ''.join(sorted(list(input())))
    # print(string)
    if string in line:
        c+=line[string]
    if string in line:
        line[string]+=1
    else:
        line[string]=1
    # print(line,c)

print(c)
### BUGGY CODE ###

#n = int(input())
#m = int(input())
#k = int(input())
#n, m = map(int, input().split())
r, g, b, n = map(int, input().split())
#a = list(map(int, input().split()))
#table = []
'''
for i in range h:
    temp = list(map(int, input().split()))
    table.append(temp)
'''
count = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        for k in range(n//b+1):
            if r*i+g*j+b*k==n:
                count +=1
print(count)

### FIXED CODE ###

#n = int(input())
#m = int(input())
#k = int(input())
#n, m = map(int, input().split())
r, g, b, n = map(int, input().split())
#a = list(map(int, input().split()))
#table = []
'''
for i in range h:
    temp = list(map(int, input().split()))
    table.append(temp)
'''
count = 0
for i in range(n//r+1):
    for j in range((n-r*i)//g+1):
        if (n-r*i-g*j)%b == 0:
            count +=1
print(count)
### BUGGY CODE ###

# const
M = 1046527

def h1(key):
    return key % M

def h2(key):
    return 1 + (key % (M-1))

def hash(key ,i):
    return (h1(key) + i*h2(key)) % M

def conv_str_to_num(str):
    converted = 0
    s_list = list(str)
    for (i,c) in enumerate(s_list):
        if c == 'A':
            n = 1
        elif c == 'C':
            n = 2
        elif c == 'G':
            n = 3
        elif c == 'T':
            n = 4
        else:
            n = 0

        converted += 5**i * n

    return converted



class hashTable(object):
    def __init__(self, arg):
        self.T = ["" for _ in range(arg)]

    def insert(self, s):
        key = conv_str_to_num(s)
        i = 0
        while True:
            h = hash(key, i)
            if self.T[h] == "":
                self.T[h] = s
                break
            i += 1

    def find(self, s):
        key = conv_str_to_num(s)
        i = 0
        while True:
            h = hash(key, i)
            if self.T[h] == s:
                return 1
            elif self.T[h] == "":
                return 0

            i += 1
        return 0


if __name__ == '__main__':
    h_t = hashTable(M)
    ans = []
    n = int(input())
    for _ in range(n):
        op, s = input().split()
        if op == "insert":
            h_t.insert(s)
        else:
            tmp = h_t.find(s)
            if tmp == 1:
                ans.append("yes")
            else:
                ans.append("no")

    for s in ans:
        print(s)

### FIXED CODE ###

def hash1(m, key):
    return key % m

def hash2(m, key):
    return 1 +  key % (m - 1)

def hash(m, key, i):
    return (hash1(m, key) + i * hash2(m, key) ) % m

def insert(T, key):
    i = 0
    l = len(T)
    while True:
        h = hash(1046527,key,i)
        if (T[h] == None ):
            T[h] = key
            return h
        elif (T[h] == key):
            return h
        else:
            i += 1

def search(T,key):
    l = len(T)
    i = 0
    while True:
        h = hash(1046527,key,i)
        if(T[h] == key):
            return h
        elif(T[h] is None or h >= l):
            return -1
        else:
            i += 1

def find(T, key):
    a = search(T,key)
    if(a == -1):
        print('no')
    else:
        print('yes')

dict = {'A' : '1', 'C' : '2', 'G' : '3', 'T' : '4'}
data = []
T = [None]*1046527
n = int(input())


while n > 0:
    st = input()
    d = list(st.split())

### convert key to num(1~4)
    tmp_key = ''
    for x in list(d[1]):
        tmp_key += dict[x]

    data.append([d[0],int(tmp_key)])
    n -= 1
for com in data:
    if(com[0] == 'insert'):
        insert(T,com[1]) 
    else:
        find(T,com[1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)

    ans = []
    for i in range(N):
        t = 0
        for k,v in c.items():
            if k == A[i]:
                if v-1 >= 2:
                    t += combination(v-1, 2)
            else:
                if v >= 2:
                    t += combination(v, 2)
        ans.append(t)
        
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)
    
    ta = 0
    for k,v in c.items():
        if v >= 2:
            ta += combination(v, 2)
            
    # dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        t = ta
        if c[A[i]] >= 2:
            t -= combination(c[A[i]], 2)
        if c[A[i]]-1 >= 2:
            t += combination(c[A[i]]-1, 2)
        
        ans.append(t)

 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

import math
import sys
def isprime(number):
	if number == 2:
		return True
	elif number == 3:
		return True
	else:
		for prime in getprime(int(math.sqrt(number))):
			if number % prime == 0:
				return False
		return True

def getprime(number):
	list_item = []
	if number == 2:
		list_item = [2]
	elif number == 3:
		list_item = [3, 2]
	else:
		if isprime(number):
			list_item = getprime(number - 1)
			list_item.append(number)
		else:
			list_item = getprime(number - 1)
	return list_item

for line in sys.stdin:
	N = int(line)
	count = 0
	for x in range(2, N + 1):
		if isprime(x):
			count += 1
	print count

### FIXED CODE ###

import itertools
import sys

N = 999999
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] 
primeb = [0 for i in range(N+1)]
 
for i in primes:
  primeb[i] = 1
 
def isprime(n):
  for p in primes:
    if (n % p == 0):
      return True
    if (n < p*p):
      return False 
S = primes[-1]
for i in range(S, N):
  if isprime(i):
    pass 
  else: 
    primes.append(i)
    primeb[i] = 1

for line in sys.stdin:
  n = int(line)
  print sum(primeb[:n+1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ list(sys.stdin.readline().strip()) for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[(1,1),(-1,1),(1,-1),(-1,-1),(2,0),(-2,0),(0,2),(0,-2),(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1),(2,2),(-2,2),(2,-2),(-2,-2)]

#隣接リスト
al=defaultdict(lambda: [])

for h in range(H):
    for w in range(W):
        for dh,dw in D:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((0,h+dh,w+dw))    #コスト,toの座標
        for dh,dw in WARP:
            if 0<=h+dh<H and 0<=w+dw<W:
                if S[h+dh][w+dw]==".":
                    al[(h,w)].append((1,h+dh,w+dw))    #コスト,toの座標 ワープはコスト1

d=defaultdict(lambda: float("inf"))    #(h,w):kyori スタート地点からその点までの距離

def dij(x,y):
	d[(x,y)]=0
	hq=[]
	heappush(hq,(0,x,y))
	while hq:
		cost,fro_x,fro_y=heappop(hq)
		for cost,to_x,to_y in al[(fro_x,fro_y)]:
			alt=d[(fro_x,fro_y)]+cost
			if alt<d[(to_x,to_y)]:
				d[(to_x,to_y)]=alt
				heappush(hq, (alt,to_x,to_y))

dij(CH,CW)
if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(1, max_counts+1):
            if not i in colors:
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)




    #print(a ^ b)
if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    num = 1
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    #print(a ^ b)
if __name__ == "__main__":
    run()
### BUGGY CODE ###

a = int(input())
b = [int(i) for i in input().split()]
print((int)(sum(1 for x in range(a) for y in range(a) for z in range(a) if x!=y and y!=z and x!=z and (b[x]<b[y]+b[z] and b[y]<b[x]+b[z] and b[z]<b[x]+b[y]))/6))



### FIXED CODE ###

a = int(input())
arr = [int(i) for i in input().split()]
arr.sort() 
count = 0
for i in range(0,a-2): 
    k = i + 2
    for j in range(i+1,a):
        while (k < a and arr[i] + arr[j] > arr[k]): 
            k += 1
        if(k>j): 
            count += k - j - 1
  
print(count)
### BUGGY CODE ###

import queue,sys,copy
sys.setrecursionlimit(10**7)
INF = 10**10
N = int(input())
x = [0 for _ in range(N)]
y = [0 for _ in range(N)]
for i in range(N):
    x[i], y[i] = map(int,input().split())
ix = [i for i in range(N)]
sort_x_ix = sorted(ix, key=lambda i:x[i])
sort_x = [x[i] for i in sort_x_ix]
sort_y_ix = sorted(ix, key=lambda i:y[i])
sort_y = [y[i] for i in sort_y_ix]

g = [i for i in range(N+1)]
def root(x):
    if g[x] == x : return x
    g[x] = root(g[x])
    return g[x]
q = []
for i in range(N-1):
    q.append((sort_x[i+1]-sort_x[i],sort_x_ix[i],sort_x_ix[i+1]))
    q.append((sort_y[i+1]-sort_y[i],sort_y_ix[i],sort_y_ix[i+1]))

q.sort()
ans = 0
cnt = N

for d,s,t in q:
    if cnt <= 1: break
    if root(s) != root(t):
        ans += d
        cnt -= 1
        g[root(t)] = g[s]
print(ans)

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    xy = [LI() for _ in range(N)]

    x = [(xy[i][0],i) for i in range(N)]
    y = [(xy[i][1],i) for i in range(N)]

    x.sort()
    y.sort()

    edge = []
    p,i = x[0]
    for q,j in x[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    p,i = y[0]
    for q,j in y[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    edge.sort()

    g = [i for i in range(N + 1)]
    g_num = [1 for i in range(N + 1)]

    def find(x):
        if g[x] == x: return x
        g[x] = find(g[x])
        return g[x]

    def union(x, y):
        if find(x) == find(y): return
        if g_num[g[x]] < g_num[g[y]]: x, y = y, x
        g_num[g[x]] += g_num[g[y]]
        g_num[g[y]] = 0
        g[g[y]] = g[x]

    ans = 0
    for v,i,j in edge:
        if find(i) != find(j):
            ans += v
            union(i,j)

    print(ans)



if __name__ == '__main__':
    main()