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

N = int(input())
a = list(map(int, input().split()))
dp = [[0, 0, 0] for _ in range(N+3)]

for i, x in enumerate(a, start=3):
    dp[i][2] = max(dp[i-2][0], x+dp[i-2][2], x+dp[i-3][1])
    dp[i][1] = max(x+dp[i-2][1], x+dp[i-3][0])
    dp[i][0] = x + dp[i-2][0]

if N & 1 == 0:
    print(max(
        dp[N+2][0],
        dp[N+2][1],
        dp[N+1][0]
    ))
else:
    print(max(
        dp[N+2][1],
        dp[N+2][2],
        dp[N+1][0],
        dp[N+1][1]
    ))


### FIXED CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import sqrt

def prime_division(x):
    q = int(sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z): # z : output of prime_division
    #ddprint(f"dvl {z}")
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
d = [0]*(k+1)
d[1] = pow(k,n,R)
sm = 0
for i in range(k,1,-1):
    d[i] = (d[i]+pow(k//i,n,R))
    ps = divisorlist(prime_division(i))
    for p in ps:
        if p!=i:
            d[p] = (d[p]-d[i])%R
    sm = (sm+d[i]*i)%R
#ddprint(d)
print((sm+d[1])%R)
"main.py" 5L, 116C written
def calc_watering_num(h, offset, left, right):
        if left > right:
                return 0
        min_h = None
        min_h_indices = []
        for i in range(left, right + 1):
                if min_h is None or min_h > h[i] - offset:
                        min_h = h[i] - offset
                        min_h_indices = [i]
                elif min_h == h[i] - offset:
                        min_h_indices.append(i)
        if len(min_h_indices) == right - left + 1:
                return min_h
        num = min_h
        prev = left
        for i in min_h_indices:
                num += calc_watering_num(h, offset + min_h, prev, i - 1)
                prev = i + 1
        num += calc_watering_num(h, offset + min_h, prev, right)
        return num


input()
h = [int(v) for v in input().split()]
print(calc_watering_num(h, 0, 0, len(h) - 1))

### FIXED CODE ###

def calc_watering_num(h, offset, left, right):
        if left > right:
                return 0
        min_h = None
        min_h_indices = []
        for i in range(left, right + 1):
                if min_h is None or min_h > h[i] - offset:
                        min_h = h[i] - offset
                        min_h_indices = [i]
                elif min_h == h[i] - offset:
                        min_h_indices.append(i)
        if len(min_h_indices) == right - left + 1:
                return min_h
        num = min_h
        prev = left
        for i in min_h_indices:
                num += calc_watering_num(h, offset + min_h, prev, i - 1)
                prev = i + 1
        num += calc_watering_num(h, offset + min_h, prev, right)
        return num


input()
h = [int(v) for v in input().split()]
print(calc_watering_num(h, 0, 0, len(h) - 1))
print(int(input()) % int(input()))

### FIXED CODE ###

a, b = map(int, input().split())
print(min(a % b, b - (a % b)))
import math
A,B=map(int,input().split())
print(int(A*B/math.gcd(A,B)))

### FIXED CODE ###

A,B=map(int,input().split())
def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
print(int(A*B/gcd(A,B)))
a,b,t = map(int,input().split())
    x = t // a
    y = x * b
    print(y)

### FIXED CODE ###

a,b,t = map(int,input().split())
x = t // a
y = x * b
print(y)
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
for i in range(X, Y):
  if X < i <= Y and max(x) < i <= min(y):
    print("No War")
    exit(1)
print("War")
             


### FIXED CODE ###

N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
for i in range(X, Y+1):
  if X < i <= Y and max(x) < i <= min(y):
    print("No War")
    exit()
print("War")
H, W = map(int, input().split())
result=0
if H==1 or W==1:
    result=1
elif W%2==0:
    result = (W/2)*H
else:
    if H%2==0:
        result=W*(H/2)
    else :
        result=W*(H-1)/2+(W+1)/2
print(str(round(result)))


### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(list[K-1])
N, M = map(int, input().split())
if N == 1:
    print(1) 
    
elif M == 0:
    print(dp[N-1])
    
else:
    dp = [0]*N
    dp[0] = 1
    dp[1] = 2
    for i in range(N-2):
        dp[i+2] = dp[i]+dp[i+1]
        
    a = [int(input()) for _ in range(M)]
    
    for i in range(M-1):
        if a[i+1] == a[i] + 1:
            ans = 0
            break
    else:
        if a[0] == 1:
            ans == 1
        else:
            ans = dp[a[0]-2]
                
    for i in range(M-1):
        if a[i+1]-a[i] >= 3:
            ans *= dp[a[i+1]-a[i]-3]
    if N-a[M-1]-2 >= 0:
        ans *= dp[N-a[M-1]-2] 
    print(ans%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0]*(N+1)
for i in a:
    dp[i] = -1

for i in range(N+1):
    if dp[i] == -1:
        dp[i] = 0
    elif i > 1:
        dp[i] = dp[i-1] + dp[i-2]
    else:
        dp[i] = 1
        
print(dp[N]%1000000007)
a,b=map(int, input().split())
print(max(a+b, a-bm a*b))

### FIXED CODE ###

a,b=map(int, input().split())
print(max(a+b, a-b, a*b))
n,k = map(int,input().split())
h = (list(map(int,input().split())))
ans =[0]*n
for i in range(1, n):
    s = max(i-k, 0)
    ans[i] = min(ans[s:i]+abs(h[s:i]-h[i]))
print(ans[-1])
#copy code

### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,input().split())))
ans = np.zeros(n, dtype=int)
for i in range(1, n):
    s = max(i-k, 0)
    ans[i] = np.min(ans[s:i]+np.abs(h[s:i]-h[i]))
print(ans[-1])
#copy code
#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(100)
h,w=map(int,input().split())

def go_next(I,J):
    global dp,w,h
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])


### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
inputs = [int(x) for x in input().split()]

N = inputs[0]
D = inputs[1]
answer = 0
if N > (D*2) + 1:
  check = N % ((D*2) + 1)
  answer = N / ((D*2) + 1) 
  answer = int(answer)
  if check != 0:
    answer += 1
  
else:
  answer = 1
  
print(answer)

### FIXED CODE ###

r = int(input())
x = 3*(r**2)
print(x)
import sys
input = sys.stdin.readline
from bisect import *
from heapq import *
up=2*10**5
maxi=10**10
kind=[heapify([]) for i in range(up)]

class segtree:
    x_unit=maxi # 要素として入れられる最大値
    x_func=min
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]
            # x_funcに従って値を取得
    def set_val(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)

n,q=map(int, input().split())
shozoku=[-1]*n
rating=[0]*n
for i in range(n):
    a,b=map(int, input().split())
    heappush(kind[b-1],a)
    shozoku[i]=b-1
    rating[i]=a
#print(kind)
seg=segtree(up)
root=[maxi for i in range(up)]

for i in range(up):
    if kind[i]!=[]:
        rate=kind[i][-1]
        root[i]=rate
seg.build(root)

for i in range(q):
    c,d=map(int, input().split())
    c-=1
    d-=1
    if rating[c]==kind[shozoku[c]][-1] and len(kind[shozoku[c]])==1:
        kind[shozoku[c]]=heapify([])
        seg.set_val(shozoku[c], 2<<30)
    elif rating[c]==kind[shozoku[c]][-1]:
        kind[shozoku[c]]=kind[shozoku[c]][:-1]
        seg.set_val(shozoku[c], kind[shozoku[c]][-1])
    else:
        ind=bisect_right(kind[shozoku[c]],rating[c])
        kind[shozoku[c]]=kind[shozoku[c]][:ind-1]+kind[shozoku[c]][ind:]
    heappush(kind[d], rating[c])
    seg.set_val(d, kind[d][-1])
    shozoku[c]=d
    print(seg.x[1])


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A=sorted(A)
up=max(A)
table=[0]*(up+1)
for i in range(n):
    table[A[i]]+=1
aset=set(A)

for i in range(len(aset)):
    if table[A[i]]>0:
        j=2
        while A[i]*j<up+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)
def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))

    s=input()+"T"

    N=len(s)
    x,y=MI()

    F=[[],[]]

    temp=0
    bit=0
    for i in range(N):
        if s[i]=="F":
            temp+=1
        else:
            if temp!=0:
                F[bit].append(temp)
            bit=(bit+1)%2
            temp=0

    Nx=len(F[0])
    Ny=len(F[1])


    #i番目の文字で，位置x [-N~N]につけるかどうか
    dpx=[[False]*(2*N+3) for _ in range(2)]
    dpy=[[False]*(2*N+3) for _ in range(2)]

    dpx[0][N]=True
    if Nx>=1:
        dpx[0][N]=False
        dpx[0][N+F[0][0]]=True
        if s[0]=="T":
            dpx[1][N-F[0][0]]=True
    dpy[0][N]=True

    MA=F[0][0]+1

    for i in range(1,Nx):
        MA+=F[0][i]
        for j in range(N-MA,N+MA):
            if dpx[(i+1)%2][j]:
                dpx[i%2][j+F[0][i]]=True
                dpx[i%2][j-F[0][i]]=True


    MA=0
    for i in range(Ny):
        MA+=F[0][i]
        for j in range(N-MA,N+MA):
            if dpy[i%2][j]:
                dpy[(i+1)%2][j+F[1][i]]=True
                dpy[(i+1)%2][j-F[1][i]]=True

    if dpx[(Nx+1)%2][N+x] and dpy[Ny%2][N+y]:
        print("Yes")
    else:
        print("No")

