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

n = int(input())

buttons = []

for i in range(n):
    buttons.append(int(input()))

index = 1
cnt = 0
history = []

while index != 2:
    if index in history:
        cnt = -1
        break

    history.append(index)        
    index = buttons[index-1]
    cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())

buttons = []

for i in range(n):
    buttons.append(int(input()))

index = 1
cnt = 0

for i in range(n):
    index = buttons[index-1]
    cnt += 1

    if index == 2:
        print(cnt)
        exit()

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

from itertools import combinations_with_replacement


n = int(input())

for i in range(1, n+1):
    count = 0
    n_list = list(combinations_with_replacement([j for j in range(1, i//6+2)], 3))
    for x in n_list:

        if x[0]**2 + x[1]**2 + x[2]**2 + x[0]*x[1] + x[1]*x[2] + x[2]*x[0] == i:
            if x.count(x[0]) == 2 or (x.count(x[0]) == 1 and x.count(x[1]) == 2):
                count += 3
            elif x.count(x[0]) == 1 and x.count(x[1]) == 1 and x.count(x[2]) == 1:
                count += 6
            else:
                count += 1
    print(count)


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(n+1)]
m = int(n**0.5) + 1
for x in range(1, m):
    for y in range(1, m):
        for z in range(1, m):
            t = x*x + y*y + z*z + x*y + y*z + z*x
            if t < n + 1:
                ans[t] += 1

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

N,M = (int(i) for i in input().split())  
A = [int(i) for i in input().split()]

a = A[0]
sum_A = []
for g in range(1,N+1):
	sum_A.append(a)
	if g<=N-1:
		a +=  A[g]

l=0
r=0
ans=0
while True:
	if r==l:
		if sum_A[l]%M==0:
			ans+=1
			r+=1
		else:
			r+=1
	else:
		if (sum_A[r]-sum_A[l])%M==0:
			ans+=1
			r+=1
		else:
			r+=1

	if r==N:
		l += 1
		r = l
	if l == N:
		break

print(ans)

### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate

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

acc=list(accumulate(A))

d=defaultdict(int)

ans=0
for i in range(N):
    if acc[i]%M==0:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]
    else:
        d[acc[i]%M]+=1
        ans+=d[acc[i]%M]-1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

from itertools import accumulate

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD
    return value

def solve(N: int, K: int, A: "List[int]"):
    A.sort()
    n = N-1
    r = K-1
    # nCkTable[i] = iCr
    nCkTable = [0]*(n+1)

    start = 1
    for _ in range(r):
        start *= n
        start %= MOD
        n -= 1

    bunbo = mod_factorial(r)
    bunbo_gyakugen = pow(bunbo,MOD-2,MOD)

    n = N-1
    for i in range(n, r-1, -1):
        nCkTable[i] = start*bunbo_gyakugen%MOD
        start*=pow(i,MOD-2,MOD)
        start*=i-r

    answer = 0
    for i in range(N):
        answer += A[i]*(nCkTable[i]-nCkTable[N-1-i])
        answer%=MOD
    print(answer%MOD)
    return


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
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

from itertools import accumulate

def mod_factorial(n):
    value = 1
    for i in range(n,0,-1):
        value*=i
        value%=MOD
    return value

def solve(N: int, K: int, A: "List[int]"):
    A.sort()
    n = N-1
    r = K-1
    # nCkTable[i] = iCr
    nCkTable = [0]*(n+1)

    start = 1
    for _ in range(r):
        start *= n
        start %= MOD
        n -= 1

    bunbo = mod_factorial(r)
    bunbo_gyakugen = pow(bunbo,MOD-2,MOD)

    n = N-1
    for i in range(n, r-1, -1):
        nCkTable[i] = start*bunbo_gyakugen%MOD
        start*=pow(i,MOD-2,MOD)
        start*=i-r
        start%=MOD

    answer = 0
    for i in range(N):
        answer += A[i]*(nCkTable[i]-nCkTable[N-1-i])
        answer%=MOD
    print(answer%MOD)
    return


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
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

h = int(input())

cnt = 1
for i in range(10**12):
  h = h//2
  n = 2**(i+1)
  cnt += n
  if h == 1:
    print(cnt)
    exit()

### FIXED CODE ###

h = int(input())

for i in range(10**12):
  if 2**i <= h < 2**(i+1):
    ans = 2**(i+1)-1
    print(ans)
    exit()
### BUGGY CODE ###

N=int(input())
S=input()
ans=9**9
for i in range(N):
    e=S[:i].count("W")
    w=S[i:].count("E")
    ans=min(ans,e+w)
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
e=0
ans=w=S.count("E")
for i in S:
    if i=="E":w-=1
    else: e+=1
    ans=min(ans,e+w)
print(ans)
### BUGGY CODE ###

#from operator import mul
from math import factorial
#from functools import reduce
X, Y = map(int, input().split())
MOD = (10 ** 9) + 7
if ((2 * X) - Y) % 3 != 0:
    print(0)
    exit()
q = ((2 * X) - Y) // 3
p = X - (2 * q)
if q < 0 or p < 0:
    print(0)
    exit()
r = max(p, q)
s = min(p, q)

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p

print(comb(r+s, r, MOD) % MOD)


### FIXED CODE ###

from operator import mul
from math import factorial
from functools import reduce

def modpow(a, n, mod): # a^n mod
    result = 1
    while n > 0:
        if n & 1: result = result * a % mod
        a = a * a % mod
        n >>= 1
    return result

X, Y = map(int, input().split())
MOD = (10 ** 9) + 7
if ((2 * X) - Y) % 3 != 0:
    print(0)
    exit()
q = ((2 * X) - Y) // 3
p = X - (2 * q)
if q < 0 or p < 0:
    print(0)
    exit()
r = max(p, q)
s = min(p, q)

over = 1
for i in range(2,r+s+1):
    over = (over * i) % MOD
under = 0
e = 1
f = 1
for i in range(2,s+1):
    e = (e * i) % MOD
for i in range(2,r+1):
    f = (f * i) % MOD
under = e * f

result = (over * modpow(under, MOD-2, MOD) % MOD)
print(result)
### BUGGY CODE ###

from bisect import bisect_right

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

B.sort()
C.sort()
ans = 0
for a in A:
    b_index = bisect_right(B, a)
    if b_index == len(B):
        continue
    b_cnt = len(B)-b_index

    for b in B[b_index:]:
        c_index = bisect_right(C, b)
        if c_index == len(C):
            continue
        c_cnt = len(C)-c_index

        ans += c_cnt
print(ans)


### FIXED CODE ###

import bisect

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

A.sort()
C.sort()
ans = 0
for i in range(N):
    a_cnt = bisect.bisect_left(A, B[i])
    c_cnt = N-bisect.bisect_right(C, B[i])
    ans += a_cnt*c_cnt
print(ans)
### BUGGY CODE ###

from itertools import combinations
mod = 10**9 + 7

n,k = map(int,input().split())
cnt = 0
for i in range(k, n + 2):
    a = set()
    for v in combinations(range(n+1), i):
        a.add(sum(v)%mod)
    cnt += len(a)
print(cnt)

### FIXED CODE ###

mod = 10**9 + 7

n,k = map(int,input().split())
tot = []
cur = 0
for i in range(n+1):
    cur += i
    tot.append(cur)

cnt = 0
for i in range(k, n+2):
    if n > i:
        max_ = tot[n] - tot[n - i]
    else:
        max_ = tot[n]
    min_ = tot[i - 1]
    cnt += max_ - min_ + 1
    cnt %= mod
print(cnt)
### BUGGY CODE ###

# coding: utf-8
class SqrtDecomposition:
    # RMQ用平方分割
    
    # n:要素数 init:配列初期値
    def __init__(self,n,init=0):
        self.data=[init for i in range(n)]
        #self.sqrt_n=int(n**0.5)+1
        self.sqrt_n=512
        self.bucket=[init for i in range(self.sqrt_n)]
    
    # x を y にする
    def update(self,x,y):
        self.data[x] = y
        tmp = self.data[x//self.sqrt_n * self.sqrt_n]
        for i in range(x//self.sqrt_n * self.sqrt_n, min(x//self.sqrt_n * self.sqrt_n + self.sqrt_n, n)):
            if tmp > self.data[i]:
                tmp = self.data[i]
        self.bucket[x//self.sqrt_n] = tmp
    
    # [x,y) の最小を求める
    def find(self,x,y):
        tmp = 10**19
        for i in range(self.sqrt_n):
            l,r=i*self.sqrt_n,(i+1)*self.sqrt_n
            if r <= x or y <= l :
                continue
            if x <= l and r <= y :
                tmp = min(tmp, self.bucket[i]);
            else:
                for j in range(max(x, l),min(y, r)):
                    tmp = min(tmp, self.data[j]);
        return tmp


n,q = map(int,input().split())
sd=SqrtDecomposition(n,2**31-1)
for i in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sd.update(x,y)
    else:
        print(sd.find(x,y+1))





### FIXED CODE ###

# coding: utf-8
class seg_tree:
    def __init__(self,n,minimum=True):
        self.inf = 2**31-1
        self.size = 2**(len(bin(n-1))-2)*2-1
        self.minimum = minimum
        if self.minimum:
            self.tree = [self.inf for i in range(self.size)]
        else:
            self.tree = [-1 for i in range(self.size)]
     
    def data(self):
        return self.tree[self.size//2:]
 
    def update(self,i,x):
        i=self.size//2+i
        self.tree[i]=x
        if self.minimum:
            while 1:
                i=(i-1)//2
                self.tree[i]=min(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
        else:
            while 1:
                i=(i-1)//2
                self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])
                if i<=0:
                    break
 
    def _mincheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return self.inf
        else:
            return min(self._mincheck(s,t,l,l+(r-l)//2,_p*2+1),self._mincheck(s,t,l+(r-l)//2+1,r,_p*2+2))
     
    def _maxcheck(self,s,t,l,r,_p=0):
        if s<=l and r<=t:
            return self.tree[_p]
        elif r<s or t<l:
            return -1
        else:
            return max(self._maxcheck(s,t,l,l+(r-l)//2,_p*2+1),self._maxcheck(s,t,l+(r-l)//2+1,r,_p*2+2))
 
    def find(self,s,t):
        if self.minimum:
            return self._mincheck(s,t,0,self.size//2)
        else:
            return self._maxcheck(s,t,0,self.size//2)
 
n,q=map(int,input().split())
st=seg_tree(n)
ans=[]
for i in range(q):
    c,x,y=map(int,input().split())
    if c:
        ans.append(st.find(x,y))
    else:
        st.update(x,y)
print(*ans,sep='\n')
### BUGGY CODE ###

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

ans = 0
mod = 1000000007

for i in range(60):
    one_count =0
    zero_count = 0
    for j in range(N):
        if A[j] >> i & 1 == 1:
            one_count+=1
        else:
            zero_count+=1
    ans += (one_count % mod) *(zero_count%mod) * (2**i) % mod
    ans = ans % mod
print(ans)

### FIXED CODE ###

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

ans = 0
mod = 1000000007

for i in range(60):
    one_count =0
    zero_count = 0
    for j in range(N):
        if A[j] >> i & 1 == 1:
            one_count+=1
        else:
            zero_count+=1
    ans += (one_count*zero_count)*(2**i)
    ans = ans%mod
print(ans)
### BUGGY CODE ###

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

ans = []
for i in range(K+1):
  temp = 0
  for j in A:
    temp += i^j
  ans.append(temp)

print(max(ans))


### FIXED CODE ###

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

np = [0]*40

for i in range(40):
  for j in A:
    if j&(1<<i):
      np[i] += 1

v = 0
for i in range(39,-1,-1):
  if v + (1<<i) > K:
    continue
  elif np[i] < N - np[i]:
    v += (1<<i)
    
ans = 0
for i in A:
  ans += (v^i)

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

from collections import deque

N,M=map(int,input().split())
A=deque([int(_) for _ in input().split()])

for m in range(M):
    a=max(A)
    A.remove(a)
    A.append(a//2)
print(sum(A))

### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=[-int(_) for _ in input().split()]
heapq.heapify(A)

for _ in range(M):
    a=heapq.heappop(A)
    heapq.heappush(A,-((-a)//2))

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

n,m = map(int, input().split())
p = [0]*m 
for i in range(m):
    p[i] = input().split()
AC=[]
WA=0
for i in range(m):
    if p[i][1]=="AC" and p[i][0] not in AC:
        AC.append(p[i][0])
    elif p[i][0] not in AC and [p[i][0],"AC"] in p:
        WA=WA+1
print(len(AC),WA)

### FIXED CODE ###

n,m = map(int, input().split())
p = [0]*m 

for i in range(m):
    p[i] = input().split()
AC=[[0,-1] for j in range(n)]
k=0
WA=0
for i in range(m):
    if p[i][1]=="AC" and AC[int(p[i][0])-1][0]==0 :
        AC[int(p[i][0])-1][0]=1
        AC[int(p[i][0])-1][1]=i
        k=k+1
for i in range(m):
    if p[i][1]=="WA" and AC[int(p[i][0])-1][0]==1 and AC[int(p[i][0])-1][1]>i:
        WA=WA+1

print(k,WA)
### BUGGY CODE ###

import math
N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
    x[i], y[i] = map(int, input().split())


def mindis(p, q):
    j = 0
    for i in range(N):
        if (x[i]-p)**2+(y[i]-q)**2<(x[j]-p)**2+(y[j]-q)**2:
            j = i
    return j


r = [0 for i in range(N)]
M = 19*10**5
for i in range(M):
    c = math.cos(2*math.pi*i/M)*10**10
    s = math.sin(2*math.pi*i/M)*10**10
    k = mindis(c, s)
    r[k] += 1
S = sum(r)
for i in range(N):
    print(r[i]/S)


### FIXED CODE ###

import math
N = int(input())
x = [0 for i in range(N)]
y = [0 for i in range(N)]
for i in range(N):
    x[i], y[i] = map(int, input().split())


def mindis(t):
    j = 0
    for i in range(N):
        if x[i]*math.cos(t)+y[i]*math.sin(t)<x[j]*math.cos(t)+y[j]*math.sin(t):
            j = i
    return j


r = [0 for i in range(N)]
M = 250000
for i in range(M):
    k = mindis(2*math.pi*i/M)
    r[k] += 1
S = sum(r)
for i in range(N):
    print(r[i]/S)
### BUGGY CODE ###

N=int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
ans = [0]*N
for i in range(len(A)):
    ans[A[i]-1] += 1
    #print(ans)
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import math
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
MOD = 10 ** 9 + 7
for a in A:
    b = a
    i = 0
    waru = 1
    while a > 0:
        if a % (waru * 2) != 0:
            a -= waru
            bit[i] += 1
        waru *= 2
        i += 1
answer = 0
for i, b in enumerate(bit):
    answer += (2 ** i) * (b * (N-b))
print(answer % MOD)

### FIXED CODE ###

import math
N = int(input())
A = list(map(int, input().split()))
bit = [0] * 60
MOD = 10 ** 9 + 7
for a in A:
    i = 0
    waru = 1
    while a > 0:
        if a % (waru * 2) != 0:
            a -= waru
            bit[i] += 1
        waru *= 2
        i += 1
answer = 0
for i, b in enumerate(bit):
    answer += (2 ** i) * (b * (N-b))
print(answer % MOD)
### BUGGY CODE ###

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


def mod10_9_7(num):
    return num % (10**9+7)


ans = 0
for i in range(N-1):
    for j in range(i, (N)):
        if i != j:
            ii = A[i]
            jj = A[j]
            if ii > 10 ** 5 or jj > 10 ** 5:
                ii = mod10_9_7(ii)
                jj = mod10_9_7(jj)
            ans += ii*jj

print(mod10_9_7(ans))

### FIXED CODE ###

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


def mod10_9_7(num):
    return num % (10**9+7)


seki = A[-1]

ans = 0
for i in range(N-2, -1, -1):
    ans += A[i] * seki
    seki += A[i]
print(mod10_9_7(ans))
### BUGGY CODE ###

K = int(input())

if(K % 2 == 0):
    print(-1)
else:
    seven_num = ''
    flg = True
    n = 0
    while(flg):
        seven_num += '7'
        n += 1
        if(int(seven_num) % K == 0):
            print(n)
            flg = False

### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for c in C:
    i = bisect_left(B, c)
    for b in B[:i]:
        j = bisect_left(A, b)
        ans += j
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())))
ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = N - bisect.bisect_right(C, b)
    ans += i * j
print(ans)
### BUGGY CODE ###

N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
P = [K for i in range(N)]
for i in range(Q):
        for j in range(N):
                if j==A[i]-1:
                        continue
                else:
                        P[j] -= 1
for i in range(N):
        if P[i] <= 0:
                print("No")
        else:
                print("Yes")

### FIXED CODE ###

N, K, Q = list(map(int, input().split()))
A = [int(input()) for i in range(Q)]
num = [0 for i in range(N)]
for i in range(Q):
        num[A[i]-1] += 1
for i in range(N):
        if Q-K < num[i]:
                print("Yes")
        else:
                print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())

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

AList.sort()

ResultList = []
PrimeList = []

tmp = 0

if N > 1:
    if AList[0] != AList[1]:
        ResultList.append(AList[0])
else:
    ResultList.append(AList[0])
PrimeList.append(AList[0])


for p in range(1, N - 1):
    tmp = 0
    if AList[p - 1] != AList[p] and AList[p] != AList[p + 1]:
        for q in PrimeList:
            if AList[p] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[p])
            PrimeList.append(AList[p])
    else:
        PrimeList.append(AList[p])

tmp = 0
if N > 1:
    if AList[N - 2] != AList[N - 1]:
        for q in PrimeList:
            if AList[N - 1] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[N - 1])

print(len(ResultList))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())

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

AList.sort()

dp = [0] *  (AList[-1] + 1)

for i in AList:
    dp[i] += 1
    
    if dp[i] == 1:
        for p in range(2 * i, len(dp), i):
            dp[p] += 2

print(dp.count(1))
### BUGGY CODE ###

def main():
    from collections import deque
    import sys

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

    an=[0]*(n-1)
    tg = deque([1])
    wwk =deque([])
    con =0

    while con<=m*2:
        for i in range(len(tg)):
            itg = tg.pop()
            wk =deque(abl[itg-1])
            for j in range(len(wk)):
                iwk=wk.pop()
                con += 1
                if an[iwk-2]==0 and iwk!=1:
                    an[iwk-2]=itg
                    wwk.append(iwk)
                if all(an):
                    print('Yes')
                    for j in an:
                        print(j)
                    sys.exit()
        tg=deque(wwk)
        wwk =deque([])

    print('No')

main()

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

#D
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
heapq.heapify(a)
tmp = 0
for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        if c >= tmp:
            p = heapq.heappop(a)
            if c > p:
                heapq.heappush(a,c)
            else:
                heapq.heappush(a,p)
                tmp = p
                break
            
        tmp = p
            
print(sum(a))

### FIXED CODE ###

#D
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append((b,c))
bc.sort(key=lambda x:-x[1])
heapq.heapify(a)
for i in range(m):
    b,c = bc[i][0],bc[i][1]
    for j in range(b):
        p = heapq.heappop(a)
        if c > p:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,p)
            break
            
            
print(sum(a))
### BUGGY CODE ###

import collections
from collections import defaultdict
N = int(input())
edges = []
vertexes = []
count = defaultdict(int)
parent = {}
childs = defaultdict(list)
color_dict = defaultdict(dict)
for i in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  childs[a].append(b)
  edges.append((a,b))
  vertexes.append(a)
  vertexes.append(b)
  
#print(edges)
#print(vertexes)
#print(parent)
#childs = dict(childs)
#print(childs)

c = collections.Counter(vertexes)
max_color = max(c.values())
print(max_color)

parent_color = {1: -1}
for i in range(1, N):
  if i not in childs:
    continue
  pc = parent_color[i]
  allowed_colors = [j for j in range(1, max_color + 1) if j != pc]
  for child, color in zip(sorted(childs[i]), allowed_colors):
    color_dict[i][child] = color
    parent_color[child] = color
    
#print(color_dict)

for e in edges:
  print(color_dict[e[0]][e[1]])

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

# make graph
# graph(x): xと繋がっている頂点（番号）のリスト
graph = [[] for _ in range(N+1)]
for a,b in AB:
  graph[a].append(b)
  graph[b].append(a)

# 深さ優先探索で、頂点の探索順序を作成
root = 1
parent = [0] * (N+1) # parent[x]: xの親の番号
order = [] # 深さ優先探索の順序リスト
stack = [root]
while stack:
  x = stack.pop()
  order.append(x)
  for y in graph[x]:
    if y == parent[x]:
      continue
    parent[y] = x
    stack.append(y)

# color[i]: 頂点iとその親の間の辺の色
color = [-1] * (N+1)

# 頂点の探索順ごとに、頂点とその子の間の辺の色を決定
for x in order:
  ng = color[x] # 頂点xとxの親との間の辺の色
  c = 1
  # 頂点xとつながっている頂点のリストを取得し、辺の色を1から順に割り当てる
  for y in graph[x]:
    if y == parent[x]: # xの親の頂点の場合は何もしない
      continue
    if c == ng: # xとその親との間の辺の色は割り当てないようにする
      c += 1
    color[y] = c
    c += 1

# 回答作成
answer = []
for a,b in AB:
  # aがbの子ならcolor[a]を、逆の場合はcolor[b]を出力する
  if parent[a] == b:
    answer.append(color[a])
  else:
    # 今回の場合、a_i < b_iで、番号の小さい方が親になるように木を作っているので、
    # こちらの条件のほうにしか引っかからないはず
    answer.append(color[b])

K = max(answer) # 色の番号の中で最も大きいものがK
print(K)
print('\n'.join(map(str,answer)))