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

import sys
sys.setrecursionlimit(2000)
n, m = map(int, input().split())
bridge = list(map(int, sys.stdin.read().split()))
total = n*(n-1)//2
ans =[total]
u = [i for i in range(n+1)]
size = [1 for i in range(n+1)]
rank = [1 for i in range(n+1)]
def check(x, y):
    return find(x) != find(y)

def find(x):
    if x == u[x]:
        return x
    else:
        return u[x]

for x , y in zip(bridge[-2::-2],bridge[::-2]):
    if check(x, y):
        X = find(x)
        Y = find(y)
        total -= size[X] * size[Y]
        ans += [total]
        if rank[X] == rank[Y]:
            X, Y = sorted([X,Y])
            u = [Y if i == X else i for i in u]
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
        else:
            if rank[X] > rank[Y]:
                X, Y = sorted([X,Y])
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
            u = [Y if i == u[X] else i for i in u]
        size[Y] += size[X]

    else:
        ans += [total]

print(*ans[-2::-1], sep="\n")

### FIXED CODE ###

import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

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

nc = dict()
for row in range(h):
    for col in range(w):
        v = A[row][col]
        nc[v] = (row, col)

q = int(input())
lrs = [list(map(int, input().split())) for _ in range(q)]

for lr in lrs:
    l, r = lr
    ans = 0
    while l != r:
        i, j = nc[l]
        x, y = nc[l + d]
        ans += abs(x - i) + abs(y - j)
        l += d
    print(ans)


### FIXED CODE ###

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

nc = dict()
for row in range(h):
    for col in range(w):
        v = A[row][col]
        nc[v] = (row, col)

q = int(input())
lrs = [list(map(int, input().split())) for _ in range(q)]

c_sums = [[0] for _ in range(d)]
for r in range(d):
    k = 0
    if r == 0: k = 1
    while r + (k + 1) * d <= h * w:
        i, j = nc[r + k * d]
        x, y = nc[r + (k + 1) * d]
        t = c_sums[r][-1] + abs(x - i) + abs(y - j)
        c_sums[r].append(t)
        k += 1

for lr in lrs:
    l, r = lr
    ld, rest = divmod(l, d)
    rd = r // d
    if rest == 0:
        ld -=1
        rd -=1
    print(c_sums[rest][rd] - c_sums[rest][ld])
### BUGGY CODE ###

import itertools
given_n = int(input())
given_A = list(map(int,input().split()))
given_q = int(input())
given_m = list(map(int,input().split()))

for mi in given_m:
    partial_A = list(filter(lambda ai:ai<=mi,given_A))
    check = False
    for num in range(1,len(partial_A)+1):
        combinationPartialA = list(itertools.combinations(partial_A,num))
        for tmp_cpa in combinationPartialA:
            if sum(tmp_cpa) == mi:
                check = True
                break
        if check:
            break
    if check:
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = []
for i in range(n):
    P += [[int(x) for x in input().split()]]
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

### FIXED CODE ###

def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            try :
                if isCLKWISE(phU) : break
                else : del phU[-2]
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            try :
                if isCLKWISE(phL) : break
                else : del phL[-2]
            except IndexError : break
    ph = phU + phL[1:-1]
    return ph
  
P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])
### BUGGY CODE ###

import math

n, m = map(int, input().split(" "))
aL = list(map(int, input().split(" ")))

for i in range(m):
    aL.sort(reverse=True)
    aL[0] //= 2

print(sum(aL))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
aL = list(map(lambda x: int(x) * (-1), input().split(" ")))

heapq.heapify(aL)

for i in range(m):
    a = heapq.heappop(aL)
    a = int(a / 2)
    heapq.heappush(aL, a)

print(int(sum(aL) * -1))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
    b[i],c[i]=map(int,input().split())
for i in range(q):
    t=0
    for j in range(n):
        if a[j]==b[i]:
            a[j]=c[i]
        t+=a[j]
    print(t)
    

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
for i in range(q):
    b[i],c[i]=map(int,input().split())
N=[0]*(10**5)
s=0
for i in range(n):
    N[a[i]-1]+=1
    s+=a[i]
for i in range(q):
    s+=(c[i]-b[i])*N[b[i]-1]
    N[c[i]-1]+=N[b[i]-1]
    N[b[i]-1]=0
    print(s)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
connect = {}
dist = {}
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in connect.keys(): connect[a] = [b]
    else: connect[a].append(b)
    if not b in connect.keys(): connect[b] = [a]
    else: connect[b].append(a)
    
    dist[tuple(sorted([a, b]))] = c

ans = 0
for s in range(1, n):
    for t in range(s+1, n+1):
        if not (s, t) in dist.keys():
            continue
        
        dists = [1000]*(n+1)
        dists[s] = 0
        stack = [(s, sc) for sc in connect[s]]
        while len(stack) > 0:
            s0, s1 = stack[0]
            stack = stack[1:]
            if dists[s0]+dist[tuple(sorted((s0, s1)))] >= dists[s1]:
                continue
            else:
                dists[s1] = dists[s0]+dist[tuple(sorted((s0, s1)))]
                for s2 in connect[s1]:
                    stack.append((s1, s2))
        # print(dists)
        if dists[t] < dist[(s, t)]:
            ans += 1

