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

#!/usr/bin/env python3
import sys
INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    # 入次数0の節点を列挙
    in_deg = [0]*N
    for i in range(N):
        for to in E[i]:
            in_deg[to] += 1

    head = 0
    ans = [v for v in range(N) if in_deg[v] == 0]

    # 入次数0のものを順番に走査。同時に入次数を更新
    while head < len(ans):                  # O(V+E)
        v = ans[head]
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
        head += 1
    if len(ans) != N:
        return False, ans
    return True, ans


def reversed_graph(E):
    rev = [[] for _ in E]
    for i, dest in enumerate(E):
        for t in dest:
            rev[t].append(i)
    return rev


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a-1].append(b-1)

    rE = reversed_graph(E)
    # print(rE)

    looped1, order1 = Topological_sorting(E)
    looped2, order2 = Topological_sorting(rE)
    # print(looped1, order1)
    # print(looped2, order2)

    if looped1 and looped2:
        print(-1)
        return

    nodes = set(range(N))-set(order1)-set(order2)
    # nodes内部でlevel-order-likeな探索が必要
    q = [list(nodes)[0]]
    seen = [0]*N
    prev = [-1]*N
    head = 0
    while head < len(q):
        v = q[head]
        seen[v] = 1
        poi = set()
        for u in E[v]:
            if u not in nodes:
                continue
            if seen[u] == 1:
                # ループ
                poi.add(u)
                prev[u] = v
                continue
            q.append(u)
            prev[u] = v
        if poi:
            # print(poi, v)
            ans = []
            while v not in poi:
                ans.append(v)
                v = prev[v]
            ans.append(v)
            break

        head += 1
    print(len(ans))
    print(*[a+1 for a in ans], sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
# https://atcoder.jp/contests/abc142/submissions/7764934
# ほぼまんま。


def main():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)

    # スタート地点は全て試す
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            # これまで通ってきた頂点と行き先の積集合
            s = route & E[v]
            # sが空集合(ループでない)か、行き先に始点のみが含まれる場合は継続
            # 行き先に始点以外の場所が含まれるなら、もっと良い始点の選び方がある。
            # if not (not s or (s == {start})):
            if s and s != {start}:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


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

from collections import*
def main():
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d={}
    s=0
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,z=i,j
            if z<x:x,z=z,x
            x=x*n+z
            y,z=i,k
            if z<y:y,z=z,y
            y=y*n+z
            if not x in d:
                d[x]=s
                s+=1
            if not y in d:
                d[y]=s
                s+=1
            es+=(d[x],d[y]),
    e=[[]for _ in range(s)]
    for i,j in es:e[i]+=j,
    outs=defaultdict(list)
    ins=defaultdict(int)
    f=set(range(s))
    for i,j in es:
        outs[i].append(j)
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    while q:
        i=q.popleft()
        r+=i,
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
    if len(r)<s:
        print(-1)
        return
    data=[1]*s
    for i in r:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()

### FIXED CODE ###

def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(len(r)<s)or m)
main()
### BUGGY CODE ###

def gcd(x,y):
    if x <= y:
        z = x
        x = y
        y = z
    if y == 0:
        return x
    else:
        return gcd(y,x%y)

n = int(input())
s = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        a = gcd(i,j)
        for k in range(1,n+1):
            b = gcd(a,k)
            s += b
print(s)



### FIXED CODE ###

import math
n = int(input())
s = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        a = math.gcd(i,j)
        for k in range(1,n+1):
            b = math.gcd(a,k)
            s += b
print(s)
### BUGGY CODE ###

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

que = []

