Harryxun/stf_run huggingface dataset:
import statistics
import math
# N = int( input())

MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if S[i] == "C":
        dp[i + 1][0] += (dp[i][0])
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += (dp[i][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for j in range(0,4):
        dp[i + 1][j] %= MOD




print(dp[-1][3] % MOD)

### FIXED CODE ###

import math
# N = int( input())

MOD = (10 ** 9) + 7
S = input()
dp = [ [ 0 for _ in range(4)]  for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S) ):
    if S[i] == "A":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += (dp[i][0] + dp[i][1])
        dp[i + 1][2] += (dp[i][2])
        dp[i + 1][3] += dp[i][3]
    if S[i] == "B":
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] +=dp[i][1]
        dp[i + 1][2] +=  (dp[i][1] + dp[i][2])
        dp[i + 1][3] +=dp[i][3]

    if S[i] == "C":
        dp[i + 1][0] += (dp[i][0])
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += (dp[i][2] + dp[i][3])

    if S[i] == "?":
        dp[i + 1][0] +=  (dp[i][0] * 3)
        dp[i + 1][1] += (dp[i][0] + (dp[i][1]) * 3)
        dp[i + 1][2] += (dp[i][1]+ (dp[i][2]) * 3)
        dp[i + 1][3] += (dp[i][2]+ (dp[i][3]) * 3)
    for j in range(0,4):
        dp[i + 1][j] %= MOD




print(dp[-1][3] % MOD)
N = int(input())
X = list(map(int, input().split()))

# _sum = sum(X)
buff_x = X.copy()


