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

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

dp = [0] * (N + 1)
for k in range(K):
    sta = [max(i-A[i], 0) for i in range(N)]
    end = [min(i+A[i]+1, N) for i in range(N)]
    for s in sta:
        dp[s] += 1
    for e in end:
        dp[e] -= 1
    for i in range(1, len(dp)-1):
        dp[i] += dp[i-1]
    B = dp[:-1]
    if A == B:
        break
    A = B
    dp = [0] * (N + 1)
 
print(' '.join(map(str, A)))


### FIXED CODE ###

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

dp = [0] * (N + 1)
for k in range(K):
    sta = [max(i-A[i], 0) for i in range(N)]
    end = [min(i+A[i]+1, N) for i in range(N)]
    for s in sta:
        dp[s] += 1
    for e in end:
        dp[e] -= 1
    for i in range(1, len(dp)-1):
        dp[i] += dp[i-1]
    B = dp[:-1]
    if A == B:
        break
    A = B
    dp = [0] * (N + 1)
 
print(' '.join(map(str, A)))
### BUGGY CODE ###

from collections import deque

def deqreverse(deq):
    newdeq = deque()
    for _ in range(len(deq)):
        c = deq.pop()
        newdeq.append(c)
    
    return newdeq

S = deque(list(input()))
Q = int(input())

for _ in range(Q):
    Query = [x for x in input().split()]
    if Query[0] == '1':
        S = deqreverse(S)
    else:
        if Query[1] == '1':
            S.appendleft(Query[2])
        else:
            S.append(Query[2])
        
print("".join(S))


### FIXED CODE ###

from collections import deque

def reversedeq(deq):
    newdeq = deque()
    for _ in range(len(deq)):
        c = deq.pop()
        newdeq.append(c)
    
    return newdeq


S = deque(list(input()))
Q = int(input())
reverse_state = False

for _ in range(Q):
    Query = [x for x in input().split()]
    if len(Query) == 1:
        reverse_state = reverse_state ^ 1
    else:
        if reverse_state:
            if Query[1] == '1':
                S.append(Query[2])
            else:
                S.appendleft(Query[2])
        else:
            if Query[1] == '1':
                S.appendleft(Query[2])
            else:
                S.append(Query[2])

if reverse_state:
    S = reversedeq(S)

print("".join(S))
### BUGGY CODE ###

M,A,B = [int(x) for x in input().split()]

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#a = cmb(n,r,mod)
d = 0
for i in range(N):
    f = cmb(M,i+1,mod)
    d = d + f
    
d1 = cmb(M,A,mod)
d2 = cmb(M,B,mod)
print((d-d1-d2)%mod)


### FIXED CODE ###

M,A,B = [int(x) for x in input().split()]

mod = 10**9+7

def cmb(n, r, mod):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod * pow(i+1, mod-2, mod) % mod
    return res

def binary(n):
    return bin(n)[2:]


def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y
d = pow_by_binary_exponentiation(2,M,mod)-1
    
d1 = cmb(M,A,mod)
d2 = cmb(M,B,mod)
print((d-d1-d2)%mod)
### BUGGY CODE ###

s = input()
K = int(input())
ans = set()
for i in range(len(s)):
  for j in range(i,len(s)):
    ans.add(s[i:j+1])
print(sorted(ans)[K-1])

### FIXED CODE ###

s = input()
K = int(input())
ans = set()
for i in range(len(s)):
  for j in range(K):
    ans.add(s[i:i+j+1])