main()






### FIXED CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

s=input()+"T"
N=len(s)
x,y=MI()

F=[[],[]]

temp=0
bit=0
for i in range(N):
    if s[i]=="F":
        temp+=1
    else:
        if temp!=0:
            F[bit].append(temp)
        bit=(bit+1)%2
        temp=0
        
XY=[set([0]), set([0])]
    
for bit in range(2):
    for i in range(len(F[bit])):
        temp=set([])
        a=F[bit][i]
        b=-a
        if bit==0 and i==0 and s[0]=="F":
            b=a
        for j in range(len(XY[bit])):
            aaa=XY[bit].pop()
            temp.add(aaa+a)
            temp.add(aaa+b)
        XY[bit]=temp
        
if (x in XY[0] ) and (y in XY[1] ):
    print("Yes")
else:
    print("No")
x = input().split
n = int(x[0])
m = int(x[1])
if n == 0:
  print(m * (m -1) /2)
elif m == 0:
  print(n * (n - 1) / 2)
else:
  k = m * (m -1) /2 + n * (n - 1) / 2
  print(k)

### FIXED CODE ###

x = input().split()
n = int(x[0])
m = int(x[1])
if n == 0:
  print(int(m * (m -1) /2))
elif m == 0:
  print(int(n * (n - 1) / 2))
else:
  k = m * (m -1) /2 + n * (n - 1) / 2
  print(int(k))
a=int(input())
if x < 1200:
    print('ABC')
else:
    print('ARC')

### FIXED CODE ###

x = int(input())
if x < 1200:
    print('ABC')
else:
    print('ARC')
from collections import deque
import sys
sys.setrecursionlimit(1000000)

def main():
    process_count, process_time, processes = get_input()
    result =  run_roundrobin(processes = processes, time = process_time)
    for r in result:
        print(r.name, r.time)


def run_roundrobin(processes, time, total_time = 0, result=[]):
    if not processes:
        return result

    p = processes.popleft()
    if p.time <= time:
        total_time += p.time
        p.time = total_time
        result.append(p)
    else:
        total_time += time
        p.time -= time
        processes.append(p)

    return run_roundrobin(processes, time, total_time, result)



def get_input():
    count, time = list(map(lambda x: int(x), input().split(' ')))

    processes = deque([])
    for _ in range(count):
        im = input().split(' ')
        p = Process(im[0], int(im[1]))
        processes.append(p)

    return count, time, processes


class Process():

    def __init__(self, name, time):
        self.name = name
        self.time = time


main()

### FIXED CODE ###

from collections import deque


def main():
    process_count, process_time, processes = get_input()
    result = run_roundrobin(processes=processes, time=process_time)
    for r in result:
        print(r.name, r.time)


def run_roundrobin(processes, time, total_time=0, result=[]):
    while processes:
        p = processes.popleft()
        if p.time <= time:
            total_time += p.time
            p.time = total_time
            result.append(p)
        else:
            total_time += time
            p.time -= time
            processes.append(p)

    return result


def get_input():
    count, time = list(map(lambda x: int(x), input().split(' ')))

    processes = deque([])
    for _ in range(count):
        im = input().split(' ')
        p = Process(im[0], int(im[1]))
        processes.append(p)

    return count, time, processes


class Process():

    def __init__(self, name, time):
        self.name = name
        self.time = time


main()
if input() > 30:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

if int(input()) >= 30:
  print("Yes")
else:
  print("No")
n = int(input())
a = []
while n > 0:
  if n%2 ==0:
    n = n/(-2)
    a.append("0")
  else:
    n = (n-1)(-2)
    a.append("1")
    
b = ""
for i in range(len(a)):
  b += a[len(a)-i-1]
  
print("b")
  
  

### FIXED CODE ###

n = int(input())
a = []
if n ==0:
  print(0)
else:
  while n != 0:
    if n%2 ==0:
      n = n/(-2)
      a.append("0")
    else:
      n = (n-1)/(-2)
      a.append("1")
    
  b = ""
  for i in range(len(a)):
    b += a[len(a)-i-1]

  print(b)
r = input()
print(3 * r**2)

### FIXED CODE ###

r =int(input())
print(3* r**2)
a, b, c = map(int, input().split())

if a % b == 0:
    if c == 0:
        ans = "YES"
    else:
        ans = "NO"
