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

import collections
import itertools

N = int(input())
s_list = []
for i in range(N):
    s_list.append(input())

s_list.sort()
sorted_list = []
for s in s_list:
    l2 = []
    for i in range(len(s)):
        l2.append(s[i])
    l2.sort()
    a = ""
    for i in l2:
        a += i
    sorted_list.append(a)
    
C = collections.Counter(sorted_list)
ans = 0
for i in C:
    ans += len(list(itertools.combinations(range(C[i]), 2)))
print(ans)


### FIXED CODE ###

import collections
import itertools
ans = 0

N = int(input())
s_list = []
for i in range(N):
    s_list.append(input())

d = {}
for s in s_list:
    l2 = []
    for i in range(len(s)):
        l2.append(s[i])
    l2.sort()
    a = ""
    for i in l2:
        a += i
    if a in d:
        ans+=d[a]
        d[a]+=1
    else:
        d[a] = 1

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

from collections import deque
 
def main():
    h, w = map(int, input().split())
    maze= [list(input()) for i in range(h)]
    route = [[-1] * w for i in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if maze[i][j] == "#":
               que.append([i, j])
               route[i][j] = 0
            
    ans = 0
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and route[nx][ny] == -1:
                route[nx][ny] = route[x][y] + 1
                que.append([nx, ny])
                ans = max(ans , route[nx][ny])

    print(ans)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))
### BUGGY CODE ###

