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

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=[]
res=[0]
def calc(k):
    return 1/2*k*(k-1)
for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aflag,bflag=False,False
    for x in cango:
        if aflag==True and bflag==True:break
        if a in x:
            aset=x
            aflag=True
        if b in x:
            bset=x
            bflag=True
    if aset==bset:
        res.append(res[-1])
        continue
    if aset in cango:cango.remove(aset)
    if bset in cango:cango.remove(bset)
    cango.append(aset|bset)
    res.append(res[-1]-calc(len(aset))-calc(len(bset))+calc(len(aset)+len(bset)))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

### FIXED CODE ###

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = [{} for _ in range((10**5+1)*2)]
ans = 0
for _ in range(n):
    s,t,c = map(int, input().split())
    s,t = s*2-1, t*2
    for i in range(s,t+1):
        if c not in channels[i]:
            channels[i][c] = 1
        ans = max(ans, len(channels[i]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = {i:[] for i in range(1,c+1)}
table = [0 for _ in range(200004)]
for _ in range(n):
    s,t,c = map(int, input().split())
    channels[c].append([s,t])

for ch, time in channels.items():
    sub = [0 for _ in range(200004)]
    for s,t in time:
        if sub[s*2]:
            sub[s*2] = 0
        else:
            sub[s*2-1] = 1
        if sub[t*2-1]:
            sub[t*2-1] = 0
        else:
            sub[t*2] = -1
    for i in range(1,200002):
        sub[i] += sub[i-1]
        table[i] += max(0, sub[i])
ans = 0
for i in range(1,200002):
    ans = max(ans, table[i])
print(ans)
### BUGGY CODE ###

from collections import Counter
import math

n = int(input())
a = list(map(int, input().split()))
nn = len(a) - 1
ctr = Counter(a)

for aa in a:
    x = 0
    for k, v in ctr.items():
        if k == aa:
            v -= 1
        if v >= 2:
            c = math.factorial(v) // (2 * math.factorial(v - 2))
            x += c
    print(x)


### FIXED CODE ###

from collections import Counter
import math

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

ctr = Counter(aa)

cmb2 = [0] * 200001
for n in range(2, 200001):
    r = 2
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

x = 0
for k, v in ctr.items():
    x += cmb2[v]

for a in aa:
    k = ctr[a] - 1
    print(x - k)
### BUGGY CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "#":
            continue
        if visited[next_pos[0]][next_pos[1]] < visited[pos[0]][pos[1]] + 1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == h*w:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

### FIXED CODE ###

import collections

h, w = map(int, input().split())

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[-1 for _ in range(h)] for _ in range(w)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    if pos == goal:
        break
    
    for x,y in zip(dx, dy):
        next_pos = [pos[0]+x, pos[1]+y]
        
        if next_pos[0]<0 or (w-1)<next_pos[0] or next_pos[1]<0 or (h-1)<next_pos[1]:
            continue
        if ss[next_pos[1]][next_pos[0]] == "#":
            continue
        if visited[next_pos[0]][next_pos[1]] != -1:
            continue
        stack.appendleft(next_pos)
        visited[next_pos[0]][next_pos[1]] = visited[pos[0]][pos[1]] + 1

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)
### BUGGY CODE ###

N = int(input())
gacha_list = []

for i in range(N):
  input_line = input()
  if input_line in gacha_list:
    None
  else:
    gacha_list.append(input_line)
  
print(len(gacha_list))

### FIXED CODE ###

N = int(input())
gacha_list = set()

for i in range(N):
  input_line = input()
  if input_line not in gacha_list:
    gacha_list.add(input_line)
    
print(len(gacha_list))
### BUGGY CODE ###

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

a = [int(input()) for i in range(q)]
c = [0]*n
for i in a:
    c[i-1] += 1

for i in range(n) :
    if sum(c)-c[i] >= k :
        print("No")
    else :
        print("Yes")


### FIXED CODE ###

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

c = [k-q]*(n+1)

for i in range(q):
    c[int(input())] += 1

for i in range(1,n+1) :
    if c[i]>0 :
        print("Yes")
    else :
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""077-c"""

import sys
import pprint
import re

import itertools
pp = pprint.PrettyPrinter(indent=2)

def main():
    """Main function."""
    N = int(input())

    As = sorted(list(map(int, input().split(' '))))
    Bs = sorted(list(map(int, input().split(' '))))
    Cs = sorted(list(map(int, input().split(' '))))

    Bs_count = [len(list(filter(lambda c : b < c, Cs))) for b in Bs]
    As_count = [len(list(filter(lambda b : a < b, Bs))) for a in As]

    count = 0
    for c in As_count:
        if -1 * c == 0:
            break
        for c_ in Bs_count[-1 * c:]:
            count += c_

    print(count)


if __name__ == '__main__':
    sys.exit(main())

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""077-c"""

import sys
import pprint
import re
import itertools

import bisect

pp = pprint.PrettyPrinter(indent=2)

def main():
    """Main function."""
    N = int(input())

    As = sorted(list(map(int, input().split(' '))))
    Bs = map(int, input().split(' '))
    Cs = sorted(list(map(int, input().split(' '))))

    count = 0
    for b in Bs:
        i = bisect.bisect_left(As, b)
        k = N - bisect.bisect_right(Cs, b)
        count += i * k

    print(count)

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

import sys

N = int(input().rstrip('\n'))
S = [str(input().rstrip('\n')) for _ in range(N)]

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    elif now < 0:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1], reverse=True)
minus_stock = sorted(minus_stock, key = lambda x:x[1], reverse=True)

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]
last = now
now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
if last == now:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