else:
    ans = "NO"
    for i in range(1, b+1):
        if c % ((a**i) % b) == 0:
            ans = "YES"
            break

print(ans)


### FIXED CODE ###

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

if a % b == 0:
    if c == 0:
        ans = "YES"
    else:
        ans = "NO"
else:
    ans = "NO"
    for i in range(1, b+1):
        if (a*i) % b == c:
            ans = "YES"
            break

print(ans)
# -*- coding: utf-8 -*-

def parent(i):
    return i // 2


def left(i):
    return 2 * i


def right(i):
    return 2 * i + 1

class MaxHeap(list):
    def __init__(self, H=0):
        list.__init__(self)
        self.H = H
        self[:] = [None] * (H+1)

    def insert(self, key):
        self.H += 1
        self.append(-float("inf"))
        self.heapIncreaseKey(self.H, key)

    def heapIncreaseKey(self, i, key):
        if key < self[i]:
            raise "error"
        self[i] = key
        while i > 1 and self[parent(i)] < self[i]:
            self[i], self[parent(i)] = self[parent(i)], self[i]

    def heapExtract(self):
        if self.H < 1:
            raise "underflow"
        maximum = self[1]
        self[1] = A[self.H]
        self.H -= 1
        self.maxHeapify(1)

        return maximum

    def maxHeapify(self, i):
        l = left(i)
        r = right(i)
        if l <= self.H and self[l] > self[i]:
            largest = l
        else:
            largest = i
        if r <= self.H and self[r] > self[largest]:
            largest = r

        if largest != i:
            self[i], self[largest] = self[largest], self[i]
            self.maxHeapify(largest)

        


if __name__ == '__main__':

    A = MaxHeap()
    c = [None, None]
    while c[0] != "end":
        c = input().split(" ")
        if c[0] == "insert":
            A.insert(int(c[1]))
        elif c[0] == "extract":
            print(A.heapExtract())
        else:
            pass


### FIXED CODE ###

# -*- coding: utf-8 -*-
from heapq import heappush, heappop

if __name__ == '__main__':

    q = []
    while True:
        c = input().split(" ")
        if c[0]=='end':
            break
        if c[0]=='insert':
            heappush(q, -int(c[1]))
        else:
            print(-heappop(q))
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = list(map(int, input().split()))
c.sort()
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = 0
count = 0
anse = [None for _ in range(N)]
def dfs(v, p):
    global ans
    global count
    if p != -1:
        ans += min(c[count], c[count+1])
        if anse[p-1] is None:
            anse[p-1] = c[count]
        if anse[v-1] is None:
            anse[v-1] = c[count+1]
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)
dfs(0, -1)
print(ans)
print(" ".join(map(str, anse)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = list(map(int, input().split()))

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))
s = input()
d = {"A":"T","T":"A","G":"C","C":"G"}
print(s["{}".format(s)])

### FIXED CODE ###

i = input()
L1=["A","C","G","T"]
L2=["T","G","C","A"]
print(L2[L1.index(i)])
n, k = map(int, imput().split())

m = 0

while g < k:
    g = n * 2
    m = m + 1

double(p) = 0.5**m
print(p)


### FIXED CODE ###

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

g = 0
ps = 0
for i in range(n):
    g = i+1
    m = 0
    while g < k:
        g = g * 2
        m = m + 1
    p = float(0.5**m / n)
    ps = ps + p

print(ps)
N = int(input())
s = [int(input()) for i in range(N)]
M = int(input())
t = [int(input()) for i in range(M)]

s1 = list(set(s))
a = []
for i in range len(s1):
    for j in range (N):
    if s1[i] == s[j]:
        a[i]+=1
for i in range len(s1):
    for j in range (M):
    if s1[i] == t[j]:
        a[i]-=1
print(max(a))

### FIXED CODE ###

A, B = map(int, input().split())
cnt = 0
for i in range (A, B+1):
    if str(i) == str(i)[::-1]:
        cnt += 1
print(cnt)
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, (d + w) % 2)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(100100)

n = int(input())
g = [[] for i in range(n)]
c = [-1 for i in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w = w % 2
    g[u].append([v, w])
    g[v].append([u, w])


def dfs(p, d):
    if c[p] == -1:
        c[p] = d
        for x, w in g[p]:
            dfs(x, d ^ w)


dfs(0, 0)

for i in range(len(c)):
    print(c[i])
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    tmp_color = 1
    for edge in n_list[node]:
        if edge[1] == parent_edge_id:
            continue
        try:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
        except Exception:
            print(0)
        paint(edge[0], edge[1])
        tmp_color += 1

    
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num    a
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

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


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])