print(ans)

### FIXED CODE ###

n, m = list(map(int, input().split()))
dist_given = {}
dist = [[1000]*(n+1) for _ in range(n+1)]
for i in range(1, n+1): dist[i][i] = 0
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dist[a][b] = c
    dist[b][a] = c
    dist_given[tuple(sorted([a, b]))] = c

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# print(dist)
ans = 0
for i in range(1, n):
    for j in range(i+1, n+1):
        if (i, j) in dist_given.keys() and dist[i][j] < dist_given[(i, j)]:
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = max(ans, abs(xy[i][0]-xy[j][0])+abs(xy[i][1]-xy[j][1]))
print(ans)

### FIXED CODE ###

n = int(input())
x = []
y = []
for i in range(n):
    l = list(map(int, input().split()))
    x.append(l[0]+l[1])
    y.append(l[0]-l[1])
print(max(max(x)-min(x), max(y)-min(y)))
### BUGGY CODE ###

import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def divisors(n):
    lower = []
    upper = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n // i)

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(2147483647)
input=lambda:sys.stdin.readline().rstrip()

def solve():
    n = int(input())
    edge = [[] for _ in range(n)]
    for v in range(1,n):
        u = int(input())-1
        edge[u].append(v)

    dp = [None]*n
    def dfs(s):
        if dp[s] != None:
            return dp[s]
        if edge[s] == []:
            dp[s] = 0
            return 0
        tmp = []
        for v in edge[s]:
            tmp.append(dfs(v))
        dp[s] = max(1+i+x for i,x in enumerate(sorted(tmp,reverse=1)))
        return dp[s]
    print(dfs(0))
    
if __name__=='__main__':
    solve()



### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
edge = [[] for _ in range(n)]
for v in range(1,n):
    u = I()-1
    edge[u].append(v)

dp = [None]*n
def dfs(s):
    if dp[s] != None:
        return dp[s]
    if edge[s] == []:
        dp[s] = 0
        return 0
    tmp = []
    for v in edge[s]:
        tmp.append(dfs(v))
    tmp.sort(reverse=True)
    m = 0
    for i,j in enumerate(tmp):
        m = max(m,(i+1)+j)
    dp[s] = m
    return m

dfs(0)
print(dp[0])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
b = set()
for i in range(n):
    if a[i] in b:
        continue
    else:
        if a.count(a[i]) < a[i]:
            ans += a.count(a[i])
        elif a.count(a[i]) > a[i]:
            ans += a.count(a[i])-a[i]
        b.add(a[i])
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
ans = 0 
c = Counter(list(map(int, input().split())))

for key, value in c.items():
    if key < value:
        ans += value-key
    elif key > value:
        ans += value
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    nums = []
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            continue

        if i == 0:
            nums.append(1)
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
        else:
            nums.append((nums[-1] % X + nums[-2] % X) % X)
    return nums[-1]


print(solve(n, hole_ids))


### FIXED CODE ###

n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,X,Y = map(int,input().split())

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