for i in range(N//(A+B)+1):
    for j in range(A):
        que.append('b')
    for j in range(B):
        que.append('r')

count = 0
for i in range(N):
    if que[i] == 'b':
        count += 1

print(count)

### FIXED CODE ###

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

ans = (N // (A + B)) * A

if (N % (A + B)) > A:
    ans += A
else:
    ans += N % (A + B)

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

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        if end < 0:
            continue
        cnt += sum(dp[start:end+1]) % mod
        cnt %= mod
    dp[i] = cnt

print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
dp = [0] * N
dp[0] = 1
dp_sum = [0] * N
dp_sum[0] = 1
L = [0] * K
R = [0] * K
mod = 998244353

for i in range(K):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

for i in range(1, N):
    # マスiにたどり着くためのパターン数を数える
    cnt = 0
    for j in range(K):
        start = max(0, i - R[j])
        end = i - L[j]
        cnt += (dp_sum[end] - dp_sum[start - 1]) % mod
        cnt %= mod
    dp[i] = cnt
    dp_sum[i] = dp_sum[i - 1] + cnt

print(dp[N - 1])
### BUGGY CODE ###

import re
n,q=map(int,input().split())
s=input()
a=[0]*n
b=[0]*n
i=[p.span()[0]for p in re.finditer('(AC){1,1}',s)]
c=0
for m in range(n):
  if c>=len(i):
    if m<n-1:a[m+1]=a[m]
    b[m]=b[m-1]
    continue
  if m==i[c]:
    if m>0:
      if m<n-1:a[m+1]=a[m]+1
      b[m]=b[m-1]+1
    else:
      a[m]=0
      a[m+1]=1
      b[m]+=1
    c+=1
  else:
    a[m+1]=a[m]
    b[m]=b[m-1]
for _ in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-max(b[:l-1]+[0]))

### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()
a=[0]*n
b=[0]*n
i=[p.span()[0]for p in re.finditer('(AC){1,1}',s)]
c=0
for m in range(n):
  if c>=len(i):
    if m<n-1:a[m+1]=a[m]
    b[m]=b[m-1]
    continue
  if m==i[c]:
    if m>0:
      if m<n-1:a[m+1]=a[m]+1
      b[m]=b[m-1]+1
    else:
      a[m]=0
      a[m+1]=1
      b[m]+=1
    c+=1
  else:
    a[m+1]=a[m]
    b[m]=b[m-1]
for _ in range(q):
  l,r=map(int,input().split())
  if l>=2:
    print(a[r-1]-b[l-2])
  else:
    print(a[r-1])
### BUGGY CODE ###

#n = 4
#a = [141421356, 17320508, 22360679, 244949]
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7

ans = 0
for i in range(n):
    for j in range(i, n):
        if i == j:
            continue
        ans += (a[i]*a[j])
print(ans%MOD)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 0
plus = 0
for i in range(n-1):
    plus += a[n-i-1]
    plus %= MOD
    ans += a[n-i-2]*plus
    ans %= MOD
print(ans%MOD)
### BUGGY CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0,0,0,0,0]for _ in range(c+1)]for _ in range(r+1)]
for x,y,z in a:
    dp[x][y][4]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[i][j][4]
        dp[i][j][0]=max(dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3])
        dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+v,dp[i-1][j][0]+v,dp[i-1][j][1]+v,dp[i-1][j][2]+v,dp[i-1][j][3]+v)
        dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+v)
        dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+v)
print(max(dp[i][j]))

### FIXED CODE ###

r,c,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(k)]
dp=[[[0 for _ in range(c+1)]for _ in range(r+1)]for _ in range(5)]
for x,y,z in a:
    dp[4][x][y]=z
for i in range(1,r+1):
    for j in range(1,c+1):
        v=dp[4][i][j]
        dp[0][i][j]=max(dp[0][i][j-1],dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])
        dp[1][i][j]=max(dp[1][i][j-1],dp[0][i][j-1]+v,dp[0][i-1][j]+v,dp[1][i-1][j]+v,dp[2][i-1][j]+v,dp[3][i-1][j]+v)
        dp[2][i][j]=max(dp[2][i][j-1],dp[1][i][j-1]+v)
        dp[3][i][j]=max(dp[3][i][j-1],dp[2][i][j-1]+v)
print(max([dp[i][r][c] for i in range(4)]))
### BUGGY CODE ###

n = int(input())
num = list(map(int,input().split()))
ans = 1
limit = 10**18
for i in range(n):
  ans *= num[i]
if ans>limit:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

n = int(input())
num = list(map(int,input().split()))
ans = 1
limit = 1000000000000000000
if 0 in num:
  print(0)
else:
  for item in num:
    ans *= item
    if ans>limit:
      ans = -1
      break

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

import sys
sys.setrecursionlimit(10**7)

def xor(x):
  if x == 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def xor(x):
  if x <= 0:
    return 0
  if x == 1:
    return 1
  if x == 2:
    return 3
  if x == 3:
    return 0
  t = 2 ** (len(bin(x))-3)
  if x==t:
    return t
  return t*((x-t)%2^1) + xor(x-t)
a, b = map(int, input().split())
print(xor(b) ^ xor(a-1))
### BUGGY CODE ###

n, c = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(c)]
grid = [list(map(int, input().split())) for _ in range(n)]

lst_0 = []
lst_1 = []
lst_2 = []
for i in range(n):
    for j in range(n):
        if (i+j+2) % 3 == 0:
            lst_0.append(grid[i][j])
        elif (i+j+2) % 3 == 1:
            lst_1.append(grid[i][j])
        else:
            lst_2.append(grid[i][j])

