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

s = list(input())
 
digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する
mod = 10 ** 9 + 7
power = 1
 
for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = (j * power) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = (val * power)% 13
            for k in range(13):
                dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    power = (power * 10) % 13
print(dp[digits-1][5])

### FIXED CODE ###

s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する
mod = 10 ** 9 + 7
power = 1

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = (j * power) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = (val * power)% 13
            for k in range(13):
                dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    power = (power * 10) % 13
print(dp[digits-1][5])
### BUGGY CODE ###

def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    l_list.sort()
    max_l = max(l_list)

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            if b - a > max_l:
                break
            for k, c in enumerate(l_list[i+1+j+1:]):
                # if is_ok(a, b, c):
                if c < a + b:
                    ans += 1
                else:
                    break
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect


def main():
    n = int(input())
    l_list = list(map(int, input().split()))
    l_list.sort()

    ans = 0
    for i, a in enumerate(l_list):
        for j, b in enumerate(l_list[i+1:]):
            x = a + b
            temp = bisect.bisect_left(l_list, x)
            ans += temp - (i + 1 + j + 1)
    print(ans)


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

n, m = map(int, input().split())
info = sorted([list(map(int, input().split())) for _ in range(m)])

q = []
t = m
append = q.append
for i in range(m):
	if info[i][0] == 1:
		append(info[i][1])
	else:
		t = i
		break

for j in range(t, m):
	if info[j][1] == n:
		if info[j][0] in q:
			print("POSSIBLE")
			break
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
side1 = set()
side2 = set()

for i in range(m):
	a, b = map(int, input().split())

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 1

for i in range(N-1):
    if P[i+1] <= min(P[:i+1]):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
lowest = 200000
ans = 0

for num in P:
    if num <= lowest:
        ans += 1
    lowest = min(lowest, num)

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

N,M = map(int,input().split())
divide_list = []
for i in range(M):
    newleft,newright = map(int,input().split())
    if i == 0:
        divide_list.append([newleft,newright])
    else:
        for divide in divide_list:
            left = divide[0]
            right = divide[1]
            if newleft >= right or newright <= left:
                divide_list.append([left,right])
            elif left <= newleft and newright <= right:
                divide_list.remove(divide)
                divide_list.append([newleft,newright])
            elif newleft <= left and right <= newright:
                pass
            elif left < newleft < right and right < newright:
                divide_list.remove(divide)
                divide_list.append([newleft,right])
            elif newleft < left < newright and newright < right:
                divide_list.remove(divide)
                divide_list.append([left,newright])
            else:
                print(divide,newleft,newright)
print(len(divide_list))

### FIXED CODE ###

N,M = map(int,input().split())
war_list = []
divide_list = []
for i in range(M):
    war_list.append(list(map(int,input().split())))
war_list.sort(key = lambda x : x[1])

divide_list = [war_list[0][1]]
for i in range(1,M):
    if  war_list[i][0] < divide_list[-1]:
        pass
    else:
        divide_list.append(war_list[i][1])
    
print(len(divide_list))
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    query = list(input().split())
    if query[0] == "1":
        s = s[::-1]
    else:
        if query[1] == "1":
            s = query[2] + s
        else:
            s += query[2]
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

state = 0
for i in range(q):
    query = list(input().split())
    if query[0] == "1":
        state += 1
    else:
        if (int(query[1]) + state) % 2 == 1:
            s.appendleft(query[2])
        else:
            s.append(query[2])

if state % 2 == 1:
    s = list(s)[::-1]

print("".join(s))
### BUGGY CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    rs = []
    for i in range(1, n + 1):
        r = 0
        for x in range(1, i - 4):
            for y in range(1, i - 4):
                for z in range(1, i - 4):
                    if f(x, y, z) > i:
                        break
                    elif f(x, y, z) == i:
                        r += 1
        rs.append(r)

    return rs


if __name__ == '__main__':
    main()


### FIXED CODE ###

from typing import List


def main():
    n = int(input())
    m = xyz(n)
    for i in m:
        print(i)


def f(x, y, z):
    return x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x


def xyz(n: int) -> List[int]:
    result = [0] * n
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                m = f(x, y, z)
                if m > n:
                    break
                result[m - 1] += 1

    return result


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


n,k = map(int,input().split())
arr = list(map(int,input().split()))
dp = [float("inf")]*len(arr)
dp[0] = 0
for i in range(len(arr)):
    for jump in range(i+1,i+k+1):
        if(jump<len(arr)):
            dp[jump] = min(dp[jump],dp[i]+abs(arr[jump]-arr[i]))
print(dp[-1]) 

### FIXED CODE ###