print(sorted(ans)[K-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()
    Q = II()
    
    direction = 1
    for i in range(Q):
        query = input()
        if query == '1':
            direction *= -1
        else:
            _, f, c = query.split()
            if direction == 1:
                if f == '1':
                    S = c + S
                else:
                    S = S + c
            else:
                if f == '1':
                    S = S + c
                else:
                    S = c + S
    if direction == 1:
        print(S)
    else:
        print(S[::-1])

main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()
    Q = II()
    
    direction = 1
    pre = []
    sur = []

    for i in range(Q):
        query = input()
        if query == '1':
            direction *= -1
        else:
            _, f, c = query.split()
            if direction == 1:
                if f == '1':
                    pre.append(c)
                else:
                    sur.append(c)
            else:
                if f == '1':
                    sur.append(c)
                else:
                    pre.append(c)

    if direction == 1:
        ans = "".join(pre[::-1]) + S + "".join(sur)
    else:
        ans = "".join(sur[::-1]) + "".join(S[::-1]) + "".join(pre)
    print(ans)

main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, n, N):
        self.id = n
        self.edges = []
        self.weights = [-1]*N
        self.color = 1
        self.s = 0
    def set_edge(self, e, w):
        self.edges.append(e)
        self.weights[e]=w
    def set_color(self, c_):
        self.color = c_
        self.s = 1

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    # init nodes
    nodes = [Node(i,N) for i in range(N)]
    # set edges
    for ui, vi, wi in zip(u, v, w):
        nodes[ui-1].set_edge(vi-1,wi)
        nodes[vi-1].set_edge(ui-1,wi)

    def cal(node):
        c_ = node.color
        for n in node.edges:
            if nodes[n].s == 0:
                if node.weights[n]%2==1:
                    nodes[n].set_color(c_*-1)
                else:
                    nodes[n].set_color(c_)                
                cal(nodes[n])
    cal(nodes[0])

    for n in nodes:
        print((n.color==1)*1)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):

    G=[dict() for i in range(N)]
    for i in range(N-1):
        ui,vi,wi=u[i],v[i],w[i]
        G[ui-1][vi-1]=wi
        G[vi-1][ui-1]=wi

    dist = [-1]*N
    p = [0]
    dist[0] = 0

    while (len(p)>0):
        k = p.pop()
        for n in G[k]:
            if dist[n]==-1:
                dist[n] = dist[k] + G[k][n]
                p.append(n)
    
    for x in dist:
        print(x%2)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    solve(N, u, v, w)

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

#D-XXOR

n,k=map(int,input().split())
lists=list(map(int,input().split()))
a=format(k,"b")
length=max(len(a),len(format(max(lists),"b")))
uselists=[0]*length
for some in lists:
    check=format(some,"0%ib"%length)
    for i in range(length):
        if check[i]=="1":
            uselists[length-1-i]+=1         
if k>=1:
    for i in range(length):
        if  2**i<=k<2**(i+1):
            order=i
            break            
    ans1=0
    ans2=0
    for j in range(order):
        ans1+=(2**j)*max(uselists[j],n-uselists[j])
    for j in range(order+1,length):
        ans2+=(2**j)*uselists[j]
    ans2+=(2**order)*(n-uselists[order])
    bigger=0
    for g in range(0,k-2**order+1):
        checker=0
        some=format(g,"0%ib"%order)
        for i in range(order):
            if some[i]=="1":
                checker+=(2**(order-1-i))*(n-uselists[i])
            else:
                checker+=(2**(order-1-i))*uselists[i]
        bigger=max(bigger,checker)
    ans2=ans2+bigger
    
    print(max(ans1,ans2))
    
elif k==0:
    ans=0
    for i in range(length):
        if uselists[i]=="1":
            ans+=(2**i)*(n-uselists[i])
        else:
            ans+=(2**i)*uselists[i]
            
    print(ans)
        
    

### FIXED CODE ###

n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)
### BUGGY CODE ###

import sys
def h(i):
 l=2*i;r=l+1
 if r<=H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<=H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]*2000001
o=''
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  o+=f'{A[1]}\n';H-=1
  if H:A[1]=A[H+1];h(1)
print(o[:-1])


### FIXED CODE ###

import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))
### BUGGY CODE ###

# にぶたん練習
n,k=map(int,input().split())
a=list(map(int,input().split()))

# カット後のaの最大長を取り、カット数をシミュレートする。
# k以下でカット可能ならばTrueを返す。
# にぶたんは、効率良くT/Fを判定できる関数が作れるかがみそ。
def f(n):
  cnt=0
  for aa in a:
    cuta=aa
    i=0
    while cuta>n:
      i+=1
      cuta=aa/(i+1)
    cnt+=i
  if cnt>k:
    return False
  return True

# にぶたん実装
l,r=0,max(a)
while r-l>1:
  m=(r+l)//2
  if f(m):
    r=m
  else:
    l=m