cost0 = []
for i in range(1, c+1):
    C = 0
    for j in lst_0:
        if j != i:
            C += cost[j-1][i-1]
    cost0.append(C)

cost1 = []
for i in range(1, c+1):
    C = 0
    for j in lst_1:
        if j != i:
            C += cost[j-1][i-1]
    cost1.append(C)

cost2 = []
for i in range(1, c+1):
    C = 0
    for j in lst_2:
        if j != i:
            C += cost[j-1][i-1]
    cost2.append(C)

min_cost = 10**100
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                min_cost = min(min_cost, cost0[i]+cost1[j]+cost2[k])
print(min_cost)

### FIXED CODE ###

n, c = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(c)]
grid = [list(map(int, input().split())) for _ in range(n)]

lst_0 = []
lst_1 = []
lst_2 = []
for i in range(n):
    for j in range(n):
        if (i+j+2) % 3 == 0:
            lst_0.append(grid[i][j])
        elif (i+j+2) % 3 == 1:
            lst_1.append(grid[i][j])
        else:
            lst_2.append(grid[i][j])

cost0 = []
for i in range(1, c+1):
    C = 0
    for j in lst_0:
        if j != i:
            C += cost[j-1][i-1]
    cost0.append(C)

cost1 = []
for i in range(1, c+1):
    C = 0
    for j in lst_1:
        if j != i:
            C += cost[j-1][i-1]
    cost1.append(C)

cost2 = []
for i in range(1, c+1):
    C = 0
    for j in lst_2:
        if j != i:
            C += cost[j-1][i-1]
    cost2.append(C)

