Harryxun/stf_run huggingface dataset:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

num_cost = {1: 2,
            2: 5,
            3: 5,
            4: 4,
            5: 5,
            6: 6,
            7: 3,
            8: 6,
            9: 5}

chosen = {}

n, m = li()
a = list(li())

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            dp[i+cost] = str(max(int(dp[i+cost]), int(num + dp[i])))

print(dp[n]

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

dic = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        use[dic[ai]] = max(use[dic[ai]], ai)
        
# 最大順
desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        
# 遷移
INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    cand = dp[i].copy()
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue

        if sum(cand) < sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            cand = tmp.copy()
            

        elif sum(cand) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(cand, tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    cand = tmp.copy()
                    break
                
    dp[i] = cand
                

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)
def check(n):
    num=int(n**0.5)
    l=[]
    for i in range(1,num+1):
        if n%i==0:
            l.append(i)
            l.append(n//i)
    return l

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

box=[0]*n
cnt=0
for i in range(n):
    if a[-(i+1)]==box[i]:continue
    cnt+=1
    box[i]=(box[i]+1)%2
    l=check(n-i)
    for j in l:
        box[j]=(box[j]+1)%2

print(cnt)
if cnt==0:exit()
print(*box[::-1])

### FIXED CODE ###

def check(n):
    num=int(n**0.5)
    l=[]
    for i in range(1,num+1):
        if n%i==0:
            l.append(i)
            l.append(n//i)
    return set(l)

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

box=[0]*n
cnt=0
ans=[0]*n
for i in range(n):
    if a[-(i+1)]==box[-(i+1)]:continue
    cnt+=1
    ans[-(i+1)]=1
    l=check(n-i)
    for j in l:
        box[j-1]=(box[j-1]+1)%2

print(cnt)
if cnt==0:exit()
for i in range(n):
    if ans[i]:
        print(i+1,end=' ')
def f():
    _ = int(input())
    nums = np.array(list(map(int, input().split())))
    # nums = [int(x) for x in input().split()]
    c = 0
    while True:
        if any(nums % 2 == 1):
            break
        c += 1
        nums = nums / 2
    print(c)


f()


### FIXED CODE ###

import numpy as np
# Me


def f():
    i = int(input())
    nums = np.array(list(map(int, input().split())))
    # nums = [int(x) for x in input().split()]
    c = 0
    while True:
        if any(nums % 2 == 1):
            break
        c += 1
        nums = nums / 2
    print(c)


f()


# Other
import sys
a= str(input())
kaibun = list(a)
n = int(len(kaibun))
answer = "No"
strongn1 = int((n-1)/2)
strongn2 = int((n+3)/2)
for i in reversed(range((int((n+1)/2)),n)):
    if kaibun[i] == kaibun[n-i-1]:
        answer = "Yes"
    else:
        answer = "No"
        print(answer)
        sys.exit()
for i in range(int(strongn1/2)):
    if kaibun[i] == kaibun[strongn1-i-1]:
        answer = "Yes"
    else:
        answer="No"
        print(answer)
        sys.exit()
for i in reversed(range(strongn2,n,int(strongn1/2))):
    if kaibun[i] == kaibun[strongn2-2-i+n]:
        answer = "Yes"
    else:
        answer = "No"
print(answer)


### FIXED CODE ###

a= str(input())
kaibun = list(a)
n = int(len(kaibun))
answer = "No"
strongn1 = int((n-1)/2)
strongn2 = int((n+3)/2)
for i in reversed(range((int((n+1)/2)),n)):
    if kaibun[i] == kaibun[n-i-1]:
        answer = "Yes"
    else:
        answer = "No"
        break

if answer == "Yes":
    for i in range(int(strongn1/2)):

        if kaibun[i] == kaibun[strongn1-i-1]:
            answer = "Yes"
        else:
            answer="No"
            break
if answer == "Yes":
    for i in reversed(range(strongn2+int(strongn1/2)-1,n)):
        if kaibun[i] == kaibun[strongn2-2-i+n]:
            answer = "Yes"
        else:
            answer = "No"
            break
print(answer)
from math import ceil

s, k = input(), int(input())

ans = []
a = ord('z') + 1
for i in s:
    if k == 0:
        ans.append(ord(i))
    elif a - ord(i) <= k and i != 'a':
        k -= a - ord(i)
        ans.append(ord('a'))
    else:
        ans.append(ord(i))
ans[-1] += k
if ans[-1] >= a:
    ans[-1] -= ceil((ans[-1] - (a - 1)) / 26)
print(*map(chr, ans), sep='')


### FIXED CODE ###

s, k = input(), int(input())

ans = []
a = ord('z') + 1
for i in s:
    if k == 0:
        ans.append(ord(i))
    elif a - ord(i) <= k and i != 'a':
        k -= a - ord(i)
        ans.append(ord('a'))
    else:
        ans.append(ord(i))
ans[-1] += k % 26
if ans[-1] >= a:
    ans[-1] -= 26
print(*map(chr, ans), sep='')
Xs = raw_input()
  Ys = raw_input()
  count = 0
  a = 0

  for j in range(len(Ys) + 1):
    dp[1][j] = Ys[j] 
  for i in range(len(Xs) + 1):
    dp[i][1] = Xs[i]

  for j in range(1, len(Ys) + 1):
    for i in range(a + 1, len(Xs) + 1):
      if dp[i][0] == dp[j][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

### FIXED CODE ###

def solve_lcs():
    x = raw_input()
    y = raw_input()
 
    a = len(x)
    b = len(y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = x[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print solve_lcs()
if input()=='SUN':
	print(7)
elif input()=='MON':
  print(6)
elif input()=='TUE':
  print(5)
elif input()=='WED':
  print(4)
elif input()=='THU
  print(3)
elif input()=='FRI':
  print(2)
elif input()=='SAT':
  print(1)


### FIXED CODE ###

s=input()
if s=='MON':
  print(6)
elif s=='TUE':
  print(5)
elif s=='WED':
  print(4)
elif s=='THU':
  print(3)
elif s=='FRI':
  print(2)
elif s=='SAT':
  print(1)
else:
  print(7)
S = input()
W = input()

if int(S) <= int(W):
  print('unsafe')
elif int(S) > int(W):
  print('safe')
  

### FIXED CODE ###

S,W=(int(x) for x in input().split())

if S <= W:
  print('unsafe')
else:
  print('safe')
#!/usr/bin/env python
# coding: utf-8

import math

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def calc(n, x):
    return n // x

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

def main():
    a, b, c, d = rli()
    lcm_cd = lcm(c, d)
    n_a = a-1 - calc(a-1, c) - calc(a-1, d) + calc(a-1, lcm_cd)
    n_b = b - calc(b, c) - calc(b, d) + calc(b, lcm_cd)
    print(n_b-n_a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

import fractions

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def calc(n, x):
    return n // x

def lcm(a, b):
    return (a * b) // fractions.gcd(a, b)

def main():
    a, b, c, d = rli()
    lcm_cd = lcm(c, d)
    n_a = a-1 - calc(a-1, c) - calc(a-1, d) + calc(a-1, lcm_cd)
    n_b = b - calc(b, c) - calc(b, d) + calc(b, lcm_cd)
    print(n_b-n_a)


if __name__ == '__main__':
    main()
import java.util.Scanner;
class Main{
 public static void main(String aegs[]){
  int w,h,i,j;
  Scanner sc = new Scanner(System.in);
  while(true){
   h=sc.nextInt();
   w=sc.nextInt();
   if(h==0 && w==0)
    break;
   for(i=0;i<h;i++){
    for(j=0;j<w;j++)
     System.out.print("#");
   System.out.println();}
   System.out.println();
  }
 }
}


### FIXED CODE ###

while True:
    a,b=map(int,input().split())
    if a==0 and b==0:break
    for i in range (a):
        print('#'*b)
    print()
a,b=map(int,input().split())
for i in range(100):
  if(i//12.5==a and i//10==b):
    print(i)
  else:
    print("-1")

### FIXED CODE ###

s=input()
if(s.count('A')==0 or s.count('B')==0):
  print("No")
else:
  print("Yes")
N = int(input())
s =input().split()

cnt = 0
flag = -1
a = 0
for i in range(0,len(s)):

    if i+1 == int(s[i]):
        continue
    else:
       s.pop(i)
       cnt = cnt + 1
       flag = 1
       a = a + 1

if flag == 1:
    print(cnt)
else:
    print(flag)



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
k = 0
for a in A:
    if k+1==a:
        k+=1
print(-1 if k==0 else N-k)
A, B = map(int, input().split())

if A > B:
    print('GREATER')
elif A < B:
    print('LESS')
else:
    print('EQUAL')

### FIXED CODE ###

A = int(input())
B = int(input())

if A > B:
    print('GREATER')
elif A < B:
    print('LESS')
else:
    print('EQUAL')
n = int(input())
lst = list(map(int,input().split()))
mod = 10**9 + 7

col_lst = [0 , 0 , 0]
ans = 1

for i in range(n):
    tmp = lst[i]
    val = col_lst.count(tmp)
    ans = (ans * val) % mod
    col_lst[col_lst.index(tmp)] += 1
print(ans % mod)

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
mod = 10**9 + 7

col_lst = [0 , 0 , 0]
ans = 1

for i in range(n):
    tmp = lst[i]
    val = col_lst.count(tmp)
    if val == 0:
        print(0)
        exit()
    else:
        ans = (ans * val) % mod
        col_lst[col_lst.index(tmp)] += 1
print(ans % mod)
N = int(input())
A = list(map(int, input().split()))

dp = [[[0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


one = A.count(1)
two = A.count(2)
three = A.count(3)

for k in range(three + 1):
    for j in range(two + three + 1 - k):
        for i in range(one + two + three + 1 -k -j):
            if i == 0 and j == 0 and k == 0:
                continue
            ret = 0
            if i > 0:
                ret += dp[i - 1][j][k] * i
            if j > 0:
                ret += dp[i + 1][j - 1][k] * j 
            if k > 0:
                ret += dp[i], [j + 1], [k -1] * k

            ret += N
            ret *= 1.0 / (i + j + k)
            dp[i][j][k] = ret

print(dp[one][two][three])



### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    dp = [[[0.0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N * 1.0
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

                dp[i][j][k] = ret / (i + j + k)

    print(dp[one][two][three])

main()
from fractions import gcd
N, M = map(int, input().split())
a = list(map(int, input().split()))
k = a[0]
for i in range(1, N):
    k = (a[i]*k) // gcd(a[i], k)
ans = (M+(0.5*k)) // k

print(int(ans))


### FIXED CODE ###

from fractions import gcd
N, M = map(int, input().split())
a = list(map(int, input().split()))
k = a[0]
for i in range(1, N):
    k = (a[i]*k) // gcd(a[i], k)
    if k > M*2:
        print(0)
        exit(0)
    k = int(k)
ans = (M - (k // 2)) // k

if M >= (k // 2):
    flag = True
    for i in range(N):
        if (k // a[i]) % 2 == 0:
            print(0)
            exit(0)
    if flag:
        ans += 1

print(int(ans))
s = list(input())
t = list(input())
ans = ["UNRESTORABLE"]
for i in range(len(s)):
    if s[i] != "?":
        for j in reversed(range(len(t))):
            if t[j] == s[i]:
                f = True
                for k in range(len(t)):
                    if not 0 <= i - j + k < len(t):
                        f = False
                        break
                    f %= (s[i - j + k] == "?" or s[i - j + k] == t[k])
                if f:
                    ans = s.copy()
                    for l in range(len(t)):
                        ans[i - j + l] = t[l]


print("".join(ans).replace("?", "a"))


### FIXED CODE ###

s = list(input())
t = list(input())
ls = len(s)
lt = len(t)
ans = ["UNRESTORABLE"]

if "?" not in set(s):
    print("".join(s))
    exit()

for i in range(ls-lt+1):
    f = True
    for j in range(lt):
        f &= (s[i + j] == "?" or s[i + j] == t[j])

    if f:
        ans = s.copy()
        for j in range(lt):
            ans[i+j] = t[j]


print("".join(ans).replace("?", "a"))
N, M = map(int, input().split())

if N == 1:
    print(M)
else:
    ans = 1
    for g in range(1, int(M ** 0.5) + 1):
        if M % g == 0 and M / g >= N:
            ans = g
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
ans = 1
if N == 1:
    print(M)
else:
    for n in range(2, int(M ** 0.5) + 1):
        if M % n == 0 and M / N >= n:
            ans = max(ans, n)
            if M // n * N <= M:
                ans = max(ans, M // n)
    print(ans)
N = int(input())
H = tuple(map(int, input().split()))

dp = [0, abs(H[1]-H[0])]

if N > 2:
    for i in range(2, N):
        dp[i] = min(dp[i-2] + abs(H[i]-H[i-2]), dp[i-1] + abs(H[i]-H[i-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])


### FIXED CODE ###

N = int(input())
H = tuple(map(int, input().split()))

dp = [0] * N
dp[1] = abs(H[1]-H[0])
if N > 2:
    for i in range(2, N):
        dp[i] = min(dp[i-2] + abs(H[i]-H[i-2]), dp[i-1] + abs(H[i]-H[i-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])
suit = {"S": 0, "H": 1, "C": 2, "D": 3}
suit_keys = list(suit.keys())
deck = [[suit_keys[i] + " " + str(j + 1) for j in range(13)] for i in range(4)]
for _ in range(int(input())):
    card = input().split()
    del deck[suit[card[0]]][int(card[1]) - 1]
for i in range(4):
    for j in deck[i]:
        print(j)



### FIXED CODE ###

suit = {"S": 0, "H": 1, "C": 2, "D": 3}
suit_keys = list(suit.keys())
deck = [[suit_keys[i] + " " + str(j + 1) for j in range(13)] for i in range(4)]
for _ in range(int(input())):
    card = input().split()
    deck[suit[card[0]]][int(card[1]) - 1] = ""
for i in range(4):
    for j in range(13):
        if deck[i][j] != "":
            print(deck[i][j])
n=int(input())
a=list(map(int,input().split()))
count=0
for i in a:
  if i%2==0:
    count+=1
  if i%2==0 and i%3!=0 and i%5!=0:
    print('DENIED')
if count=0:
  print('DENIED')
else:
  print('APPROVED')

    


### FIXED CODE ###

n=int(input())
ans='APPROVED'
a=list(map(int,input().split()))
for x in a:
  if x%2==0:
    if x%3!=0 and x%5!=0:
      ans='DENIED'
      break
print(ans)
N = int(input())
A = map(int, input().split())

a = list(filter(lambda i: i%3 != 0 and i%5 != 0 and i % 2 == 0, A)))
print("APPROVED" if len(a) == 0 else "DENIED")

### FIXED CODE ###

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

a = list(filter(lambda i: i%3 != 0 and i%5 != 0, filter(lambda i: i % 2 == 0, A)))
print("APPROVED" if len(a) == 0 else "DENIED")
# 暴力即可
# 範囲指定 A=100 B=-100で20000000000とかになるしどっちも|100|程度でいいのではないか
x = int(input())
for a in range(-100, 101):
    for b in range(-100, 101):
        if a**5 - b**5 == x:
            print(a, b)
            exit()
print(3 / 0)  # はい


### FIXED CODE ###

# 暴力即可
# 範囲指定 A=100 B=-100で20000000000とかになるしどっちも|100|程度でいいのではないか
# なんか足りんみたい（なんで？）なので4X^2<=10^9なる最大のXを求めよう
# 2X = 1000ちょい だから500くらいあればいいのか
# 1000^2なので時間的には間に合いそう
x = int(input())
for a in range(-500, 501):
    for b in range(-500, 501):
        if a**5 - b**5 == x:
            print(a, b)
            exit()
print(3 / 0)  # はい
import numpy as np
Flg = "No"
A = [[0]*3]*3
b = [0]*N
for i in range(3):
    A[i][0], A[i][1], A[i][2] = map(int, input().split())    
N = int(input())
for j in range(N):
    b[j] = int(input())
    
for i in range(3):
    for j in range(3):
        for k in range(N):
            if(A[i][j] == b[k]):
                A[i][j] = 0
A_T = np.array(A).T
                
for i in range(3):
    if(A[i][0] == A[i][1] == A[i][2] == 0):
        Flg = "Yes"        
        break
    if(A_T[i][0] == A_T[i][1] == A_T[i][2] == 0):
        Flg = "Yes"
        break

if(A[0][0] == A[1][1] == A[2][2] == 0):
    Flg = "Yes"

print(Flg)

### FIXED CODE ###

import numpy as np
Flg = "No"
A = [[0]*3 for i in range(3)]
for i in range(3):
    A[i][0], A[i][1], A[i][2] = map(int, input().split())    
N = int(input())
b = [0]*N
for j in range(N):
    b[j] = int(input())

for i in range(3):
    for j in range(3):
        for k in range(N):
            if(A[i][j] == b[k]):
                A[i][j] = "*"
A_T = np.array(A).T
                
for i in range(3):
    if(A[i][0] == A[i][1] == A[i][2] == "*"):
        Flg = "Yes"        
        break
    if(A_T[i][0] == A_T[i][1] == A_T[i][2] == "*"):
        Flg = "Yes"
        break

if(A[0][0] == A[1][1] == A[2][2] == "*"):
    Flg = "Yes"

if(A[0][2] == A[1][1] == A[2][0] == "*"):
    Flg = "Yes"

print(Flg)
N = int(input())
input_list = sorted([int(i) for i in input().split()])

mod = 10 ** 9 + 7

if N = 1 and input_list[0] == 0:
    print(1)
else:
    if N % 2 == 1:
        if input_list[0] != 0:
            print(0)
        else:
            flag = 2
            limit = (N - 1) // 2
            for i in range(1, limit, 2):
                if input_list[i] == flag and input_list[i+1] == flag:
                    flag += 2
                    if i == limit-1:
                        print((2**limit) % mod)
                else:
                    print(0)
                    break
    elif N % 2 == 0:
        flag = 1
        limit = N // 2
        for i in range(0, limit, 2):
            if input_list[i] == flag and input_list[i+1] == flag:
                flag += 2
                if i == limit-2:
                    print((2**limit) % mod)
            else:
                print(0)
                break

### FIXED CODE ###

N = int(input())
input_list = sorted([int(i) for i in input().split()])

mod = 10 ** 9 + 7

if N % 2 == 1:
    if input_list[0] != 0:
        print(0)
    else:
        if N == 1:
            print(1)
        flag = 2
        limit = (N - 1) // 2
        for i in range(1, limit, 2):
            if input_list[i] == flag and input_list[i+1] == flag:
                flag += 2
                if i == limit-1:
                    print((2**limit) % mod)
            else:
                print(0)
                break
elif N % 2 == 0:
    flag = 1
    limit = N
    for i in range(0, limit, 2):
        if input_list[i] == flag and input_list[i+1] == flag:
            flag += 2
            if i == limit-2:
                print((2**(N//2)) % mod)
                break
        else:
            print(0)
            break
def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 0:
        print(n_pow(2, count[0]) + n_pow(2, count[1] - 1))
    else:
        print(n_pow(2, count[0] + count[1] - 1, 0))


if __name__ == '__main__':
    main()



### FIXED CODE ###

def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 1 and count[1] == 0:
        print(0)
    elif count[1] == 0:
        print(pow(2, bags))
    else:
        print(n_pow(2, bags - 1))


if __name__ == '__main__':
    main()
#!/usr/bin/env python3

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

#     ans = [[None] for _ in range(N-1)]

#     def dfs(focus,parent_color):
#         color = 1
#         for child,index in sides[focus]:
#             if parent_color == color:
#                 color += 1 #もし親の色と被っていた場合はその色を飛ばす
#             ans[index] = color
#             if child < N-1:
#                 dfs(child,color)
#             color += 1 #同じ親から続く次の辺の色を変更する

#     dfs(0,0)

#     print(max(ans))
#     for color in ans:
#         print(color)

def main():
    N = int(input())

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

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

    print(max(ans))
    for c in ans:
        print(c)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)

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

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

    print(max(ans))
    for color in ans:
        print(color)


if __name__ == "__main__":
    main()
N = int(input())
A = [int(a) for a in input().split()]

A.sort()
flag = True
for a in A:
    if a > A[0]+1:
        flag = False

if flag:
    cnt = A.count(A[0])
    if cnt == N and (A[0] == N-1 or A[0]*2 <= N):
        ans = "Yes"
    elif cnt == A[0] and cnt < N-1:
        ans = "Yes"
    else:
        ans = "No"
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

A.sort()
flag = True
for a in A:
    if a > A[0]+1:
        flag = False

ans = "No"
if flag:
    cnt = A.count(A[0])
    if cnt == N and (A[0] == N-1 or A[0]*2 <= N):
        ans = "Yes"
    elif cnt == A[0] and cnt < N-1:
        ans = "Yes"
    elif cnt < A[0] and N-cnt >= 2*(A[0]-cnt+1):
        ans = "Yes"
        
print(ans)
N = []
for n in range (3):
    n = int(input())
if n == 7:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

num = int(input())
N = [int(i) for i in str(num)]
if N[0] == 7:
    print("Yes")
elif N[1] == 7:
    print("Yes")
elif N[2] == 7:
    print("Yes")
else:
    print("No")