import sys
N = int(input().rstrip('\n'))
S = [str(input().rstrip('\n')) for _ in range(N)]

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    elif now < 0:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1], reverse=True)
minus_stock = sorted(minus_stock, key = lambda x:x[1], reverse=True)

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]
last = now
now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
if last == now:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

query = [input().split() for i in range(q)]

a = s

flag = True

for i in range(len(query)):
    if query[i][0] == "1":
        flag = not(flag)
    else:
        if (query[i][1] == "1" and flag) or (query[i][1] != "1" and not(flag)):
            a = query[i][2] + a
        else:
            a = a + query[i][2]

if not(flag):
    a = a[::-1]

print(a)

### FIXED CODE ###

from collections import deque

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

query = [input().split() for i in range(q)]

a = deque([s])

flag = True

for i in range(q):
    if query[i][0] == "1":
        flag = not(flag)
    else:
        if (query[i][1] == "1" and flag) or (query[i][1] != "1" and not(flag)):
            a.appendleft(query[i][2])
        else:
            a.append(query[i][2])

b = "".join(a)
if not(flag):
    b = b[::-1]

print(b)
### BUGGY CODE ###

#!/usr/bin/env python3
import re
s = input()

while(True):
    l = len(s)
    s = re.sub('(dream($|er$))|(erase($|r$))','',s)
    if len(s) == l:
        if len(s)==0:
            print('YES')
        else:
            print('NO')
        exit()


### FIXED CODE ###

#!/usr/bin/env python3
import re
s = input()


while True:
    # s = re.sub('dream$|dreamer$|erase$|eraser$','',s)

    l = len(s)
    if s.rfind('dream') == l-5:
        s = s[:-5]
    elif s.rfind('dreamer') == l-7:
        s = s[:-7]
    elif s.rfind('erase') == l-5:
        s = s[:-5]
    elif s.rfind('eraser') == l-6:
        s = s[:-6]
    else:
        break
        
if len(s)==0:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

[print(i) for i in range(A, B+1) if abs(i-A) < K or abs(B-i) < K]


### FIXED CODE ###

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

R = [A, B]

for k in range(1, K):
    if A + k >= B:
        break
    R.append(A + k)

for k in range(1, K):
    if B - k <= A:
        break
    R.append(B - k)


R = list(set(R))
R.sort()

for r in R:
    print(r)
### BUGGY CODE ###

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

def calcCommonDivisor(a, b):
    cdiv=[]
    for i in range(1, max(a,b)+1):
        if a%i==0 and b%i==0:
            cdiv.append(i)

    return cdiv

def isPrime(a):
    if a == 1:
        return True

    d=0
    for i in range(1, a+1):
        if a%i==0:
            d+=1

    return d == 2

cdiv=calcCommonDivisor(a,b)
if len(cdiv) == 1:
    print(1)
    quit()

ans=0
for i in cdiv:
    if i in (1,2,3,5,7,9):
        ans+=1

print(ans)


### FIXED CODE ###

import fractions
a, b = map(int, input().split())