min_cost = 10**100
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                min_cost = min(min_cost, cost0[i]+cost1[j]+cost2[k])
print(min_cost)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in range(m)]

    g = [[] for _ in range(n)]

    for s, t in st:
        s -= 1
        t -= 1
        g[s].append(t)

    deg = [len(x) for x in g]

    dp = [0] * n

    for u in range(n-1)[::-1]:
        now = 0
        for v in g[u]:
            now += dp[v]

        now /= deg[u]
        now += 1
        dp[u] = now

    ans = dp[0]

    for u in range(n-1):
        if deg[u] == 1:
            continue

        d = g[u][0]
        for v in g[u]:
            if dp[d] < dp[v]:
                d = v

        dp2 = [0] * n
        for x in range(n - 1)[::-1]:
            now = 0
            for y in g[x]:
                if x == u and y == d:
                    continue
                now += dp2[y]

            if x == u:
                now /= deg[x] - 1
            else:
                now /= deg[x]

            now += 1
            dp2[x] = now

        ans = min(ans, dp2[0])

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    st = [list(map(int, input().split())) for _ in range(m)]

    g = [[] for _ in range(n)]

    for s, t in st:
        s -= 1
        t -= 1
        g[s].append(t)

    deg = [len(x) for x in g]

    dp = [0] * n

    for u in range(n-1)[::-1]:
        now = 0
        for v in g[u]:
            now += dp[v]

        now /= deg[u]
        now += 1
        dp[u] = now

    ans = dp[0]

    for u in range(n-1):
        if deg[u] == 1:
            continue

        d = g[u][0]
        for v in g[u]:
            if dp[d] < dp[v]:
                d = v

        dp2 = [0] * n
        for x in range(n - 1)[::-1]:
            now = 0
            for y in g[x]:
                if x == u and y == d:
                    continue
                now += dp2[y]

            if x == u:
                now /= deg[x] - 1
            else:
                now /= deg[x]

            now += 1
            dp2[x] = now

        ans = min(ans, dp2[0])

    print(ans)


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

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def run():
    N = input()
    S = input()
    dp = [0] * 1000
    ans = 0
    for n in S:
        n = int(n)
        #print(dp)
        for i in range(1000):
            if i // 100 == n and dp[i] == 0:
                dp[i] = 1
                #print(f'{i} -> 1')
            elif (i // 10) % 10 == n and dp[i] == 1:
                dp[i] = 2
                #print(f'{i} -> 2')
            elif i % 10 == n and dp[i] == 2:
                dp[i] = 3
                #print(f'{i} -> 3')
                ans += 1
    print(ans)

    #print(factorials)
if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def run():
    N = input()
    S = input()
    dp = [0] * 1000
    ans = 0
    for n in S:
        n = int(n)
        #print(dp)
        for i in range(1000):
            if i // 100 == n and dp[i] == 0:
                dp[i] = 1
                #print(f'{i} -> 1')
            elif (i // 10) % 10 == n and dp[i] == 1:
                dp[i] = 2
                #print(f'{i} -> 2')
            elif i % 10 == n and dp[i] == 2:
                dp[i] = 3
                #print(f'{i} -> 3')
                ans += 1
    print(ans)

    #print(factorials)
if __name__ == "__main__":
    run()
### BUGGY CODE ###

import sys
import copy
import itertools
input = sys.stdin.readline

N=int(input())

A=[]
for i in range(70):
    A.append(i+1)

D=list(itertools.combinations_with_replacement(A, 3))
#print(len(D))
for j in range(N):
    count=0
    for sa in D:
    
        if ((sa[0]+sa[1]+sa[2])**2)-(sa[0]*sa[1]+sa[1]*sa[2]+sa[2]*sa[0])==j+1:
            if sa[0]!=sa[1] and sa[1] !=sa[2]:
                
                count+=6
            elif sa[0]==sa[1] and sa[1]==sa[2]:
                count+=1
            else:
                count+=3

    print(count)


### FIXED CODE ###

import sys

import itertools
input = sys.stdin.readline
 
N=int(input())

ans=[0]*10050

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            v=i*i+j*j+k*k+i*j+i*k+j*k
            if v<10050:
                ans[v]+=1

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

import numpy
import math
L = int(input())
print(numpy.sum([math.gcd(math.gcd(i + 1, j + 1), k + 1) for i in range(L) for j in range(L) for k in range(L)]))

### FIXED CODE ###

import numpy
import math

L = int(input())
ans = 0
for i in range(L):
    for j in range(L):
        t = math.gcd(i+1, j+1)
        for k in range(L):
            ans += math.gcd(t, k + 1)
print(ans)
### BUGGY CODE ###

from itertools import combinations

n = int(input())
l = list( map(int, input().split())) 
ans = 0

l3s = list(combinations(l,3))
for l3 in l3s:
    if abs(l3[1] - l3[2]) < l3[0] < (l3[1] + l3[2]):
        ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list( map(int, input().split())) 
ans = 0
l.sort()

for i in range(n-2):
    shortest = l[i]
    for j in range(i+1, n-1):
        second = l[j]
        # このスライスしたやつと地味にTLEになる...
        # k = bisect_left(l[j], shortest + second)
        # ans += k

        k = bisect_left(l, shortest + second)
        ans += k - j - 1

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

import numpy as np

def main():
    h, w, k = map(int, input().split())
    s = np.array([[int(i) for i in list(input())] for _ in range(h)])
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    for i in range(2**(h - 1)):
        ss = np.split(s, [j + 1 for j in range(h - 1) if i & 2**j])
        stack = np.zeros(cnt[i] + 1, dtype=int)
        for j in range(w):
            sm = [st.T[j].sum() for st in ss]
            if max(sm) > k:
                cnt[i] = 100000
                break
            for t, st in enumerate(sm):
                stack[t] += st
            if max(stack) > k:
                for t, st in enumerate(sm):
                    stack[t] = st
                cnt[i] += 1
    print(min(cnt))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    h, w, k = map(int, input().split())
    s = [[int(i) for i in list(input())] for _ in range(h)]
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    c = 0
    for ci in [sum(i) for i in zip(*s)]:
        if ci > k:
            cnt[0] = 100000
            break
        c += ci
        if c > k:
            cnt[0] += 1
            c = ci
    for i in range(1, 2**(h - 1)):
        div = [j + 1 for j in range(h) if i & 2**j]
        ss = []
        l = 0
        for d in div:
            ss.append(s[l:d])
            l = d
        ss.append(s[l:])
        c = [0] * len(ss)
        t = [[sum(i) for i in zip(*si)] for si in ss]
        for j in range(w):
            if max(ti[j] for ti in t) > k:
                cnt[i] = 100000
                break
            for tt, ti in enumerate(t):
                c[tt] += ti[j]
            if max(c) > k:
                cnt[i] += 1
                c = [ti[j] for ti in t]
    print(min(cnt))

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

n = int(input())
a = list(map(int,input().split()))
sum = 0
for i in range(n):
    for j in range(i+1,n) :
        sum += a[i]*a[j]
m = 7+10**9
print(sum%m)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
s = sum(a)
ans = 0

for i in range(n-1):
    s -= a[i]
    ans += a[i]*s
m = 7 + 10**9
print(ans%m)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        while todo:
            u = todo.pop()
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

N = int(input())
i = int(N**(1/2))
while N%i != 0:
  i += 1
print(len(str(i)))

### FIXED CODE ###

N = int(input())
i = int(N**(1/2))
while N%i != 0:
  i -= 1
print(len(str(N//i)))