# 今回は、rが必要な値。厳密な値は(l<x<=r)になるので、小数点切り上げでrとなる。
print(r)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# template: v1.3.1

# 丸太の分割分割問題。
# 速度の観点から、「答えの二分探索」が必要。典型らしい。



import io
import sys
import math

### DEBUG ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
2 1
1 50
"""

# Worst
# _INPUT = f"{str(2*(10**5))} {str(10**9)}\n{(str(10**9)+' ')*(2*(10**5)) }"
# _INPUT = f"{str(2*(10**5))} {str(10**9)}\n{(str(10**9)+' ')*(2*(10**5)) }"


_EXPECTED = """\
ABC
"""
if _DEB:
    sys.stdin = io.StringIO(_INPUT)
    print("!! Debug Mode !!")


def logd(str):
    if _DEB: print(f"[deb] {str}")

# is_m_OK?
def f(m):
    cut=0
    for aa in a:
        c=math.ceil(aa/m)
        cut+=c-1
        if cut > k:
            return False
    return True
#m=7,a=[7,9]


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

### Solve ####
def solve():
    # Process

    ans=0
    l,r=0,10**9
    while abs(r-l)!=1:
        m=(l+r)//2
        if f(m): # m is ok: Go left
            r=m
        else: # m is ng : Go right
            l=m
    
    ans=r
    # ans=min(r,max(a))

    # OUPUT
    ans = str(ans)
    print(ans)
    return ans

### MAIN ###
if __name__ == "__main__":
    ans = solve()

    # Checker
    if _DEB:
        if _EXPECTED.strip() == ans.strip(): print("\n!! Success !!")
        else: print(f"\n!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")
### BUGGY CODE ###

import bisect

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if k<=ncc:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    for i in range(c1):
      cnt+=bisect.bisect_right(arr2,mid//arr1[i])
    if cnt>k:
      r=mid
    else:
      l=mid
  print(-r)
elif k<=(ncc+zcc):
  print(0)
else:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k-=(ncc+zcc)
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    for i in range(c1):
      tmp=bisect.bisect_right(arr1,mid//arr1[i])
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    for i in range(c2):
      tmp=bisect.bisect_right(arr2,mid//arr2[i])
      if arr2[i]**2<mid:
        tmp-=1
      cnt2+=tmp
    cnt2=cnt2//2
    cnt=cnt1+cnt2
    if cnt>=k:
      r=mid
    else:
      l=mid
  print(r)


### FIXED CODE ###

#incited numpy source code from 'https://atcoder.jp/contests/abc155/submissions/10155744'

import numpy

n,k=map(int,input().split())
arr=list(map(int,input().split()))
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if ncc<k<=(ncc+zcc):
  print(0)
else:
  arr=numpy.array(arr,dtype=int)
  ms=numpy.msort(numpy.abs(arr[arr<0]))
  ps=numpy.msort(arr[arr>0])
  if k<=ncc:
    k=ncc-k
    l=0
    r=10**18+1
    while r-l!=1:
      mid=(l+r)//2
      cnt=numpy.searchsorted(ps,mid//ms,side='right')
      if cnt.sum()>k:
        r=mid
      else:
        l=mid
    print(-r)
  elif k<=(ncc+zcc):
    print(0)
  else:
    l=0
    r=10**18+1
    k-=(ncc+zcc)
    while r-l!=1:
      mid=(l+r)//2
      cnt1=numpy.searchsorted(ps,mid//ps,side='right')
      dup1=ps**2<=mid
      cnt2=numpy.searchsorted(ms,mid//ms,side='right')
      dup2=ms**2<=mid
      if (cnt1.sum()-dup1.sum()+cnt2.sum()-dup2.sum())//2>=k:
        r=mid
      else:
        l=mid
    print(r)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
ans = None
for i in range(m):
    l, r = map(int, input().split())
    card = set(range(l, r + 1))
    if ans is None:
        ans = card
    else:
        ans = ans.intersection(card)

print(len(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m = map(int, input().split())
l_key = []
r_key = []
for i in range(m):
    l, r = map(int, input().split())
    l_key.append(l)
    r_key.append(r)

print(max(0, min(r_key) - max(l_key) + 1))
### BUGGY CODE ###

n = int(input())
R = [int(input()) for i in range(n)]
profit= R[1] - R[0]
for i in range(n):
    for j in range(i+1,n):
        tmp = R[j]-R[i]
        if profit < tmp:
            profit = tmp

print(profit)

### FIXED CODE ###

n = int(input())
R = [int(input()) for i in range(n)]
profit= R[1] - R[0]
mn = R[0]
R.pop(0)
for i in R:
    if profit < i - mn:
        profit = i - mn
        if 0 > i - mn:
            mn = i
    elif mn > i:
        mn = i

print(profit)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
s = list(map(int, input().split()))
g = [[] for i in range(n)]

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

q = deque()
chk = [0] * n
res = []

for i in range(n):
    tmp = set()
    if not chk[i]:
        q.append(i)
        while q:
            v = q.pop()
            chk[v] = 1
            tmp.add(v)
            for u in g[v]:
                if chk[u] == 1:
                    continue
                q.append(u)
        res.append(tmp)

ans = 0
for re in res:
    tmp2 = set()
    for r in re:
        tmp2.add(s[r] - 1)
    ans += len(tmp2 & re)
print(ans)


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
s = list(map(int, input().split()))
g = [[] for i in range(n)]

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

q = deque()
chk = [0] * n
res = []

for i in range(n):
    tmp = set()
    if not chk[i]:
        q.append(i)
        while q:
            v = q.pop()
            chk[v] = 1
            tmp.add(v)
            for u in g[v]:
                if chk[u] == 1:
                    continue
                q.append(u)
        res.append(tmp)

ans = 0
for re in res:
    tmp2 = set()
    for r in re:
        tmp2.add(s[r] - 1)
    ans += len(tmp2 & re)
print(ans)
### BUGGY CODE ###

X = int(input())
A = 1
K = 1
while K < X:
    A += 1
    K = A ** 5
S = A - 4
w = 0
while w != 1:
    Q = S ** 5 - X
    if Q < 0:
        B = 0
        while (Q < B**5):
            B -= 1
        if (Q == B**5):
            w += 1
        else:
            S += 1
        
    elif Q > 0:
        B = 0
        while (Q > B**5):
            B += 1
        if (Q == B**5):
            w += 1
        else:
            S += 1
print(S,B)

### FIXED CODE ###

X = int(input())
for i in range (240):
    for j in range (240):
        s = (i -120)**5 - (j -120)**5
        if s == X:
            A = i-120
            B = j -120
print(A,B)
### BUGGY CODE ###

import math

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += math.gcd(math.gcd(i, j), l)
print(ans)


### FIXED CODE ###

from math import gcd

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            ans += gcd(gcd(i, j), k)
print(ans)
### BUGGY CODE ###

from itertools import product


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    aa = list(product(a[:], repeat=2))
    print(sum(sorted(list(map(lambda x: x[0] + x[1], aa)), reverse=True)[:m]))
   
resolve()

### FIXED CODE ###

import sys
from itertools import accumulate
from bisect import bisect_left

n, m, *a = map(int, sys.stdin.read().split())
a.sort()


def f(x):
    # 幸福度がx未満となる組み合わせの個数を数える
    cnt = 0
    for ai in a:
        cnt += bisect_left(a, x-ai)
    # 幸福度がx以上の組み合わせの個数がm未満かどうか
    return n * n - cnt < m


left = a[0] * 2
right = a[-1] * 2
while right - left > 1:
    mid = (right + left) // 2
    if f(mid):
        right = mid
    else:
        left = mid
ans = 0
cumsum = [0] + list(accumulate(a))
j = 0
for ai in a:
    i = bisect_left(a, left-ai)
    j += n - i
    ans += ai * (n - i) + cumsum[-1] - cumsum[i]
ans += (m - j) * left
print(ans)
### BUGGY CODE ###

S = str(input())
T = str(input())

for i in range(len(S)):
    if S[i] == T[i]:
        continue
    else:
        s_before = S[i]
        S = S.replace(T[i], ',')
        S = S.replace(S[i], T[i])
        S = S.replace(',', s_before)
    if (S == T):
        print("Yes")
        exit()

if (S == T):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import string

alphabet = string.ascii_lowercase

S = str(input())
T = str(input())
start = [-1 for i in range(len(alphabet))]
goal = [-1 for i in range(len(alphabet))]
tf = True

for i in range(len(S)):
    a = alphabet.index(S[i])
    b = alphabet.index(T[i])

    if (start[a] != -1 or goal[b] != -1):
        if (start[a] != b or goal[b] != a):
            tf = False
            break
    else:
        start[a] = b
        goal[b] = a

if tf:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import heapq
N, M = [int(x) for x in input().split()]
AB_list = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: int(x[0]))
h = []
ans = 0
for i in range(1, M+1):
    lst = AB_list[:]
    for A, B in lst:
        if (A <= i):
            tmp = AB_list.pop(0)
            heapq.heappush(h, -1 * tmp[1])
        else: break
    # print(AB_list, h)
    if (len(h)):
        ans += -1 * heapq.heappop(h)
print(ans)



### FIXED CODE ###

import heapq
N, M = [int(x) for x in input().split()]
AB_list = [[] for _ in range(M)]
for _ in range(N):
    A, B = list(map(int, input().split()))
    if (A > M): continue
    AB_list[A-1].append(B)
h = []
ans = 0
for i in range(M):
    for B in AB_list[i]:
        heapq.heappush(h, -B)
    # print(AB_list, h)
    if (len(h)):
        ans += -heapq.heappop(h)
print(ans)
### BUGGY CODE ###

# C - 100 to 105
from collections import defaultdict


def main():
    X = int(input())
    items = tuple(range(100, 106))
    dp = defaultdict(bool)
    dp[0] = True
    while max(dp.keys()) < X:
        for possible_price in tuple(dp.keys()):
            for item in items:
                dp[possible_price + item] = True
    print(int(X in dp))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# C - 100 to 105
def main():
    X = int(input())
    check = lambda x: x * 100 <= X <= x * 105
    is_possible = any(check(i) for i in range(X))
    print(int(is_possible))


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

def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [[10**9+1] * (N+1) for _ in range(N+1)]
    for i in range(N):
        l[i][i+1] = 0
    for j in range(2, N+1):
        for i in range(N):
            m = i + j
            if m > N:
                continue
            l[i][m] = min(l[i][k] + l[k][m] for k in range(i+1, m)) + sum(a[k] for k in range(i, m))
    return l[0][-1]

print(main())


### FIXED CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = [[10**9+1] * (N+1) for _ in range(N+1)]
    s = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1):
        for j in range(i+1, N+1):
            s[i][j] = s[i][j-1] + a[j-1]
    for i in range(N):
        l[i][i+1] = 0
    for j in range(2, N+1):
        for i in range(N):
            m = i + j
            if m > N:
                continue
            l[i][m] = min(l[i][k] + l[k][m] for k in range(i+1, m)) + s[i][m]
    return l[0][-1]

print(main())
### BUGGY CODE ###

N=int(input());AB=[list(map(int,input().split())) for _ in range(1,N)]
nd=[0 for _ in range(N)]
table = [[] for _ in range(N)]
for a,b in AB:
  table[a-1].append(b)
  nd[a-1]+=1
  nd[b-1]+=1

for li in table:
  li.sort()

K=max(nd)
print(K)
co=[0 for _ in range(N)]
ans=dict()
for x,li in enumerate(table):
  c=[i for i in range(1,K+1) if i != co[x]]
  for b,y in zip(li,c):
    co[b-1]=y
    ans[(x+1,b)]=y

for a,b in AB:
  print(ans[(a,b)])


### FIXED CODE ###

import sys

input = sys.stdin.readline
N=int(input());AB=[tuple(map(int,input().split())) for _ in range(1,N)]

co=[0 for _ in range(N)]
prev=0
color=1
for a,b in sorted(AB):
  if prev!=a:
    color=1
  if co[a-1]==color:
    color+=1
  co[b-1]=color
  prev=a
  color+=1

print(max(co))
for _,b in AB:
  print(co[b-1])