def factorize(n: int) -> int:
    b = 2
    ret = []
    while b*b <= n:
        while n%b == 0:
            n //= b
            ret.append(b)
        b = b + 1

    if n > 1:
        ret.append(n)

    return list(set(ret))

g = fractions.gcd(a, b)
print(len(factorize(g))+1)
### BUGGY CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
for i in range(k+1):
    #print(dum,ans_list,i,k)
    if ok and ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False

    if k == 0:
        print(int(dum))
        break
    if ok:
        ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1



### FIXED CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
check_list = n*[0]
check_list[0] = 1
for i in range(k+1):
    if ok and check_list[dum-1] == 1:
        #print(dum,111)
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False
    else:
        check_list[dum-1] = 1

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1
### BUGGY CODE ###

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = 1
    for num in A:
        ans *= num
    if ans > 10**18:
        ans = -1
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    ans = 1
    for i in range(N):
        if ans == -1 and A[i] != 0:
            continue
        ans *= A[i]
        if ans > 10**18:
            ans = -1
    print(ans)

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

n,k=map(int,input().split())
p = [int(i) for i in input().split()]
ans=[]
for i in range(len(p)-k+1):
    x=0
    for j in range(k):
        x+=(p[i+j]+1)/2
    ans.append(x)
#print(ans)
print(max(ans))

### FIXED CODE ###

n,k=map(int,input().split())
p = [int(i) for i in input().split()]

for i in range(len(p)):
    p[i]=(p[i]+1)/2
tmp=sum(p[0:k])
x=sum(p[0:k])
for i in range(k,len(p)):
    x=x-p[i-k]+p[i]
    if x>tmp:
        tmp=x
print(tmp)
### BUGGY CODE ###

S = list(input())
ans = 0
# print(S)
cl1 = []
cl2 = []
while True:
	for i in range(len(S)-1):
		if S[i] == 'B' and S[i+1] == 'W' and i not in cl1:
			S[i] = 'W'
			S[i+1] = 'B'
			ans += 1
			cl1.append(i)
		elif S[i] == 'W' and S[i+1] == 'B' and i not in cl1:
			S[i] = 'B'
			S[i+1] = 'W'
			ans += 1
			cl1.append(i)
		else:
			pass
		# print(S)
	if cl1 == cl2:
		break
	else:
		cl1, cl2 = cl2, cl1
		cl1 = []
print(ans)


### FIXED CODE ###

S = list(input())
move = 0
ans = 0
for i in range(len(S)):
	if S[i] == 'B':
		move += 1
	else:
		ans += move
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
a =list(map(int,input().split()))
b = sorted(a,reverse=True)


for i in range(m):
    max_b = b[0]
    b.pop(0)
    b.append(max_b//2)
    b = sorted(b,reverse = True)
print(sum(b))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

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

# solve
ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]

# output
print(sum(ans))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())

ans = 0

d = ([0, 1], [0, -1], [1, 0], [-1, 0])


def bfs(x, y):
    m = []
    for _ in range(H):
        m.append([-1] * W)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if maximus < v+1:
                    maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

N=int(input())
ps=[]
#for i in range(N):
#tmp=input()
ps = [list(map(int, input().split())) for _ in range(N)]

    

tg=[]
tp=[]

ag=[]
ap=[]
for p in ps:
  tg.append((p[1]+p[0]))
  tp.append(p[0])
  ag.append((p[0]+p[1]))
  ap.append(p[1])
    
import numpy as np
def is_even(num):
  if num % 2 == 0:
    return True
  else:
    return False
    
T=0
A=0

for i in range(N):
  if is_even(i):
    if tg[np.argmax(tg)]!=0:
      tmpIndex=np.argmax(tg)
      T+=tp.pop(tmpIndex)
      tg.pop(tmpIndex)
      ag.pop(tmpIndex)
      ap.pop(tmpIndex)
    else:
      tmpIndex=np.argmax(tp)
      T+=tp.pop(tmpIndex)
      tg.pop(tmpIndex)
      ag.pop(tmpIndex)
      ap.pop(tmpIndex)
  else:
    if ag[np.argmax(ag)]!=0:
      tmpIndex=np.argmax(ag)
      A+=ap.pop(tmpIndex)
      ag.pop(tmpIndex)
      tg.pop(tmpIndex)
      tp.pop(tmpIndex)
    else:
      tmpIndex=np.argmax(ap)
      A+=ap.pop(tmpIndex)
      ag.pop(tmpIndex)
      tg.pop(tmpIndex)
      tp.pop(tmpIndex)
