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

def main():
    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data():
        return sys.stdin.readline().strip()

    def mdata():
        return map(int, data().split())

    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(10e9)

    s = data()
    t = data()
    dp = [[0] * (len(s) + 1) for i in range(len(t) + 1)]
    for i in range(1, len(t) + 1):
        for j in range(1, len(s) + 1):
            if s[j - 1] == t[i - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    m = max(max(dp))
    ans = ''
    for i in range(len(t) - 1, -1, -1):
        for j in range(len(s) - 1, -1, -1):
            if dp[i + 1][j + 1] == m and s[j] == t[i]:
                ans = s[j] + ans
                m -= 1
                break
    out(ans+'\n')


if __name__ == '__main__':
    main()

### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(int, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(10e9)


s=data()
t=data()
dp=[[0]*(len(s)+1) for i in range(len(t)+1)]
for i in range(1,len(t)+1):
    for j in range(1,len(s)+1):
        if s[j-1]==t[i-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
m=max(max(dp))
ans=''
for i in range(len(t)-1,-1,-1):
    for j in range(len(s)-1,-1,-1):
        if dp[i+1][j+1]==m and s[j]==t[i]:
            ans=s[j]+ans
            m-=1
            break
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for j in range(M)]

#dp[i]:i段目までの上がり方

div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1

def stairs():
    for i in range(N-1):
        if not i+2 in a:
            dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for j in range(M)]

#dp[i]:i段目までの上がり方

div = 1000000007