ans = [0]*(n-1)

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[Y-1][X-1] = 1
d[X-1][Y-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
d = warshall_floyd(d)

for i in range(n):
    for j in range(i+1,n):
        ans[d[i][j]-1] += 1

for i in range(n-1):
    print(ans[i])

### FIXED CODE ###

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

X -= 1
Y -= 1
ans = [0]*(N)

d = [[N]*N for i in range(N)]

for i in range(N):
    for j in range(i,N):
        if i<=X and Y<=j:
            d[i][j] = X-i+j-Y+1
        else:
            d[i][j] = min(abs(i-X)+abs(Y-j)+1,j-i)



for i in range(N):
    for j in range(i+1,N):
        ans[d[i][j]] += 1

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

N,K = map(int, input().split())
S = input()

kukan = []
cnt0 = 0
cnt1 = 0
for n in range(N):
        if S[n] == '0':
                cnt0 +=1
                if cnt1 > 0:
                        kukan.append(cnt1)
                cnt1 = 0
        if S[n] == '1':
                cnt1 +=1
                if cnt0 > 0:
                        kukan.append(cnt0)
                cnt0 = 0
kukan.append(max(cnt1,cnt0))

#print(kukan)
ans = []

if S[0] == '0':
        start = 1
else:
        start = 0
l = len(kukan)
if l == 1:
        print(N)
        exit()

for i in range(l-K):
        if (i+start)%2 == 0:
                #print(i+2*K)
                ans.append(sum(kukan[i:min(l+1,i+2*K+1)]))
        if (i+start)%2 == 1:
                #print(i+2*K-1)
                ans.append(sum(kukan[i:min(l+1,i+2*K)]))

print(max(ans))

### FIXED CODE ###

N,K = map(int, input().split())
S = input()

kukan = []
cnt0 = 0
cnt1 = 0
for n in range(N):
        if S[n] == '0':
                cnt0 +=1
                if cnt1 > 0:
                        kukan.append(cnt1)
                cnt1 = 0
        if S[n] == '1':
                cnt1 +=1
                if cnt0 > 0:
                        kukan.append(cnt0)
                cnt0 = 0

kukan.append(max(cnt1,cnt0))

#print(kukan)
ans = []

if S[0] == '0':
        start = 1
else:
        start = 0

l = len(kukan)

if l == 1:
        print(N)
        exit()

cnt = [0]*(l+1)
for i in range(1,l+1):
        cnt[i] = cnt[i-1] + kukan[i-1]

#print(cnt)
        


for i in range(1,l-K+1):
        if (i+start)%2 == 1:
                #print(i+2*K)
                ans.append(cnt[min(l,i+2*K)]-cnt[i-1])
        else:
                #print(i+2*K-1)
                ans.append(cnt[min(l,i+2*K-1)]-cnt[i-1])


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

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

INF = 10**10
#dp = [[INF]*K]*N
dp = [[INF] * (K+1) for i in range(N)]

for i in range(N):
    #j_max = min(K+1, k)
    #print(dp)
    H_i = H[i]
    for j in range(1, K+1):
        if i==0:
            dp[i][j] = 0
        elif j>i:
            dp[i][j] = dp[i][j-1]
        else:
            #print(i,j)
            #print(dp[i-j][K]+abs(H[i]-H[i-j]), dp[i][j-1])
            dp[i][j] = min(dp[i-j][K]+abs(H_i-H[i-j]), dp[i][j-1])
            #print(dp[i][j])

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

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
 
INF = 10**9
 
dp = [INF]*N
dp[0] = 0
 
for i in range(N):
    for j in range(1, min(i+1, K+1)):
        dp[i] = min(dp[i], dp[i-j]+abs(H[i]-H[i-j]))
 
print(dp[N-1])
### BUGGY CODE ###

from collections import deque
import sys

N = int(input())

b = list(map(int,input().split()))

q = deque([])

q.append([b,[]])

while len(q) > 0:

    now = q.pop()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        if (i+1) == nb[i]:

            nex = nb.copy()
            nec = nc.copy()
            nec.append(nex[i])
            del nex[i]

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])

print (-1)

            


### FIXED CODE ###

from collections import deque
import sys

N = int(input())

b = list(map(int,input().split()))

q = deque([])

q.append([b,[]])

dic = {}

while len(q) > 0:

    now = q.pop()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        i = len(nb) - i - 1

        if (i+1) == nb[i]:

            nex = []
            nec = []
            for j in range(len(nb)):
                if j != i:
                    nex.append(nb[j])
            for j in range(len(nc)):
                nec.append(nc[j])
            
            nec.append(nb[i])
            

            s = " ".join(map(str,nex))
            if s in dic:
                continue
            dic[s] = 1

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])
            break

print (-1)
### BUGGY CODE ###

from sys import stdin

s=list(input())
q=int(input())

for i in range(1,q+1):
    q_i=stdin.readline().rstrip().split()
    if q_i==["1"]:
        s=s[::-1]
    else:
        if q_i[1]=="1":
            s=list(q_i[2])+s
        else:
            s=s+list(q_i[2])

s="".join(s)
print(s)

### FIXED CODE ###

from collections import deque

s=list(input())
s=deque(s)
q=int(input())

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)
### BUGGY CODE ###

from collections import deque


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

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

inf = 10 ** 10
cost = [[inf] * w for _ in range(h)]

walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if [i, j] not in [[0, 0]] + walk]

q = deque()
cost[ch][cw] = 0
q.append([ch, cw, 0])

while q:
    x, y, c = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c:
            cost[nx][ny] = c
            q.appendleft([nx, ny, c])

    for dx, dy in warp:
        nx = x + dx
        ny = y + dy

        if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] == '.' and cost[nx][ny] > c + 1:
            cost[nx][ny] = c + 1
            q.append([nx, ny, c + 1])

ans = cost[dh][dw] if cost[dh][dw] != inf else -1
print(ans)
### BUGGY CODE ###

from collections import deque

def dfs(T,colors,visit,q):
    if len(q)==0:
        return colors
    s = q.popleft()
    d = 0
    for i in T[s]:
        if visit[i]<0:
            d += 1
            d += (d==visit[s])
            colors[s][i] = d
            visit[i] = d
            q.append(i)
    return dfs(T,colors,visit,q)

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]

colors = [[-1 for _ in range(n)] for _ in range(n)]
visit = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]

for i in range(n-1):
    a, b = ab[i]
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

visit[0] = 0
colors = dfs(tree,colors,visit,deque([0]))
result = []
for a, b in ab:
    result.append(colors[a-1][b-1])
print(max(result))
for i in range(n-1):
    print(result[i])

### FIXED CODE ###

from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()