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

from bisect import bisect_left
 
 
N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        if time[q] == -1 or time[q] > x:
            time[q] = x
 
for q in querys:
    print(time[q])

### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

n,m=(int(x) for x in input().split())
l = [int(i) for i in input().split()]

l.sort(reverse=True)
for i in range(m):
    l[0]=l[0]//2
    l.sort(reverse=True)
total=0
for j in range(len(l)):
    total+=l[j]

print(total)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
### BUGGY CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

set_list = list(set(a_list))

for i in range(n):
    if i+1 in set_list:
        print(a_list.count(i+1))
    else:
        print("0")

### FIXED CODE ###

n = input()
line = input()
n = int(n)
a_list = line.split(" ")
a_list = [int(a) for a in a_list]

ans_list = [0 for i in range(n)]

for a in a_list:
    ans_list[a-1] = ans_list[a-1] + 1

for ans in ans_list:
    print(ans)
### BUGGY CODE ###

n = int(input())
from functools import reduce
#import numpy as np
def f(x):
  rtn = {}
  i = 2
  while x > 1:
    if x % i == 0:
      x //= i
      if i in rtn:
        rtn[i] += 1
      else:
        rtn[i] = 1
    else:
      i += 1
  return rtn

def lcm(xs,ys):
  rtn = {}
  for i in xs:
    if i in ys:
      rtn[i] = max(xs[i], ys[i])
    else:
      rtn[i] = xs[i]
  for i in ys:
    if not i in rtn:
      rtn[i] = ys[i]
  return rtn
    
a = list(map(lambda x:f(int(x)), input().split()))
l = reduce(lcm, a)
ans = 0
mod = 10**9 + 7
for j in range(n):
  b = 1
  for i in l:
    if i in a[j]:
      b *= i ** (l[i] - a[j][i])
    else:
      b *= i ** l[i]
  ans += b
  ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

X = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((i, x, y))

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))
### BUGGY CODE ###

import fractions
from functools import reduce

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
   
M = 1  
for i in range(0,N):
  L1 = X[:i]
  R1 = X[i+1:]
  if not L1:
    M = max(M, gcd_list(R1))
  elif not R1:
    M = max(M, gcd_list(L1))
  else:
    L = gcd_list(L1)
    R = gcd_list(R1)
    M = max(M, fractions.gcd(L,R))

print(M)

### FIXED CODE ###

#解説の方針にしたがった
import fractions

N = int(input())
X = list(map(int, input().split()))
   
M = 1  
L = [0 for i in range(100004)] #L(0)=0
R = [0 for i in range(100004)]  #R(N+1) = 0

for i in range(N):
  L[i] = (fractions.gcd(L[i-1],X[i]))

for i in reversed(range(N)):
  #print(i)
  R[i] = (fractions.gcd(R[i+1],X[i]))
    
ans = 1

#print(L)
#print(R)
for i in range(N):
  ans = max(ans, fractions.gcd(L[i-1],R[i+1]))

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

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

sum_l = 0
sum = 0
sum_p = 0
sum_p_len = []
max = 0

for i in range(len(p) - K + 1):
    l = p[i:K]
    for j in l:
        sum_l += j
    if max < sum_l:
        max = sum_l
        sum_p_len = l
    sum_l = 0
    K += 1

# print(sum_p_len)

for i in sum_p_len:
    for j in range(i):
        j += 1
        sum += j / i
    sum_p += sum
    sum = 0

print(sum_p)


### FIXED CODE ###

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

for i in range(len(p)):
    p[i] = (p[i] + 1) / 2

sum = 0
S = [0]

for i in p:
    sum += i
    S.append(sum)

# print(S)

max = 0

for i in range(len(p) - K + 1):
    s = S[i + K] - S[i]
    # print(s)
    if max < s:
        max = s

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

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

tree = {}

tmp = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
will_go = [0]
already = []

while will_go:
  tmp2 = []
  now = will_go.pop()
  already.append(now)
  for node in tmp:
    if (now == node[0]) & (node[1] not in already):
      will_go.append(node[1])
      if now not in tree:
        tree[now] = [node[1]]
      else:
        tree[now].append(node[1])
    if (now == node[1]) & (node[0] not in already):
      will_go.append(node[0])
      if now not in tree:
        tree[now] = [node[0]]
      else:
        tree[now].append(node[0])
    else:
      tmp2.append(node)
  tmp = [i for i in tmp2]

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

### FIXED CODE ###

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
ald = [True]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
ald[0] = False
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    for root in tree[now]:
      if ald[root]:
        ald[root] = False
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)
### BUGGY CODE ###