print(T-A)


### FIXED CODE ###

N=int(input())
ps=[]
tp=[]
ap=[]
for i in range(N):
  p=input().split()
  ps.append([int(p[0])+int(p[1]),i])
  tp.append(int(p[0]))
  ap.append(int(p[1]))
    
def is_even(num):
  if num % 2 == 0:
    return True
  else:
    return False

T=0
A=0
calc=sorted(ps,reverse=True)
#print(calc)
i=0
for p,j in calc:
  if is_even(i):
    T+=tp[j]
  else:
    A+=ap[j]
  i+=1
print(T-A)
### BUGGY CODE ###

knots = []
n, l = map(int, raw_input().split())
a = map(int, raw_input().split())
index = range(0,n+1)
# print a
while len(knots) < n-1:
    i = 0
    untied = False
    while i < (len(a)-1):
        if a[i] + a[i+1] >= l:
            untied = True
            a[i] += a.pop(i+1)
            # print a
            # print "i", index
            knots.append(index[i+1])
            del index[i+1]
        i += 1
    if untied == False:
        print "Impossible"
        exit()
print "Possible"
for k in reversed(knots):
    print k


### FIXED CODE ###

n, l = map(int, raw_input().split())
a = map(int, raw_input().split())
# print a
i = 0
untied  = False
while i < (len(a)-1):
    if a[i] + a[i+1] >= l:
        # print i, a[i]
        untied = True
        break
    i += 1
if untied == False:
    print "Impossible"
    exit()
print "Possible"
for k in xrange(n-1, i+1, -1):
    print k
for k in xrange(1, i+2):
    print k
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=a[0]
dp=[]
dp.append(a[0])
dp.append(a[1])
for i in range(2,n):
  check=0
  for j in range(i-1):
    check=max(check,min(dp[j],dp[j+1]))
  dp.insert(dp.index(check),a[i])
  ans=ans+check
print(ans)

  



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
if n%2==0:
  print(a[0]+sum(a[1:int(n/2)])*2)
else:
  print(a[0]+sum(a[1:int((n-1)/2)])*2+a[int((n+1)/2-1)])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    g = []
    ans = 0
    for j in range(60):
        d = 0
        for i in range(n):
            d += a[i]&1
            a[i] >>= 1
        g.append(d)
    for i in range(60):
        ans += g[i]*(n-g[i])*(pow(2,i,1000000007))
        ans = ans % (1000000007)
    print(ans%(1000000007))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1) # 自分がnp.sumを利用したがどうしても正解になれなかった。なぜ？
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

from collections import deque
from heapq import heappop
import sys
input = sys.stdin.readline
N = int(input())
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

d = max(D)
for M in [d, d+1]:
    flag = False
    Q = deque([argmax])
    check = [0]*N
    color = [2**M-1 for _ in range(N)]
    C = dict()
    while Q:
        v = Q.popleft()
        check[v] = 1
        for u in V[v]:
            if check[u]:
                continue
            else:
                Q.append(u)
            usable_colors = color[v] & color[u]
            if usable_colors == 0:
                flag = True
                break
            else:
                cnt = 0
                while usable_colors % 2 == 0:
                    usable_colors //= 2
                    cnt += 1

            C[tuple(sorted([u, v]))] = cnt
            color[v] -= 2**cnt
            color[u] -= 2**cnt
        if flag:
            break
    
    if M == d and flag == False:
        break

ans = [0]*(N-1)  
for i in range(N-1):
    ans[i] = C[T[i]]+1

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

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

K = D[argmax]
Q = deque([])
C = dict()
for i, v in enumerate(V[argmax]):
    C[tuple(sorted([argmax, v]))] = i+1
    Q.append((v, i+1))

check = [0]*N
check[argmax] = 1
while Q:
    v, color = Q.popleft()
    check[v] = 1
    i = 0
    for u in V[v]:
        if check[u]:
            continue
        i += 1
        if i == color:
            i += 1
        C[tuple(sorted([u, v]))] = i
        Q.append((u, i))

print(K)
for i in range(N-1):
    print(C[T[i]])
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n - 1) * n // 2
print(int(ans))