dp = [0] * (N+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1
else:
    del a[0]

def stairs():
    for i in range(N-1):
        if dp[i+1] == 0 and dp[i] == 0:
            break
        if a:
            if i+2 == a[0]:
                del a[0]
                continue
        dp[i+2] = (dp[i+1] + dp[i]) % div
    print(dp[N])

stairs()
### BUGGY CODE ###

def solve():
  r,g,b,n = (int(i) for i in input().split())
  ans = 0
  for i in range(0,1+n//r):
    for j in range(0,1+n//g):
        rest = n-(i*r + j*g)
        #print(rest)
        if rest%b == 0 and rest >= 0:
          ans += 1
  print(ans)
solve()

### FIXED CODE ###

def solve():
  r,g,b,n = (int(i) for i in input().split())
  ans = 0
  for i in range(0,1+n//r):
    for j in range(0,1+n//g):
        rest = n-(i*r + j*g)
        #print(rest)
        if rest%b == 0 and rest >= 0:
          ans += 1
  print(ans)
solve()
### BUGGY CODE ###


from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

x = 1
for i in range(N):
  x = (x*A[i]) // gcd(x, A[i])

ans = 0
for a in A:
  ans += x//a
  ans %= mod
print(ans)


### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

x = 1
for i in range(N):
  x = (x*A[i]) // gcd(x, A[i])

ans = 0
for a in A:
  ans += x//a
  #ans %= mod
print(ans%mod)
### BUGGY CODE ###

from collections import deque

s = input()
Q = int(input())

l = deque()
l.append(s)

rev = True
for i in range(Q):
    q = list(input().split())
    if q[0] == "1":
        rev = not rev
    else:
        if rev:
            if q[1] == "1":
                l.appendleft(q[2])
            else:
                l.append(q[2])
        else:
            if q[1] == "1":
                l.append(q[2])
            else:
                l.appendleft(q[2])

ans = ""    
for i in l:
    ans += i

if not rev:
    print(ans[::-1])
else:
    print(ans)

### FIXED CODE ###

from collections import deque

s=input()
n=int(input())
q=deque()
q.append(s)
f=1
for i in range(n):
    t=list(input().split())
    if int(t[0])==1:
        f*=-1
    else:
        if f==1:
            if t[1]=='1' :
                q.appendleft(t[2])
            else:
                q.append(t[2])
        else:
            if t[1]=='2':
                q.appendleft(t[2])
            else:    
                q.append(t[2])
ans=''.join(q)
if f==-1:
    ans=ans[::-1]


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

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10**9+7

def matrixmul(A, B):
    n = len(A)
    C = []
    for i in range(n):
        c = [sum([A[i][k]*B[k][j] for k in range(n)])%mod for j in range(n)]
        C.append(c)
    return C

def matrixpow(A, n):
    if n == 1:
        return A
    if n&1 == 1:
        return matrixmul(matrixpow(A, n-1), A)
    else:
        return matrixmul(matrixpow(A, n//2), matrixpow(A, n//2))
    
An = matrixpow(A, K)
ans = 0
for i in range(N):
    for j in range(N):
        ans = (An[i][j]+ans)%mod
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
mod = 10**9+7

def matrixmul(A, B):
    n = len(A)
    C = []
    for i in range(n):
        c = []
        for j in range(n):
            num = 0
            for k in range(n):
                num = (A[i][k]*B[k][j] + num)%mod
            c.append(num)
        C.append(c)
    return C

now = [[1 if i == j else 0 for i in range(N)] for j in range(N)]        

while K:
    if K&1 == 1:
        now = matrixmul(now, A)
    K //= 2
    A = matrixmul(A, A)

ans = 0
for i in range(N):
    for j in range(N):
        ans = (now[i][j]+ans)%mod
print(ans)
### BUGGY CODE ###

K = int(input())  #スペース抜きの複数行,１文字ずつ
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

A = []
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            #print(i, j, k)
            #print(gcd_list([i, j, k]))
            A.append(gcd_list([i, j, k]))

print(sum(A))

### FIXED CODE ###

K = int(input())  #スペース抜きの複数行,１文字ずつ
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

A = []
for i in range(1, K + 1):
    for j in range(i, K+1):
        for k in range(j, K + 1):
            if i == j and j == k and k == i:
                #print(i,j,k)
                A.append(gcd_list([i, j, k]))
            elif i != j and j != k and k != i:
                A.append(gcd_list([i, j, k])*6)
            else:
                #print(i,j,k)
                A.append(gcd_list([i, j, k])*3)           

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

#coding:utf-8
import math
import collections

def prime():
    prime = [2, 3]
    for i in range(5, 1000000, 2):
        flag = True
        for j in range(1, len(prime)):
            if prime[j] ** 2 > i:
                break
            if i % prime[j] == 0:
                flag = False
                break
        if flag:
            prime.append(i)
    return prime

if __name__ == "__main__":
    x = int(input())
    prime = prime()
    #print(prime)
    for num in prime:
        if int(num) >= x:
            print(num)
            break

### FIXED CODE ###

#coding:utf-8
import math

#素数判定
def prime(n):
    if n == 2:
        return True
    elif (n < 2) or (n % 2 == 0):
        return  False
    else:
        i = 3
        while i <= math.sqrt(n):
            if n % i == 0:
                return False
            i += 2

        return True

if __name__ == "__main__":
    x = int(input())
    num = x

    while prime(num) == False:
        num += 1

    print(num)
### BUGGY CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=int)
@njit
def calc(A, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-A[i]))
        right = int(min(N-1, i+A[i]))
        b[left:right+1] +=1
 
    A = b.copy()
    if step < K:
        step += 1
        return calc(A, step)
    else:
        return A
ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
from numba import njit

N, K = list(map(int, input().strip().split()))
A = np.array(input().strip().split(), dtype=np.int64)

@njit(cache=True)
def calc(a, step):
    b = np.array([0]*N)
    for i in range(N):
        left = int(max(0, i-a[i]))
        right = int(min(N-1, i+a[i]))
        b[left] += 1
        if right + 1 < N:
            b[right+1] -= 1
    b = np.cumsum(b)
    
    if np.all(a==b) or step>=K:
        return b
    else:
        step += 1
        return calc(b, step)

ans = calc(A, 1)
ans = [str(x) for x in ans]
print(" ".join(ans))
### BUGGY CODE ###

N,M = map(int, input().split())
LRD = [ [int(j) for j in input().split()] for _ in range(M)]
MAP = [ [] for _ in range(N+1)]
CR  = [ [0] * (N+1) for _ in range(N+1)]

def canDFS(node, par, target):
    if len(list(filter(lambda x: x!=par, MAP[node]))) == 0:
        return float("inf")
    if target in MAP[node]:
        return CR[node][target]

    ans = float("inf")
    for ch in MAP[node]:
        if ch == par: continue
        tmp = CR[node][ch]
        tmp += canDFS(ch, node,target)
        if tmp < ans:
            ans = tmp
    return ans
        


for i in range(M):
    L,R,D = LRD[i]
    
    LtoR = canDFS(L, -1, R)
    # print("LRD:", L,R,D, LtoR)

    if LtoR == D:
        continue
    elif LtoR == float("inf"):
        MAP[L].append(R)
        MAP[R].append(L)
        
        CR[L][R] = D
        CR[R][L] = -D
        # print("\tappend")
    else:
        print("No")
        exit(0)
print("Yes")

    

    



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
N,M = map(int, input().split())
input = sys.stdin.readline
LRD = [ [int(j) for j in input().split()] for _ in range(M)]

data = [x for x in range(N+1)]
rank = [0]  * (N+1)
diff_weight = [0] * (N+1)

def root(x):
    if data[x] == x:
        return x
    else:
        r = root( data[x] )
        diff_weight[x] += diff_weight[ data[x] ]
        data[x] = r
        return r

def weight(x):
    # _ = root(x)
    return diff_weight[x]


def diff(x,y):
    return weight(y) - weight(x)

def merge(x,y,w):
    w  += weight(x); w -= weight(y)
    x = root(x)
    y = root(y)
    if x == y: return False
    if rank[x] < rank[y]: x,y = y,x; w = -w
    if rank[x] == rank[y]: rank[x] += 1
    data[y] = x
    diff_weight[y] = w
    return True

def issame(x,y):
    return root(x) == root(y)

for i in range(M):
    L,R,D = LRD[i]
    # print(L,R,D)
    if not issame(L,R):
        _  = merge(L,R,D)
    else:
        if diff(L,R) != D:
            print("No")
            exit(0)
            
print("Yes")
### BUGGY CODE ###

import collections

n = int(input())
ans = 0

l = []

for _ in range(n):
    s = collections.Counter(input())
    for le in l:
        if le == s:
            ans += 1

    l.append(s)

print(ans)

### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
### BUGGY CODE ###

from heapq import heappush,heappop 
from math import sqrt
inf=float("inf")

xs,ys,xt,yt=map(int,input().split())
n=int(input())

q=[]
l=[(xs,ys,0),(xt,yt,0)]+[tuple(map(int,input().split())) for _ in range(n)]

sizeV=len(l)
rests={i for i in range(sizeV)}
cost=[inf]*sizeV
cost[0]=0
heappush(q,(0,0))

while q:
  c1,i=heappop(q)
  if c1>cost[i]:continue

  rests.remove(i)
  if not rests:break

  xi,yi,ri=l[i]
  for j in rests:
    xj,yj,rj=l[j]
    d=max(0.0,sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj)
    c2=c1+d
    if c2<cost[j]:
      cost[j]=c2
      heappush(q,(c2,j))

print(cost[1])

### FIXED CODE ###

from heapq import heappush,heappop 
from math import sqrt
inf=float("inf")

xs,ys,xt,yt=map(int,input().split())
n=int(input())

q=[]
l=[(xs,ys,0),(xt,yt,0)]+[tuple(map(int,input().split())) for _ in range(n)]

sizeV=len(l)
rests=set(range(sizeV))
cost=[inf]*sizeV
cost[0]=0
heappush(q,(0,0))

while q:
  c1,i=heappop(q)
  if c1>cost[i]:continue

  rests.remove(i)
  if not rests:break

  xi,yi,ri=l[i]
  for j in rests:
    xj,yj,rj=l[j]
    d=max(0.0,sqrt((xj-xi)**2+(yj-yi)**2)-ri-rj)
    c2=c1+d
    if c2<cost[j]:
      cost[j]=c2
      heappush(q,(c2,j))

print(cost[1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    ans = [0] * N
    con = deque([[] for i in range(N)])

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
edge = [[] for i in range(N)]
ops = []
ans = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
for _ in range(Q):
    ops.append(tuple(map(int, input().split())))

for op in ops:
    node = op[0] - 1
    pnt = op[1]
    ans[node] += pnt

stack = deque()
stack.append((0, -1))

while stack:
    st = stack.pop()
    node, parent = st[0], st[1]
    children = edge[node]
    for child in children:
        if child == parent:
            continue
        ans[child] += ans[node]
        stack.append((child, node))

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

import numpy as np

h, w = map(int, input().split())
s = []
for i in range(h):
    line = list(input())
    s.append(line)
table = np.ones([h,w])
for i in range(h):
 
    tuzuki = False
    count = 0
    for j in range(w):
        if s[i][j] == '.':
 
            if tuzuki:
                count += 1
            else:
                start = j
                count = 1
                tuzuki = True
            if j == w-1:
              table[i][start:w] = count

        else:
            if tuzuki:
                tuzuki = False
                table[i][start:j] = count
for j in range(w):
    tuzuki = False
    count = 0
    for i in range(h):
        if s[i][j] == '.':
            if tuzuki:
                count += 1
            else:
                start = i
                count = 1
                tuzuki = True
            if i == h-1:
              table[start:h, j] += count - 1
        else:
            if tuzuki:
              table[start:i, j] += count - 1
              tuzuki = False
print(int(table.max()))

### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
table = np.array([list(input())for _ in range(h)]) == '.'

d = np.zeros((h, w), dtype = int)
u = np.zeros((h, w), dtype = int)
r = np.zeros((h, w), dtype = int)
l = np.zeros((h, w), dtype = int)

for i in range(h):
    d[i] = (d[i-1]+1) * table[i]
    u[-i-1] = (u[-i]+1) * table[-i-1]
for i in range(w):
    r[:, i] = (r[:, i-1]+1) * table[:, i]
    l[:, -i-1] = (l[:, -i]+1) * table[:, -i-1]
print(np.max(d+u+r+l)-3)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    par = [-1] * n
    g = [[0] * n for _ in range(n)]

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

    for i1 in range(n):
        member = members(i1)
        for m in member:
            g[i1][m] ^= 1

    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        g[c][d] = 0
        g[d][c] = 0

    for i in range(n):
        print(sum(g[i]) - 1, end=' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

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

l, r = map(int, input().split())
ans = 9999
for i in range(l, r):
    for j in range(l + 1, min(r+1, (l + 4038))):
        if (i * j) % 2019 < ans:
            ans = (i * j) % 2019
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
ans = 9999
r = min(r, l+4038)
for i in range(l, r):
    for j in range(i + 1, r+1):
        if (i * j) % 2019 < ans:
            ans = (i * j) % 2019
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
num=[]
def ap(num1):
    num.append(num1)
for i in range(n):
    ap((p[i]+1)/2)
ans=[]
if k==1:
    print(max(num))
else:
    def ap2(num2):
        ans.append(num2)
    for i in range(n-k+1):
        ap2(sum(num[i:i+k]))
    print(max(ans))


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
num=[sum(p[0:k])]
def ap(num1):
    num.append(num1)
for i in range(n-k):
    ap(num[i]-p[i]+p[k+i])
print((max(num)+k)/2)
### BUGGY CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if max(nex)>k:
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        
        num = i
        p = 0
        nex = [0 for _ in range(checker+1)]
        for m in range(h):
            nex[p] += s[m][0]
            p += num%2
            num = num >> 1
        if max(nex) > k:
            x = float('inf')
            continue

        if all(nex[m]+c[m] <= k for m in range(checker+1)):
            c = [c[I]+nex[I] for I in range(checker+1)]
        else:
            x += 1

        for j in range(1, w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1
            if max(nex) > k:
                x = float('inf')
                break            
            
            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
S = S.translate(str.maketrans({"T":"0","G":"0"}))
for q in range(Q):
  l, r = map(int, input().split())
  si = S[l-1:r].replace("AC","11")
  si = si.translate(str.maketrans({"A":"0","C":"0"}))
  print(int(sum(map(int,list(si)))/2))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
c = [0]
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    c.append(c[-1]+1)
  else:
    c.append(c[-1])
    
for i in range(q):
  l, r = map(int, input().split())
  print(c[r-1] - c[l-1])
### BUGGY CODE ###

import bisect
import sys
readline = sys.stdin.readline
N = int(readline())
ls = list(map(int, readline().split()))
ls.sort()

ans = 0
for i in range(N-2):
  a = ls[i]
  for j in range(i+1, N-1):
    b = ls[j]
    pos = bisect.bisect_left(ls, a+b, lo=j)
    ans += pos - j - 1
print(ans)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
N = int(input())
ls = list(map(int, input().split()))
ls.sort()

ans = 0
for i in range(N-2):
  a = ls[i]
  for j in range(i+1, N-1):
    b = ls[j]
    pos = bisect.bisect_left(ls, a+b)
    ans += pos - j - 1
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
D = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = tuple([int(x) for x in input().strip().split()])
    AB[n] = (a, b)
    D[a-1][b-1] = '#'
    D[b-1][a-1] = '#'

maxc = 0

for i, d in enumerate(D):
    c = d.count('#')
    if c > maxc:
        maxc = c
        maxi = i

q = deque([])
c = 1
for i in range(N):
    if D[maxi][i] == '#':
        D[maxi][i] = c
        D[i][maxi] = c
        c += 1
        q.append(i)

while q:
    ind = q.popleft()
    c = 1
    for i in range(N):
        while c in D[ind]:
            c += 1
        if D[ind][i] == '#':
            D[ind][i] = c
            D[i][ind] = c
            c += 1
            if i not in q:
                q.append(i)

print(maxc)
for a, b in AB:
    print(D[a-1][b-1])


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])