X.sort()
mm = X[N//2-1]
mx = X[N//2]
for i in range(N):
    if buff_x[i] < mx:
        print(mx)
    else:
        print(mm)

### FIXED CODE ###

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

# _sum = sum(X)
buff_x = X.copy()


X.sort()
mm = X[N//2-1]
mx = X[N//2]
for i in range(N):
    if buff_x[i] < mx:
        print(mx)
    else:
        print(mm)
N, *p = map(int, open(0).read().split())

if sum(p[i] != i + 1 for i in range(N)) <= 2:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    if len(str(i))%2==1:
        ans+=1
print(ans)
s = input()
t = input()
flag = False
tq = '?'*len(t)
start = []
for i in range(len(s)-len(t)+1):
    if s[i] == t[0]:
        start.append(i)
        flag = True
        for j in range(len(t)):
            if s[i+j] == t[j] or s[i+j] == '?':
                continue
            else:
                flag = False
                start.pop[-1]
    if s[i:i+len(t)] == tq:
        start.append(i)
        flag = True
stal = []
if flag:
    for i in start:
        stal.append(s[:i].replace('?','a') + t + s[i+len(t):].replace('?','a'))
    stal.sort()
    print(stal[0])
else:
    print('UNRESTORABLE')

### FIXED CODE ###

s = input()
t = input()
flag = False
tq = '?'*len(t)
start = []
for i in range(len(s)-len(t)+1):
    flag = True
    for j in range(len(t)):
        if s[i+j] == t[j] or s[i+j] == '?':
            continue
        else:
            flag = False
            break
    if flag:
        start.append(i)
    
stal = []
if start:
    for i in start:
        stal.append(s[:i].replace('?','a') + t + s[i+len(t):].replace('?','a'))
    stal.sort()
    print(stal[0])
else:
    print('UNRESTORABLE')
N=int(input())
for i in reversed(range(int(N**0.5))):
    if N % i == 0:
        a=i
        break
print(int(a+(N/a)-2))

### FIXED CODE ###

N=int(input())
for i in reversed(range(int(N**0.5)+1)):
    if N % i == 0:
        print(int(i+N//i-2))
        break
a = int(input())
b = int(input())
if a == b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N,M = map(int, input().split())
 
if N == M:
  print("Yes")
else:
  print("No")
K, X = map(int, input().split())
for i in range(X - K + 1, X + K):
if i < X + K - 1:
print(i, end=' ')
else:
print(i)


### FIXED CODE ###

K, X = map(int, input().split())
for i in range(X - K + 1, X + K):
  if i < X + K - 1:
    print(i, end=' ')
  else:
    print(i)
str = input()

flag = False
for i in range(len(str)) - 1:
  if str[i] == str[i+1]:
    flag = True

print("Bad") if flag else print("Good")

### FIXED CODE ###

str = input()

flag = False
for i in range(len(str) - 1):
  if str[i] == str[i+1]:
    flag = True

print("Bad") if flag else print("Good")
try:
    while True:
        result = result2 = count = 0
        a, b = map(int, input().split(','))
        result += a*b
        result2 += b
        count += 1
except:
    print(result,"{0:.1f}".format(result2/count))

### FIXED CODE ###

try:
    result = result2 = count = 0
    while True:
        a, b = map(int, input().split(','))
        result += a*b
        result2 += b
        count += 1
except:
    print(result)
    print(round(result2/count+0.5))
i = int(input())

if i/3600 != 0:
    h = i/3600
    i = i - 3600 * h
if i/60 != 0:
    m = i/3600
    i = i - 60 * m

print(h,":",m,":",a)


### FIXED CODE ###

i = int(input())

h = 0
m = 0

if i/3600 >= 1:
    h = int(i/3600)
    i = i - 3600 * h
if i/60 >= 1:
    m = int(i/60)
    i = i - 60 * m
    
s = str(h) + ":" + str(m) + ":" + str(i)

print(s)
N, row = input().split()
unit1, unit2 = row[:len(row)//2], row[len(row)//2:]
if unit1 == unit2:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N = input()
row = input()
unit1, unit2 = row[:len(row)//2], row[len(row)//2:]
if unit1 == unit2:
    print('Yes')
else:
    print('No')
N=int(input())
if(N<105):
  print(0)
elif(105<=N<165):
  print(1)
elif(165<=N<195):
  print(2)
else:
  print(3)

### FIXED CODE ###

A,B=map(int,input().split())
print((A-1)*(B-1))
s=input()
n=len(s)
if s=="hi"*(n//2):
  print("Yes")
else:
  print("No")



### FIXED CODE ###

s=input()
n=len(s)
if s=="hi"*(n//2):
  print("Yes")
else:
  print("No")
s = input()
    res = "AC"
    for i in s:
        if (i!="A" and i!="C" and i.isupper() == True):
            res = "WA"
            break;

    if (res == "AC" and s[0]=="A" and s.count("C")==1 and  s.index("C")>1 and s.index("C")<len(s)-1 ):
        print("AC")
    else:
        print("WA")

### FIXED CODE ###

s = input()
f = False
f2 = True
c = 0
if s[0] =="A":
    f = True
for x in s[2:len(s)-1]:
    if x == "C":
        c +=1
    else:
        if x.isupper() or s[-1].isupper():
            f2 = False
if not s[1].islower():
    f2 = False
if f and c == 1 and f2:
    print("AC")
else:
    print("WA")
N, x = map(int, input().split())
A = list(map(int, input().split()))
s = 0
for i in range(N - 1):
  s = A[i] + A[i + 1] - x
  ans += max(0, s)
  if s > 0:
    if s <= A[i + 1]:
      A[i + 1] -= s
    else:
      A[i + 1] = 0
print(ans)


### FIXED CODE ###

N, x = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N - 1):
  s = A[i] + A[i + 1] - x
  ans += max(0, s)
  if s > 0:
    if s <= A[i + 1]:
      A[i + 1] -= s
    else:
      A[i + 1] = 0
print(ans)
N,K=map(int,input().split())
c=[0,0,0]
for _ in range(K):
    d=int(input())
    l=list(map(int,input().split()))
    for i in range(d):
        c[l[i]-1]+=1
print(c.count(0))

### FIXED CODE ###

N,K=map(int,input().split())
c=[0]*N
for _ in range(K):
    d=int(input())
    l=list(map(int,input().split()))
    for i in range(d):
        c[l[i]-1]+=1
print(c.count(0))
import sys
for s in sys.stdin:
    s1=s.split(",")
    n=int(s1[0])
    h,w=map(float(s[1:]))
    bmi=w/h^2
    if bmi>=25: print n

### FIXED CODE ###

import sys
for s in sys.stdin:
    n,w,h = map(float, s.split(","))
    if w / h**2 >= 25: print int(n)
import copy

n = int(input())
natural = [int(i) for i in input().split()]
sortedlist = natural.sorted()

sum = 0

for i in range(n):
  removed = copy.deepcopy(sortedlist).remove(natural[i])
  for j in range(n-1):
    if j == 0:
      sum += abs(removed[j])
    else:
      sum += abs(removed[j]-removed[j-1])
  print(sum)

### FIXED CODE ###

n = int(input())
sortedlist = [int(i) for i in input().split()]
anslist = []

longest = 0
ans = 0

for i in range(n+1):
  if i==0:
    longest += abs(sortedlist[0]-0)
  elif i==n:
    longest += abs(0-sortedlist[n-1])
  else:
    longest += abs(sortedlist[i]-sortedlist[i-1])

    
for i in range(n):
  if i==0:
    ans = longest - abs(sortedlist[0]) - abs(sortedlist[1]-sortedlist[0]) + abs(sortedlist[1])
  elif i==n-1:
    ans = longest - abs(sortedlist[n-1]) - abs(sortedlist[n-1]-sortedlist[n-2]) + abs(sortedlist[n-2])
  else:
    ans = longest - abs(sortedlist[i]-sortedlist[i-1])-abs(sortedlist[i+1]-sortedlist[i]) + abs(sortedlist[i+1]-sortedlist[i-1])
  print(ans)
n.k = map(int,input().split())
P = list(map(int,input().split()))
ans = 0
import itertools
import math
cnt_nPk = math.factorial(n)/math.factorial(k)
P_nPk = list(itertools.permutations(n,k))

sum_P_nPk = sum(P_nPk)

print(sum_P_nPk / cnt_nPk)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    tmp_max = sum(P[:K])
    tmp = sum(P[:K])
    for i in range(N-K):
        tmp += P[i+K]
        tmp -= P[i]

        if tmp > tmp_max:
            tmp_max = tmp

    print((tmp_max + K) / 2)

main()
a,b,c = map(int,input().split())
if a==b+c:
    print("YES")
elif b==a+c:
    print("YES")
elif c=a+b:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a,b,c = map(int,input().split())
if a==b+c:
    print("Yes")
elif b==a+c:
    print("Yes")
elif c==a+b:
    print("Yes")
else:
    print("No")
S = input()
T = input()

import sys

j = 0
flag = 0
check = 0

while j < len(S):
    flag = S.find(T[0],j)
    if flag != -1:
        for i in range(len(T)-1):
            if S[flag+1+i] == '?' or S[flag+1+i] == T[i+1]:
                check += 1
        if check == len(T)-1:
            Snew = S[:flag] + T + S[flag+len(T):]
            break
        else:
            check = 0
            j = flag + len(T)
    else:
        print('UNRESTORABLE')
        sys.exit()
            
for i in range(len(S)):
    if Snew[i] == '?':
        print('a', end="")
    else:
        print(Snew[i], end="")

### FIXED CODE ###

S = input()
T = input()
S2 = S.replace('?','a')
ans = []

for i in range(len(S)-len(T)+1):
    S_sub = S[i:i+len(T)]
    
    check = True
    
    for s,t in zip(S_sub,T):
        if s != t and s == '?':
            continue
        elif s == t:
            continue
        elif s != t and s != '?':
            check = False
            break
        
    if check == True:
        tmp = S2[:i] + T + S2[i+len(T):]
        ans.append(tmp)
        
if len(ans) != 0:
    answer = sorted(ans)[0]
else:
    answer = 'UNRESTORABLE'
    
print(answer)
A,B,N = map(int,input().split())
x = 0
a = 0
while x <= B-1:
  if x%B != 0 and a < A*x//B - A*(x//B):
    a = A*x//B - A*(x//B)
    x -= 1
  else:
    x -= 1
print(a)


### FIXED CODE ###

K = int(input())
A,B = map(int,input().split())
i=1
while i<=B:
  if K*i>=A and K*i<=B:
    print("OK")
    break
  else:
    i += 1
if i == B+1:
  print("NG")
n = int(input())
*A, = map(int, input().split())
m = max(A)
C = [0 for a in range(m + 1)]
for a in A:
    C[a] += 1
s = max(sum(C[a::a]) for a in range(2, m + 1))
if s < 2:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())

m = max(A)
is_prime = [True] * (m + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, m + 1):
    for j in range(i * 2, m + 1, i):
        is_prime[j] = False
primes = [i for i in range(m + 1) if is_prime[i]]

Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] += 1

# Pmap[p]はAにでてくるpの倍数の数
Pmap = {p: 0 for p in primes}
for p in primes:
    for a in range(p, m + 1, p):
        Pmap[p] += Amap[a]

try:
    score = max(Pmap.values())
except BaseException:
    print('pairwise coprime')
    exit()
if score == 1:
    print('pairwise coprime')
elif score != n:
    print('setwise coprime')
else:
    print('not coprime')
from sys import stdin
import numpy as np

def bit_search(a, n, m, x):
    min_price = np.inf
    for i in range(2 ** n):
        price = 0
        skill = np.zeros((n, m))
        for j in range(n):
            if (i >> j) & 1:
                price += a[j][0]
                skill[j] = a[j][1:]
        skill_sum = np.sum(skill, axis=0)\
                        if skill.shape[0] > 1 else np_skill
        if not (skill_sum >= x).all() or price > min_price: continue
        min_price = price
    return min_price

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    min_price = bit_search(a, n, m, x)
    return print('-1' if np.isinf(min_price) else min_price)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import numpy as np

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    res = []
    for i in range(2 ** n):
        price = 0
        skill = []

        for j in range(n):
            if ((i >> j) & 1):
                price += a[j][0]
                skill.append(a[j][1:])
        np_skill = np.array(skill)
        skill_sum = np.sum(np_skill, axis=0)\
                        if np_skill.shape[0] > 1 else np_skill

        if skill_sum.size != 0 and (skill_sum >= x).all():
            res.append(price)

    if not res: return print('-1')

    return print(min(res))

if __name__ == '__main__':
    main()
import math

a, b, c, d = map(int, input().split())
lcm_cd = (c * d) // math.gcd(c, d)
total = b - a + 1
d_c = b // c - (a - 1) // c
d_d = b // d - (a - 1) // d
d_cd = b // lcm_cd - (a - 1) // lcm_cd
print(int(total - (d_c + d_d - d_cd)))

### FIXED CODE ###

import fractions

a, b, c, d = map(int, input().split())
lcm_cd = (c * d) // fractions.gcd(c, d)
total = b - a + 1
d_c = b // c - (a - 1) // c
d_d = b // d - (a - 1) // d
d_cd = b // lcm_cd - (a - 1) // lcm_cd
print(int(total - (d_c + d_d - d_cd)))
x,y = map(int, input().split())
ans='No'
if x,y in [2]:
  if y in [2]:
    ans='Yes'
if x in [4,6,9,11]:
  if y in [4,6,9,11]:
    ans='Yes'
if x in [1,3,5,7,8,10,12]:
  if y in [1,3,5,7,8,10,12]:
    ans='Yes'
print(ans)

### FIXED CODE ###

x,y = map(int, input().split())
ans='No'
if x in [2]:
  if y in [2]:
    ans='Yes'
if x in [4,6,9,11]:
  if y in [4,6,9,11]:
    ans='Yes'
if x in [1,3,5,7,8,10,12]:
  if y in [1,3,5,7,8,10,12]:
    ans='Yes'
print(ans)
N,K = map(int, input().split())
L = []
for i in range(N):
  d = int(input())
  A = list(map(int, input().split()))
  for j in range(d):
    L.append(A[j])
print(N-len(set(L)))

### FIXED CODE ###

N,K = map(int, input().split())
L = []
for i in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for j in range(d):
    L.append(A[j])
print(N-len(set(L)))
N,M = map(int,input().split())
a=[]
for i in range(N):
  x = input().split()
  z = x[1:]
  a += list(map(int,z))
cnt=0
for k in range(1:M+1):
  n = a.count(k)
  if n==N:
    cnt +=1
print(cnt)
    
  
    
    
       
    


### FIXED CODE ###

N,M = map(int,input().split())
a=[]
for i in range(N):
  x = input().split()
  z = x[1:]
  a += list(map(int,z))
cnt=0
for k in range(1,M+1):
  n = a.count(k)
  if n==N:
    cnt +=1
  else:
    cnt = cnt
print(cnt)
x,y = map(int,input().split())
ans = 10000000000
for a,b,c in [(x,y,0)(x,-y,1)(-x,y,1)(-x,-y,2)]:
    if a < b:
        ans = min(ans,b-a+c)
print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
ans = 10000000000
for a,b,c in [(x,y,0),(x,-y,1),(-x,y,1),(-x,-y,2)]:
    if a <= b:
        ans = min(ans,b-a+c)
print(ans)
X,Y,Z = map(int,input().split())
 
print({} {} {} .format(Y,Z,X))

### FIXED CODE ###

X,Y,Z = map(int,input().split())
 
print('{} {} {} '.format(Z,X,Y))
a,b=map(int,input().split())
grid=[["."]*(a+2)]+[list("."+input()+".")for i in range(b)]+[["."]*(a+2)]
for s in range(1,1+a):
    for t in range(1,1+a):
        if grid[s][t]=="#" and all([grid[s+x][t+y]=="."for x,y in ([0,-1],[0,1],[1,0],[-1,0])]):
            print("No")
            exit()
print("Yes")

### FIXED CODE ###

h,w=map(int,input().split())
grid=[["."]*(w+2)]+[list("."+input()+".")for i in range(h)]+[["."]*(w+2)]
for s in range(1,1+h):
    for t in range(1,1+w):
        if grid[s][t]=="#" and all([grid[s+x][t+y]=="."for x,y in ([0,-1],[0,1],[1,0],[-1,0])]):
            print("No")
            exit()
print("Yes")
import math

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

def calc(n):
    return n-n//c-n//d+n//(c*d//math.gcd(c, d))


print(calc(b)-calc(a-1))


### FIXED CODE ###

import fractions

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

def calc(n):
    return n-n//c-n//d+n//(c*d//fractions.gcd(c, d))

print(calc(b)-calc(a-1))
a,b=map(int,input().split())
if(a==b):
  print("Draw")
elif(a<b):
  if(a==1):
    print("Alice")
  else:
    print("Bob")
else:
  if(b==1):
    print("Alice")
  else:
	print("Bob")


### FIXED CODE ###

a,b=map(int,input().split())
if(a==b):
  print("Draw")
elif(a<b):
  if(a==1):
    print("Alice")
  else:
    print("Bob")
else:
  if(b==1):
    print("Bob")
  else:
    print("Alice")
# GCD on Blackboard
"""
リストのどの要素を抜いた時に最大公約数が最大値をとるか調べて、
その時の最大公約数を出力する。
"""

from functools import reduce

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


def get_gcd(a, b):
    """
    ユークリッド互除法により最大公約数を求める。
    """
    if a < b:
        a, b = b, a

    elif a % b == 0:
        return b

    return get_gcd(b, a % b)


def get_gcd_l(l):
    """
    リストの要素の最大公約数を求める。
    """
    return reduce(get_gcd, l)


def answer(l):
    """
    どの要素を抜いた時に最大公約数が最大値をとるか調べる。
    """
    len_l = len(l)
    answers = []  # 答えの案

    for i in range(len_l): # 要素を1個ずつ消してみる。
        temp_l = []
        temp_l += l[0 : i]
        temp_l += l[i+1 : len_l]
        answers.append(get_gcd_l(temp_l))
    ans = max(answers)
    return ans


def main():
    """
    答えを出力する。
    """
    print(answer(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#Biscuit Generator

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

def answer():
    ans = T // A * B
    return ans

def main():
    print(answer())


if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [[-10**18]*3 for _ in range(N)]
dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][2] = A[2]

for i in range(2, N):
    dp[i][0] = dp[i-2][0]+A[i]
    dp[i][1] = max(dp[i][1], dp[i-2][1]+A[i])
    
    if i>=3:
        dp[i][1] = max(dp[i][1], dp[i-3][0]+A[i])
    
    dp[i][2] = max(dp[i][2], dp[i-2][2]+A[i])
    
    if i>=3:
        dp[i][2] = max(dp[i][2], dp[i-3][1]+A[i])
    
    if i>=4:
        dp[i][2] = max(dp[i][2], dp[i-4][0]+A[i])

if N%2==0:
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))

### FIXED CODE ###

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

if N%2==0:
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
    
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    dp = [[0]*3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        elif i==3:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-2][1]+A[i], dp[i-3][0]+A[i])
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
            dp[i][2] = max(dp[i-4][0]+A[i], dp[i-3][1]+A[i], dp[i-2][2]+A[i])
    
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))
#!/usr/bin/env python3
import sys
import statistics
import collections

def solve(n: int, v: "List[int]"):
    half_length = len(v) // 2
    O = [v[i] for i in range(1, n, 2)]
    E = [v[i] for i in range(0, n, 2)]

    co = list(collections.Counter(O).most_common())
    ce = list(collections.Counter(E).most_common())
    o1 = co[0][0]
    e1 = ce[0][0]

    O_ = list(filter(lambda o: o != o1, O))
    E_ = list(filter(lambda e: e != e1, E))
    num_o_1 = len(O_) 
    num_e_1 = len(E_)

    if e1 != o1:
        num = num_o_1 + num_e_1
    else:
        if True and len(co) == 1 and len(ce) == 1:
            num = half_length
        elif len(co) == 1:
            e2 = ce[1][0]
            num_e_2 = len(list(filter(lambda e: e != e2, E)))
            num = num_o_1 + num_e_2
        elif len(ce) == 1:
            o2 = co[1][0]
            num_o_2 = len(list(filter(lambda o: o != o2, O)))
            num = num_o_2 + num_e_1
        else:
            e2 = ce[1][0]
            o2 = co[1][0]
            num = min(num_o_1 + num_e_2, num_o_2 + num_e_1)
    num = 0
    print(num)
    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
    v = [ int(next(tokens)) for _ in range(n) ]  # type: "List[int]"
    solve(n, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import statistics
import collections

def solve(n: int, v: "List[int]"):
    half_length = len(v) // 2
    O = [v[i] for i in range(1, n, 2)]
    E = [v[i] for i in range(0, n, 2)]

    co = list(collections.Counter(O).most_common())
    ce = list(collections.Counter(E).most_common())
    o1 = co[0][0]
    e1 = ce[0][0]

    O_ = list(filter(lambda o: o != o1, O))
    E_ = list(filter(lambda e: e != e1, E))
    num_o_1 = len(O_) 
    num_e_1 = len(E_)

    num = 0
    if e1 != o1:
        num = num_o_1 + num_e_1
    else:
        if len(co) == 1 and len(ce) == 1:
            num = half_length
        elif len(co) == 1:
            e2 = ce[1][0]
            num_e_2 = len(list(filter(lambda e: e != e2, E)))
            num = num_o_1 + num_e_2
        elif len(ce) == 1:
            o2 = co[1][0]
            num_o_2 = len(list(filter(lambda o: o != o2, O)))
            num = num_o_2 + num_e_1
        else:
            e2 = ce[1][0]
            o2 = co[1][0]
            num_e_2 = len(list(filter(lambda e: e != e2, E)))
            num_o_2 = len(list(filter(lambda o: o != o2, O)))
            num = min(num_o_1 + num_e_2, num_o_2 + num_e_1)
    print(num)
    return

def len2(l):
    n = 0
    for i in l:
        n += 1
    return n

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

if __name__ == '__main__':
    main()
N = int(input())

def dfs(v, c, p):
    k = 1
    for _v, _id in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

V = [[] for _ in range(N)]
C = [-1 for _ in range(N-1)]

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

dfs(0, -1, -1)
print(max(C))
for i in range(N-1):
    print(C[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())

V = [[] for _ in range(N)]
C = [-1 for _ in range(N - 1)]


# v:頂点, c:色, p:親
def dfs(v, c, p):
    k = 1
    for _v, _id  in V[v]:
        if _v == p:
            continue
        if k == c:
            k += 1
        C[_id] = k
        dfs(_v, k, v)
        k += 1

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    V[a].append([b, i])
    V[b].append([a, i])
#print(V)
dfs(0, -1, -1)
print(max(C))
for i in C:
    print(i)