n,k = map(int,input().split())
arr = list(map(int,input().split()))
dp = [float("inf")]*len(arr)
dp[0] = 0
cost = 0
for i in range(len(arr)):
    for jump in range(i+1,i+k+1):
        if(jump<len(arr)):
            dp[jump] = min(dp[jump],dp[i]+abs(arr[jump]-arr[i]))
print(dp[-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_BIT = 60
    MOD = 10 ** 9 + 7

    data = [0] * (MAX_BIT + 2)
    for a in A:
        for bit in range(MAX_BIT + 1):
            if a & (1 << bit):
                data[bit] += 1
    ans = 0
    for i, d in enumerate(data):
        if d == 0:
            continue
        ans += pow(2, i, MOD) * d * (N-d)
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_BIT = 60
    MOD = 10 ** 9 + 7

    data = [0] * (MAX_BIT + 2)
    for a in A:
        for bit in range(MAX_BIT + 1):
            if a & (1 << bit):
                data[bit] += 1
    ans = 0
    for i, d in enumerate(data):
        if d == 0:
            continue
        ans += pow(2, i, MOD) * d * (N-d)
        ans %= MOD
    print(ans)

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

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ai_sum=0
for i in range(n):
	ai_sum+=a[i]
	clear=True
	scale=ai_sum
	for j in range(i+1,n):
		if(2*scale>=a[j]):
			scale+=a[j]
		else:
#			print(i,j,scale)
			clear=False
			break
	
	if(clear):
		ans=n-i
		break

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
sum_former=sum(a)
for i in range(n-1,-1,-1):
    sum_former-=a[i]
    if(2*sum_former < a[i]):
        ans=n-i
        break

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

import math

K = int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      c += math.gcd(math.gcd(i,j),k)
print(c)
      


### FIXED CODE ###

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

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import statistics
  import math
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  X=list(map(int,pin().split()))
  for i in range(N):
    try:
      print(statistics.median(X[:i]+X[i+1:]))
    except:
      pass
  return 

main()

### FIXED CODE ###

'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import copy
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N=int(pin())
  X=list(map(int,pin().split()))
  t=(N+1)//2
  Y=sorted(X)
  ans1=Y[t-1]
  ans2=Y[t]
  median=ans1+ans2
  for i in range(N):
    s=X[i]
    if s==ans1:
      print(ans2)
    elif s==ans2:
      print(ans1)
    elif  2*s<median:
      print(ans2)
    elif 2*s>median:
      print(ans1)
  return 

main()
### BUGGY CODE ###

N=int(input().split(" ")[0])
A=input().split(" ")
x=[]
for i in range(N):
    k=i+1
    y=0
    while k<=N-1:
        if y< int(A[k])-int(A[i]):
            y=int(A[k])-int(A[i])
        k+=1
    if y!=0:    
        x.append(y)

x.sort()

print(x.count(x[-1]))


### FIXED CODE ###

nt=input().split(" ")
N=int(nt[0])
T=int(nt[1])


a=input().split(" ")
int_a=[]
maxlist=[]
for i in range(N):
    int_a.append(int(a[i]))

reva=int_a
reva.reverse()
max=0
for i in range(N):
    if reva[i]>max:
        max=reva[i]
    maxlist.append(max)

maxlist.reverse()
int_a.reverse()


max=0
count=1
for i in range(N):
    if maxlist[i]-int_a[i]>max:
        count=1
        max=maxlist[i]-int_a[i]
    elif maxlist[i]-int_a[i]==max:
        count+=1

print(count)
### BUGGY CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    l = n + 1
    for k in range(1, n + 1):
        r = l + 1
        l = 0
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()


### FIXED CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    for k in range(1, n + 1):
        l = 0
        r = n // k + 2
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
inf = 10**18
M = 10**5
#dp = [0 for i in range(10**5+1)]


dp = [[inf for i in range(M+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, val = map(int, input().split())
    for v in range(M+1):
        if v >= val:
            dp[i+1][v] = min(dp[i][v-val] + w, dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for i in range(M+1):
    if dp[N][M-i] <= W:
        print(M-i)
        break

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
inf = 10**18
M = 10**5
#dp = [0 for i in range(10**5+1)]


dp = np.array([inf for i in range(M+1)])
dp[0] = 0
for i in range(N):
    w, v = map(int, input().split())
    dp[v:] = np.minimum(dp[:-v]+w, dp[v:])
    
for i in range(M+1):
    if dp[M-i] <= W:
        print(M-i)
        break
### BUGGY CODE ###

from collections import deque

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    score = deque([0])
    while j < k:
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if now == i:
            break
    ans = max(ans, max(list(score)[1:]))
    if j < k and score[-1] > 0:
        loop_num = k//j
        rest = k%j
        ans = max(ans, max(list(score)[:rest+1])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )
print(ans)
        

### FIXED CODE ###

from collections import deque

n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = -1000000000
for i in range(n):
    now = i
    j = 0
    score = deque([0])
    while j < k:
        score.append(score[j] +c[p[now]-1])
        now = p[now]-1
        j += 1
        if now == i:
            break
    ans = max(ans, max(list(score)[1:]))
    if j < k and score[-1] > 0:
        loop_num = k//j
        rest = k%j
        ans = max(ans, max(list(score)[:rest+1])+loop_num*score[-1] )
        ans = max(ans, max(list(score))+(loop_num-1)*score[-1] )
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
counter = 0
while(True):
  for i in range(n):
    if a[i] % 2 != 0:
      break
    else:
      a[i] = a[i] // 2
  counter += 1
print(counter)

### FIXED CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
g = a[0]
for i in range(n):
  g = gcd(g, a[i])
counter = 0
while(True):
  if g % 2 != 0:
    break
  else:
    counter += 1
    g = g // 2
print(counter)
### BUGGY CODE ###

global N
global Nlist
global Ma
global Mb
global minicost
minicost = 10000000
N, Ma, Mb = map(int,input().split()) 
Nlist = []
for i in range(N):
    a,b,c = map(int,input().split())
    Nlist.append([a,b,c])

def dvector(vector):
    global Ma
    global Mb
    global Nlist
    global minicost
    if len(vector) == len(Nlist):
        return 0
    vector.append(1)
    Masum = 0
    Mbsum = 0
    cost = 0
    for i in range(len(vector)):
        Masum+= vector[i] * Nlist[i][0]
        Mbsum+= vector[i] * Nlist[i][1]
        cost += vector[i] * Nlist[i][2]
        if Mbsum > 0:
            if Masum/Mbsum == Ma/Mb:
                if minicost > cost:
                    minicost = cost
        if cost < minicost:
            dvector(vector)
    vector.pop()
    vector.append(0)
    dvector(vector)
    vector.pop()
    return 0
    
dvector([])
if minicost == 10000000:
    print("-1")
else:
    print(minicost)

### FIXED CODE ###

global N
global Nlist
global Ma
global Mb
global minicost
minicost = 10000000
N, Ma, Mb = map(int,input().split()) 
Nlist = []
for i in range(N):
    a,b,c = map(int,input().split())
    Nlist.append([a,b,c])

def dvector(Masum,Mbsum,cost,vector):
    global Ma
    global Mb
    global Nlist
    global minicost
    if len(vector) == len(Nlist):
        return 0
    dvector(Masum,Mbsum,cost,vector+[0])
    Masum+= Nlist[len(vector)-1][0]
    Mbsum+= Nlist[len(vector)-1][1]
    cost += Nlist[len(vector)-1][2]
    if Mbsum > 0:
        if Masum/Mbsum == Ma/Mb:
            if minicost > cost:
                minicost = cost
    if cost < minicost:
        dvector(Masum,Mbsum,cost,vector+[1])
    return 0
    
dvector(0,0,0,[])
if minicost == 10000000:
    print("-1")
else:
    print(minicost)
### BUGGY CODE ###

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

ans = 0
if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n + 1):
        for a in range(k, b):
            ans += ((n - a) // b) + 1

print(ans)


### FIXED CODE ###

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

ans = 0
if k == 0:
    ans = n ** 2
else:
    for b in range(k + 1, n + 1):
        ans += (b - k) * (n // b)
        last_count = n % b - k + 1
        ans += last_count if last_count > 0 else 0

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

import sys
sys.setrecursionlimit(100000)
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
mapper={}
for i in range(H):
    for j in range(W):
        mapper[A[i][j]]=(i,j)

Q=int(input().strip())
L=[]
R=[]
dist={}
def search(l,r):
    if l==r:
        return 0
    if (l,r) in dist:
        return dist[l,r]
    else:
        if l+D==r:
            posl=mapper[l]
            posr=mapper[r]
            val= abs(posl[0]-posr[0])+abs(posl[1]-posr[1])
            dist[(l,l+D)]=val
            return val
        else:
            val=search(l,l+D)+search(l+D,r)
            dist[l,r]=val
            return val
for i in range(Q):
    cst=0
    l,r=map(int,input().split())
    print(search(l,r))

### FIXED CODE ###

# 解説読後
import sys
sys.setrecursionlimit(100000)
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
mapper={}
for i in range(H):
    for j in range(W):
        mapper[A[i][j]]=(i,j)

Q=int(input().strip())
dist=[0]*(H*W+1)
for i in range(1,H*W+1):
    if i<=D:
        dist[i] = 0
    else:
        pos1=mapper[i]
        pos2=mapper[i-D]
        dist[i]=dist[i-D]+abs(pos1[0]-pos2[0])+abs(pos1[1]-pos2[1])
for i in range(Q):
    cst=0
    l,r=map(int,input().split())
    print(dist[r]-dist[l])
### BUGGY CODE ###

t = input()
ans = ''
for i in range(len(t)):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)

### FIXED CODE ###

t = input()
ans = ''
for i in range(len(t)):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)
### BUGGY CODE ###

from itertools import product
n,m = map(int, input().split())

# dp[i][j] i個取った時の{+,-}*3 タイプの最大値
dp = [[0]*8 for i in range(m+1)]
op = [i for i in product([-1,1], repeat=3)]
#print(op)

for i in range(n):
    x,y,z = map(int, input().split())
    nxt = [[0]*8 for i in range(m+1)]
    for j in range(m):
        for k in range(8):
            nxt[j+1][k] = max(dp[j+1][k], dp[j][k] + op[k][0]*x+op[k][1]*y+op[k][2]*z)
    dp = nxt
print(max(dp[-1]))

### FIXED CODE ###

n, m = map(int, input().split())
v = [list(map(int, input().split())) for i in range(n)]
ans = 0
op = [-1,1]
for i in range(2):
    for j in range(2):
        for k in range(2):
            sx, sy, sz = op[i], op[j], op[k]
            ans_tmp = sum(sorted([x*sx+y*sy+z*sz for x,y,z in v], reverse=True)[:m])
            ans = max(ans, ans_tmp)
print(ans)
### BUGGY CODE ###

#143d
import itertools

N = int(input())
L_list = [int(e) for e in input().split()]

ans = 0

for comb in itertools.combinations(L_list, 3):
    if comb[0]<comb[1]+comb[2] and comb[1]<comb[2]+comb[0] and comb[2]<comb[0]+comb[1]:
        ans += 1

print(ans)

### FIXED CODE ###

from itertools import combinations
from bisect import bisect_left, bisect_right

N = int(input()) #2*10**3
L_list = [int(e) for e in input().split()]
index_list = [i for i in range(N)]

L_list.sort(reverse=False)
#print(L_list)

ans = 0

for comb in combinations(index_list, 2): #(2*10*3)*(2*10*3 -1)/2 ≒ 2*10*6
    a = L_list[comb[0]]
    b = L_list[comb[1]]
    
    #a < b+c ∴a-b < c
    #b < c+a ∴b-a < c
    if a-b > 0:
        low_limit = a-b
    else:
        low_limit = b-a
    index_left = bisect_right(L_list, low_limit) #log(2*10**6)≒6.3

    #c < a+b
    index_right = bisect_left(L_list, a+b) #log(2*10**6)
    
    #print(a,b,low_limit,a+b)
    #print(L_list[index_left:index_right])
    
    OK_c = index_right - index_left
    
    if index_left <= comb[0] <= index_right:
        OK_c -= 1
    if index_left <= comb[1] <= index_right:
        OK_c -= 1
        
    #print(OK_c)
    ans += OK_c
    
print(ans//3)
### BUGGY CODE ###

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

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = [[0]*n for i in range(n)]
from collections import deque
q = deque([[0,-1]])
reach[0] = True

while q:
    cur,col = q.popleft()
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            c[cur][next_i] = col
            c[next_i][cur] = col
            q.append([next_i,col])
            reach[next_i] = True

for a,b in ab:
    print(c[a][b]+1)


### FIXED CODE ###

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

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)
### BUGGY CODE ###

s = input()

ans = 0

while "ABC" in s:
    cnt = s.count("ABC")
    s = s.replace("ABC","BCA")
    ans += cnt
    
print(ans)

### FIXED CODE ###

s = input()
 
ans = 0
s = s.replace("BC","D")
cnt_A = 0
 

for i in s:
    if i == "A":
        cnt_A += 1
    elif i == "D":
        ans += cnt_A
    else:
        cnt_A = 0

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

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a)):
  for j in range(i,len(a)):
    if sum(a[t] for t in range(i,j+1)) == 0:
      cnt += 1
print(cnt)

### FIXED CODE ###

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

acc = [0 for i in range(n+1)]
for i in range(n):
    acc[i+1] = a[i] + acc[i]

ans = {}
for x in acc:
    ans.setdefault(x, 0)
    ans[x] += 1
cnt = 0
for i in ans:
    cnt += ans[i]*(ans[i]-1)//2

print(cnt)
### BUGGY CODE ###

import numpy as np
N = int(input())
X = [int(i) for i in input().split()]

for i in range(N):
    Y = X[:]
    Y.pop(i)
    print(int(np.median(Y)))

### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]
Y = X[:]
Y.sort()

for i in range(N):
    print(Y[int(N/2)] if Y[int(N/2)] > X[i] else Y[int(N/2)-1])