N,Q=map(int,input().split())
C=list(map(int,input().split()))
LR=sorted([[i]+list(map(int,input().split())) for i in range(Q)],key=lambda x:x[2])
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=[0]*(N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        if a>0:
            r=self.sum(0,b)-self.sum(0,a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.data[i]
                i-=i&-i
        return r
b=BIT(N)
p=[-1]*N
q=0
a=[0]*Q
for i in range(N):
    if p[C[i]-1]>=0:
        b.add(p[C[i]-1],-1)
    p[C[i]-1]=i
    b.add(i,1)
    while q<Q and LR[q][2]==i+1:
        a[LR[q][0]]=b.sum(LR[q][1]-1,LR[q][2])
        q+=1
print(*a,sep='\n')

### FIXED CODE ###

def main(N,Q,C,LR,A):
    data=[0]*(N+1)
    def add(i,x):
        i+=1
        while i<=N:
            data[i]+=x
            i+=i&-i
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return njit(f)

    main=cc_export(main,(i8,i8,i8[:],i8[:,:],i8[:]))
    cc.compile()
    exit()

def input(): return sys.stdin.buffer.readline()
N,Q=map(int,input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
LR=np.array(sys.stdin.buffer.read().split(),dtype=np.int64).reshape(Q,2)
A=np.argsort(LR[:,1])

from my_module import main
print(*main(N,Q,C,LR,A),sep='\n')
### BUGGY CODE ###

def gcd(a,b):
    if a <= b:
        a,b = b,a
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

L_gcd = [A[0]]
R_gcd = [A[-1]]

for i in range(1,N):
    L_gcd.append(gcd(L_gcd[i-1],A[i]))
    R_gcd.insert(0,gcd(A[N-i-1],R_gcd[0]))

ans = [max(L_gcd[-2],R_gcd[1])]
for i in range(N-2):
    ans.append(gcd(L_gcd[i],R_gcd[i+2]))
print(max(ans))

### FIXED CODE ###

def gcd(a,b):
    if a <= b:
        a,b = b,a
    if b == 0:
        return a
    if a%b == 0:
        return b
    else:
        return gcd(b,a%b)

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

L_gcd = [0]*(N+1)
R_gcd = [0]*(N+1)

for i in range(N):
    L_gcd[i+1] = gcd(L_gcd[i],A[i])
    R_gcd[N-i-1] = gcd(R_gcd[N-i],A[N-i-1])

ans = 0
for i in range(N):
    if gcd(L_gcd[i],R_gcd[i+1])>ans:
        ans = gcd(L_gcd[i],R_gcd[i+1])
    
print(ans)
### BUGGY CODE ###

import time
import math

def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    for i in range(N):
        B[i+1] = B[i] + A[i]
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([C(i, 2) for i in d.values()]))
        
c = {}
f = math.factorial
def C(n, r):
    if (n, r) in c.keys():
        return c[n, r]
    if n < 0 or r<0 or n<r:
        return 0
    c[(n, r)] = f(n) // (f(n-r) * f(r))
    return c[(n, r)]


# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)

main()


### FIXED CODE ###


def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    accum = 0
    for i in range(N+1):
        B[i] = accum
        if i != N:
            accum += A[i]
    
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([i * (i - 1)//2 for i in d.values()]))
        
# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

H, W = map(int, input().split())

m = []
for i in range(H):
    m.append(input().rstrip('\n'))

wei = [[0]*(W+1) for _ in range(H+1)]
for h in range(H):
    for w in range(W):
        if m[h][w] == '.':
             wei[h][w] = wei[h][w-1] + 1
        else:
            wei[h][w] = 0
    #reverse
    for wz in range(W-1, -1, -1):
        if wei[h][wz] > 0 and wei[h][wz] < wei[h][wz+1]:
                wei[h][wz] = wei[h][wz + 1]

hei = [[0]*(W+1) for _ in range(H+1)]
for w in range(W):
    for h in range(H):
        if m[h][w] == '.':
             hei[h][w] = hei[h-1][w] + 1
        else:
            hei[h][w] = 0

    #reverse
    for hz in range(H-1, -1, -1):
        if hei[hz][w] > 0 and hei[hz][w] < hei[hz+1][w]:
            hei[hz][w] = hei[hz+1][w]

ans = 0
for h in range(H):
    for w in range(W):
       val = wei[h][w] + hei[h][w] - 1
       if ans < val:
           ans = val

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())

m = []
for i in range(H):
    m.append(input().rstrip('\n'))

wei = [[0]*(W+1) for _ in range(H+1)]
for h in range(H):
    for w in range(W):
        if m[h][w] == '.':
             wei[h][w] = wei[h][w-1] + 1
        else:
            wei[h][w] = 0
    #reverse
    for wz in range(W-1, -1, -1):
        if wei[h][wz] > 0 and wei[h][wz] < wei[h][wz+1]:
                wei[h][wz] = wei[h][wz + 1]

hei = [[0]*(W+1) for _ in range(H+1)]
for w in range(W):
    for h in range(H):
        if m[h][w] == '.':
             hei[h][w] = hei[h-1][w] + 1
        else:
            hei[h][w] = 0

    #reverse
    for hz in range(H-1, -1, -1):
        if hei[hz][w] > 0 and hei[hz][w] < hei[hz+1][w]:
            hei[hz][w] = hei[hz+1][w]

ans = 0
for h in range(H):
    for w in range(W):
       val = wei[h][w] + hei[h][w] - 1
       if ans < val:
           ans = val

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

l, r = map(int, input().split())

if l > r:
    l, r = r, l

mod = 2020

for i in range(l, r+1):
    for j in range(i+1, r+1):
        tmp = i * j % 2019
        if tmp < mod:
            mod = tmp

print(mod)

### FIXED CODE ###

l, r = map(int, input().split())

mod = 2018

if r - l >= 2019:
    print(0)
else:
    for i in range(l, r):
        for j in range(i+1, r+1):
            tmp = i * j % 2019
            if tmp < mod:
                mod = tmp
    print(mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a_s = list(map(int, input().split()))
bs = list(map(int, input().split()))
cs = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = 0
minlist = 0
for a in a_s:
    if minlist > (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist > (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if  i > k:
                minlist = min(list)
            if minlist > abc:
                break
            list.append(a + b + c)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

import sys

s = str(sys.stdin.readline())
count = 0
f = False
while True:
    p1 = s.find("01")
    p2 = s.find("10")
    if p1 == -1 and p2 == -1:
        i = None
    elif p1 == -1:
        i = p2
    elif p2 == -1:
        i = p1
    else:
        i = p1 if p1 < p2 else p2

    if i is not None:
        count += 2
        s = s[:i] + s[i + 2:]
        continue

    break
print(count)

### FIXED CODE ###

import sys

s = str(sys.stdin.readline())
c0 = s.count('0')
c1 = s.count('1')
r = c0 if c0 < c1 else c1
print(r*2)
### BUGGY CODE ###

from functools import lru_cache

N,K=[int(i) for i in input().split(" ")]
V=[int(i) for i in input().split(" ")]

@lru_cache()
def value(V,k,hands):
    hands=list(hands)
    V=list(V)
    if k==0:
        return sum(hands)
    else:
        retval=sum(hands)
        try:
            retval=max(value(tuple(V[1::]),k-1,tuple(sorted(hands+[V[0]]))),retval)
        except:
            pass
        try:
            p2=value(tuple(V[:-1:]),k-1,tuple(sorted(hands+[V[-1]])))
            retval=max(retval,p2)
        except:
            pass
        try:
            p3=value(tuple(V+[hands[0]]),k-1,tuple(hands[1::]))
            retval=max(p3,retval)
        except:
            pass
        try:
            p4=value(tuple([hands[0]]+V),k-1,tuple(hands[1::]))
            retval=max(p4,retval)
        except:
            pass
        return retval

print(value(tuple(V),K,tuple()))


### FIXED CODE ###

from functools import lru_cache
import numpy as np

N,K=[int(i) for i in input().split(" ")]
V=[int(i) for i in input().split(" ")]

retval=0
for left in range(max(N+1,K+1)):
    for right in range(min(N-left+1,K-left+1)):
        modoseru=K-(left+right)
        temoto=np.asarray(sorted(V[:left:]+V[N-right::]))
        modosu=min(np.sum(temoto<0),modoseru)
        retval=max(sum(temoto[modosu::]),retval)

print(retval)
### BUGGY CODE ###

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

def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

base_num = N-K+1
for i in range(K):
    select_num = nCk(base_num,i+1)
    seq_num = nCk(K-1,i)
    count_n = select_num*seq_num%(10**9 + 7)
    print(count_n)


### FIXED CODE ###

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

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

mod = 10**9+7 #出力の制限
max_N = 2000 #階乗の制限どれだけ
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

base_num = N-K+1
for i in range(K):
    select_num = cmb(base_num,i+1,mod)
    seq_num = cmb(K-1,i,mod)
    count_n = (select_num*seq_num)%mod
    print(count_n)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1

print(ans)


### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(k+1):
        if x+y > s:
            continue
        if 0 <= s-x-y <= k:
            ans += 1

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

h,w=map(int,input().split())
hf=[[0 for i in range(w)]for i in range(h)]
vf=[[0 for i in range(w)]for i in range(h)]
field=[]
for i in range(h):
    field.append(list(input()))
for i in range(h):
    tmp=0
    for j in range(w):
        if field[i][j]=='.':
            tmp+=1
            hf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for j in range(w):
        j=w-j-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=hf[i][j]
            else:
                hf[i][j]=tmp
        else:
            tmp=0
for j in range(w):
    tmp=0
    for i in range(h):
        if field[i][j]=='.':
            tmp+=1
            vf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for i in range(h):
        i=h-i-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=vf[i][j]
            else:
                vf[i][j]=tmp
        else:
            tmp=0
mx=0
for i in range(h):
    for j in range(w):
        if hf[i][j]+vf[i][j]>mx:
            mx=hf[i][j]+vf[i][j]
print(mx-1)

### FIXED CODE ###

h,w=map(int,input().split())
hf=[[0 for i in range(w)]for i in range(h)]
vf=[[0 for i in range(w)]for i in range(h)]
field=[]
for i in range(h):
    field.append(list(input()))
for i in range(h):
    tmp=0
    for j in range(w):
        if field[i][j]=='.':
            tmp+=1
            hf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for j in range(w):
        j=w-j-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=hf[i][j]
            else:
                hf[i][j]=tmp
        else:
            tmp=0
for j in range(w):
    tmp=0
    for i in range(h):
        if field[i][j]=='.':
            tmp+=1
            vf[i][j]=tmp
        else:
            tmp=0
    tmp=0
    for i in range(h):
        i=h-i-1
        if field[i][j]=='.':
            if tmp == 0:
                tmp=vf[i][j]
            else:
                vf[i][j]=tmp
        else:
            tmp=0
mx=0
for i in range(h):
    for j in range(w):
        if hf[i][j]+vf[i][j]>mx:
            mx=hf[i][j]+vf[i][j]
print(mx-1)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
# ある回数から先は全ての電球にNを足す
for _ in range(K):
    next = [0] * N
    for i in range(N):
        x = A[i]
        for j in range(max(0, i-x), min(N-1, i+x)+1):
            next[j] += 1
    A = next
    if sum(A) == N * N:
        break

print(*A)

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

K, S = map(int,input().split())
ans = 0

for i in range(K+1):
  for j in range(K+1):
    if 0<=i<=K and 0<=S-i-j<=K and 0<=j<=K:
      ans += 1
#    print(i, j, S-i-j, ans)
      

print(ans)


### FIXED CODE ###

K, S = map(int,input().split())
ans = 0

for i in range(K+1):
  for j in range(K+1):
    if 0<=S-i-j<=K:
      ans += 1
#    print(i, j, S-i-j, ans)
      

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

# 組み合わせ(高速，フェルマーの小定理を利用)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
N = 10 ** 9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


N, A, B = map(int, input().split())
tmp = (2 ** N - 1) % mod 
a = cmb(N, A, mod)
b = cmb(N, B, mod)
print(((tmp + mod) - a - b ) % mod)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(n, r, p):
    ret = 1
    while 1:
        if (r == 0):
            break
        N = n % p
        R = r % p
        if N < R:
            return 0
        for i in range(R):
            ret = ret * (N-i) % p
        imul = 1
        for i in range(R):
            imul = imul * (i+1) % p
        ret = ret * modinv(imul, p) % p
        n //= p
        r //= p
    return ret

mod = 10 ** 9 + 7
N, A, B = map(int, input().split())
tmp = (2 ** N - 1) % mod 
a = comb(N, A, mod)
b = comb(N, B, mod)
print(((tmp + mod) - a - b ) % mod)
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    #s.append(list(input())) # !!!
    #s.append(sorted(list(input()))) # !!!
    s.append(sorted(input())) # !!!
#print(s)
 
x = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            x += 1
 
print(x)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    #s.append(list(input())) # !!!
    #s.append(sorted(list(input()))) # !!!
    #s.append(sorted(input())) # !!!
    s += [''.join(sorted(input()))]
    #''.join(sorted((sorted(input()))
s = sorted(s)
s.append('X')
#print(s)

a = []
x = 1
for i in range(1,n+1):
    if s[i] == s[i-1]:
        x += 1
    else:
        a.append(x)
        x = 1
#print(a)
y = 0

for j in a:
    y += j*(j-1)/2

print(int(y))
### BUGGY CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    vis[now][step] = cnt
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            q.append((x,cnt+1))
if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3)



### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
### BUGGY CODE ###

import numpy as np
N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f

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

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
for p in prime:
	q = p**N
	if P % q == 0:
		ans*=p
		P=P//q
		while(P % q == 0):
			ans*=p
			P=P//q
print(ans)





### FIXED CODE ###

import numpy as np
N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f


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

thres = int(np.log2(P))+1
if N > thres:
	print(1)
	exit()

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
	
for p in prime:
	q = p**N
	if P < q:
		break
	if P % q == 0:
		ans*=p
		q*= p**N
		while(P % q == 0):
			ans*=p
			q*=p**N

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

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

settansaku = set([])
setmada = {0}
listmada = [(0, None)]  #left: Vertex, right: Color
kouho = 1
num = [0 for _ in range(n-1)]

while kouho != 0:
	for i, cnt in listmada[:]:
		colors = {cnt}
		settansaku.add(i)
		setmada.remove(i)
		listmada.remove((i, cnt))
		kouho -= 1
		for k, j in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					c = 0
					while True:
						if c not in colors:
							listmada.append((k, c))
							colors.add(c)
							num[j] = c
							break
						c += 1
					kouho += 1

print(max(num)+1)
print("\n".join([str(i+1) for i in num]))

### FIXED CODE ###

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

settansaku = set([])
setmada = {0}
listmada = [(0, None)]  #left: Vertex, right: Color
kouho = 1
num = [0 for _ in range(n-1)]

while kouho != 0:
	for i, cnt in listmada[:]:
		colors = {cnt}
		settansaku.add(i)
		setmada.remove(i)
		listmada.remove((i, cnt))
		kouho -= 1
		c = 0
		for k, j in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					while True:
						if c not in colors:
							listmada.append((k, c))
							colors.add(c)
							num[j] = c
							break
						c += 1
					kouho += 1

print(max(num)+1)
print("\n".join([str(i+1) for i in num]))