###################
# AC:1102 ms(PyPy)
###################

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for c in range(c1,c2+1):
        ans += ((r2+1) * modcmb(c+r2+1, r2+1, MOD) - r1 * modcmb(c+r1, r1, MOD)) * pow(c+1, MOD-2, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def f(r, c):
    return modcmb(r+c, r, MOD)


def main():
    prepare(2*10**6+10, MOD)
    r1,c1,r2,c2 = map(int, input().split())

    ans = 0
    for i in range(1,c2+2):
        ans += f(r2, i)
        ans %= MOD

    for i in range(1,c2+2):
        ans -= f(r1-1, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans -= f(r2, i)
        ans %= MOD

    for i in range(1,c1+1):
        ans += f(r1-1, i)
        ans %= MOD

    print(ans % MOD)


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

N=int(input())
S=[str(input()) for i in range(N)]

SA=list(set(S))
l=len(SA)
d=[0]*l
for i in range(l):
  d[i]=S.count(SA[i])
  S.remove(SA[i])

m=max(d)
sm=[]
for i in range(l):
  if d[i]==m:
    sm.append(SA[i])

sm.sort()
for i in sm:
  print(i)

### FIXED CODE ###

import collections
N=int(input())
S=[]
for i in range(N):
   S.append(str(input())) 
c=collections.Counter(S)
c_sorted=sorted(c.items(),key=lambda x:x[0])
s=max(c.values())
for i in c_sorted:
    if i[1]==s:
        print(i[0])
### BUGGY CODE ###

n = int(input())

ans = 0

for a in range(1, n):
	b = 1
	while a * b < n:
		ans += 1
		b += 1
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0

for a in range(1, n):
	if n % a == 0:
		ans += n // a - 1
	else:
		ans += n // a
print(ans)
### BUGGY CODE ###

import sys
n = int(input())
x = int(input(),2)
bitx = bin(x).count('1')

ans = [0]*(bitx+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
for i in range(n):
    y = x^(1<<(n-i-1))
    if y>>(n-i-1)&1:
        bity = bitx+1
    else:
        bity = bitx-1
    if bity != 0:
        t = y % bity
        l.append(str(1+ans[t]))
    else:
        l.append(str(0))
    #print(1+ans[t])
print('\n'.join(l))

### FIXED CODE ###

n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0


if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
            xmm += pow(2, n-(i+1), bitm)
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
else:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
print('\n'.join(l))
### BUGGY CODE ###

N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    a_list.append(min(ans))
    graph[i].remove(min(ans))
    graph[j].remove(min(ans))
print(max(a_list))
for i in a_list:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split(' '))
    E[a].append((b, i))
    E[b].append((a, i))
K = max(len(e) for e in E)
print(K)
ans = [-1] * (N - 1)


def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1


dfs()
for i in ans:
    print(i)
### BUGGY CODE ###

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

C = [0]*N
for i in range(M):
    L, R = map(int, input().split())
    for j in range(L, R+1):
        C[j-1] += 1

ans = 0
for i in range(N):
    if C[i] == M:
        ans += 1

print(ans)

### FIXED CODE ###

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

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

ans = 0
l = max(L)
r = min(R)
for i in range(N):
    if i+1 >= l and i+1 <= r:
        ans += 1

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

data = input().split()
N = int(data[0])
K = int(data[1])

TL = list(input())
TLLlist = []
now = TL[0]
nowlist = now
anslist = []

for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLLlist.append(len(nowlist))

hjm = 0
if TL[0] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    hjm = 1
elif TL[0] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    hjm = 2
for lop in range(hjm,len(TLLlist),2):
    if 2*K +  lop > len(TLLlist):
        break
    anslist.append( sum(TLLlist[lop:2*K + 1 + lop]) )


#print(TLlist)
#print(TLLlist)
#print(anslist)
print(max(anslist))



### FIXED CODE ###

data = input().split()
N = int(data[0])
K = int(data[1])
 
TL = list(input())
TLlist = []
TLLlist = []
now = TL[0]
nowlist = now
anslist = []
 
for lop in range(1,len(TL)):
    if not (now == TL[lop]):
        TLlist.append(nowlist)
        TLLlist.append(len(nowlist))
        nowlist = TL[lop]
        now = TL[lop]
    else:
        nowlist += now
TLlist.append(nowlist)
TLLlist.append(len(nowlist))
 
 
if TLlist[0][:1] == "0" :
    anslist.append( sum(TLLlist[:2*K]) )
    anslist.append( sum(TLLlist[1:2*K + 2]) )
    for lop in range(3,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
elif TLlist[0][:1] == "1" :
    anslist.append( sum(TLLlist[:2*K + 1 ]) )
    for lop in range(2,len(TLlist),2):
        if 2*K +  lop > len(TLlist):
            break
        anslist.append( anslist[len(anslist)-1] - sum(TLLlist[lop-2:lop]) + sum(TLLlist[lop + 2*K - 1 : lop + 2*K + 1])  )
 
print(max(anslist))
### BUGGY CODE ###

S = input()
T = input()
for i in range(len(S)):
    kensa1 = [index for index, word in enumerate(S) if S[i] == word]
    kensa2 = [index for index, word in enumerate(T) if T[i] == word]

    if kensa1 != kensa2:
        print('No')
        break
else:
    print('Yes')

### FIXED CODE ###

S = input()
T = input()

used = []
res  = []

for i in range(len(S)):
    if S[i] not in used:
        used.append(S[i])
    res.append(used.index(S[i]))

#print(used)
#print(res)
used = []
ret = []

for i in range(len(T)):
    if T[i] not in used:
        used.append(T[i])
    ret.append(used.index(T[i]))

if res == ret:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

frag = False

for i in range(n):
  for j in range(n):
    if i != j and a[i] == a[j]:
      frag = True
if frag:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

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

b = set(a)

if len(a) == len(b):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append([x,tmp])
        return

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = get_unique_list(q)
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)


### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)
### BUGGY CODE ###

num_of_employee = int(input())
employeenos = list(map(int, input().split()))

for i in range(1, num_of_employee + 1):
    print(employeenos.count(i))


### FIXED CODE ###

import collections

num_of_employee = int(input())
employeenos = list(map(int, input().split()))

c = collections.Counter(employeenos)
for i in range(1, num_of_employee + 1):
    print(c[i])
### BUGGY CODE ###

from collections import deque

INF = 10**6

H,W = map(int,input().split())
C1,C2 =map(lambda x : int(x) - 1,input().split())
D1,D2 = map(lambda x : int(x) - 1,input().split())

S = [input() for _ in range (H)]
t = [[INF]*W for _ in range (H)]


for h in range (H):
    Sh = S[h]
    th = t[h]
    for w in range (W):
        if Sh[w] == '#':
            th[w] = -1


q = deque([(C1,C2)])
a = 0
t[C1][C2] = a

while q:
    warpq = []
    while q:
        h,w = q.popleft()
        warpq.append((h,w))
        if 0 < h and t[h-1][w] > a:
            t[h-1][w] = a
            q.append((h-1,w))
        if H-1 > h and t[h+1][w] > a:
            t[h+1][w] = a
            q.append((h+1,w))
        if 0 < w and t[h][w-1] > a:
            t[h][w-1] = a
            q.append((h,w-1))
        if w < W-1 and t[h][w+1] > a:
            t[h][w+1] = a
            q.append((h,w+1))

    if t[D1][D2]!= INF:
        break

    a+=1

    for h,w in warpq:
        for i in range (max(0,h-2),min(H,h+3)):
            ti = t[i]
            for j in range (max(0,w-2),min(W,w+3)):
                if ti[j] >a:
                    ti[j] = a
                    q.append((i,j))


if t[D1][D2] == INF:
    print(-1)
else:
    print(t[D1][D2])


### FIXED CODE ###

from collections import deque


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

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()
### BUGGY CODE ###

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j < WV[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - WV[i][0]] + WV[i][1])


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


### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
dp = {0: 0}
for i in range(N):
    for j in sorted(dp.keys(), reverse=True):
        w, v = wv[i][0], wv[i][1]
        nw = dp[j] + w
        nv = j + v
        if nw <= W:
            if nv in dp:
                if nw < dp[nv]:
                    dp[nv] = nw
            else:
                dp[nv] = nw


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


#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    As = [tuple(map(int, input().split())) for _ in range(N-1)]

    m = [[0 for _ in range(N)] for _ in range(N)]
    for u, v in As:
        m[u-1][v-1] = 1
        m[v-1][u-1] = 1

    n_e = max([l.count(1) for l in m])
    print(n_e)

    ans = [[0 for _ in range(N)] for _ in range(N)]

    def dfs(u, c0):
        c = c0
        for v in range(N):
            if m[u][v]:
                m[u][v]=0
                m[v][u]=0
                c = c%n_e + 1
                ans[u][v] = c
                ans[v][u] = c
                dfs(v, c)

    dfs(0, 0)

    for u, v in As:
        print(ans[u-1][v-1])



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)


### FIXED CODE ###


#%%
import sys
sys.setrecursionlimit(100000)

def input():
    return sys.stdin.readline().rstrip()

def main():
    N = int(input())

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

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

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



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc146","d",main)