Harryxun/stf_run huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class a168{
    public static void main(String[] args){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            String N = reader.readLine();
            int len = (int)N.length()-1;
            String last = N.substring(len);
            System.out.println(last);
            if(last.equals("3")){
                System.out.println("bon");
            }else if(last.equals("0") || last.equals("1") || last.equals("6") || last.equals("8")){
                System.out.println("pon");
            }else{
                System.out.println("hon");
            }
        }catch(IOException e){
            System.out.println("aaaa");
        }
    }
}

### FIXED CODE ###

N = str(input())
n = int(N[len(N)-1])
if n==3:
    print('bon')
elif n==0 or n==1 or n==6 or n==8:
    print('pon')
else:
    print('hon')
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
right=[i for i in l if i>0]
left=[i for i in l if i<=0]
k=k-l.count(0)
le=len(left)
ri=len(right)
rl=[0]*le 
rr=[0]*ri 
left=[abs(i) for i in left]
#print(left)
left=left[::-1]
rl[0]=left[0]
for i in range(1,le):
    rl[i]=rl[i-1]+(left[i]-left[i-1])
rr[0]=right[0]
mini=10**9 
for i in range(1,ri) :
    rr[i]=rr[i-1]+(right[i]-right[i-1])
#print(rl)
#print(rr)
if k==n:
    print(sum(rl)+sum(rr))
    exit()
for a in range(1,len(left)):
    b=k-a 
    #print(a,b,rl[a],rr[b-1])
    mini=min(mini,2*rl[a-1]+rr[b-1],rl[a-1]+2*rr[b-1])
print(mini)

### FIXED CODE ###

n,k=map(int,input().split())
l=[int(i) for i in input().split()]
right=[i for i in l if i>0]
left=[i for i in l if i<=0]
if not left: 
    sm=0 
    sm+=l[0]
    for i in range(1,k):
        sm+=(l[i]-l[i-1])
    print(sm)
    exit()
if not right: 
    sm=0 
    l=[abs(i) for i in l]
    l.sort()
    sm=l[0]
    for i in range(1,k):
        sm+=(l[i]-l[i-1])
    print(sm)
    exit()
le=len(left)
ri=len(right)
rl=[0]*le 
rr=[0]*ri 
left=[abs(i) for i in left]
left=left[::-1]
rl[0]=left[0]
for i in range(1,le):
    rl[i]=rl[i-1]+(left[i]-left[i-1])
rr[0]=right[0]
mini=10**20 
for i in range(1,ri) :
    rr[i]=rr[i-1]+(right[i]-right[i-1])
if len(left)>=k:
    mini=min(mini,rl[k-1])
if len(right)>=k:
    mini=min(mini,rr[k-1])
#print(left,right,rl,rr)
for a in range(1,len(left)+1):
    b=k-a 
    #print(a,b)
    if b>len(rr):
        #print('hsef')
        continue 
    mini=min(mini,2*rl[a-1]+rr[b-1],rl[a-1]+2*rr[b-1])
print(mini)
first=strings.spitlines(input())
P=first[0]
S=first[1]
count=0
for t in range(len(P)-1):
  if P=0:count=count+1
    else count=count
print(count)

### FIXED CODE ###

a=[input() for i in range(2)]
P=a[0]
S=a[1]
count=0
for t in range(len(P)):
  if P[t] != S[t]:
    count=count+1
print(count)
from collections import Counter
from pandas import Series

N,K=map(int,input().split())
A=list(map(int,input().split()))
count=0
S=set(A)
c=Counter(A)
L=c.most_common(len(S))

x=len(S)-1
for _ in range(len(S)-K):
    count=count+int(L[x][1])
    x=x-1

print(count)

### FIXED CODE ###

from collections import Counter


N,K=map(int,input().split())
A=list(map(int,input().split()))
count=0
S=set(A)
c=Counter(A)
L=c.most_common(len(S))

x=len(S)-1
for _ in range(len(S)-K):
    count=count+int(L[x][1])
    x=x-1

print(count)
import numpy as np

Tmp = []
Tmp = input().rstrip().split(' ')

nN = int(Tmp[0])
nM = int(Tmp[1])
nC = int(Tmp[2])
nAns = 0
ListA = []
ListB = []
ListB += list(map(int,input().split()))
nAns = 0

for i in range(nN):
  ListA += list(map(int,input().split()))
  nTmp = np.dot(ListA, ListB.T)
  nTmp += nC
  if nTmp > 0:
    nAns += 1

print(nAns)



### FIXED CODE ###

import numpy as np
 
Tmp = []
Tmp = input().rstrip().split(' ')
 
nN = int(Tmp[0])
nM = int(Tmp[1])
nC = int(Tmp[2])
nAns = 0
ListA = [0 for i in range(nM)]
ListB = [0 for i in range(nM)]
Tmp = input().rstrip().split(' ')
for i in range(nM):
  ListB[i] = int(Tmp[i])
nAns = 0
 
for i in range(nN):
  Tmp = input().rstrip().split(' ')
  for j in range(nM):
    ListA[j] = int(Tmp[j])

    
#  nTmp = np.dot(ListA, ListB.T)
  nTmp = 0
  for j in range(nM):
    nTmp += ListA[j] * ListB[j]
  nTmp += nC
  if nTmp > 0:
    nAns += 1

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

### FIXED CODE ###

a,b,c=map(int, input().split())
     
if a+b>=c:
  print("Yes")
else:
  print("No")
n,m=map(int,input().split())
a=set(map(int,input().split()))
b=set(map(int,input().split()))
c=1;N=0;M=0
for k in range(n*m,0,-1):
  if k in A and k in B:
    N+=1;M+=1
  elif k in A:
    c*=M;N+=1
  elif k in B:
    c*=N;M+=1
  else:
    c*=N*M-n*m+k
  c%=10**9+7
print(c)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)
s = input()

res = 0
for i in range(len(s)//2):
  if(s[i] != s[-i-1])
    res++

print(res)

### FIXED CODE ###

s = input()

res = 0
for i in range(len(s)//2):
  if(s[i] != s[-i-1]):
    res += 1

print(res)
from collections import deque
H,W=map(int,input().split())
white=0
s=[]
for y in range(H):
    line=input()
    white+=line.count('.')
    s.append(list(line))

q = deque([(0,0,1)])
q_append=q.append
q_popleft=q.popleft
while q:
    x,y,l=q_popleft()
    if s[y][x]!='.':
        continue
    if x==W-1 and y==H-1:
        print(white-l)
        break
    s[y][x]='*'
    for d in [(1,0),(0,1),(-1,0),(0,-1)]:
        nx, ny=(x+d[0],y+d[1])
        if 0<=nx<W and 0<=ny<H:
            q_append((nx,ny,l+1))
else:
    print(-1)

### FIXED CODE ###

n=int(input())
a=int(input())
m=n%500-a
if m<=0:
    print("Yes")
else:
    print("No")
n=int(input())
a=[]
cou=0

for i in range(n*2):
  a[i]=int(input())
  
a.sort()
for i*2 in range(n):
  cou+=min(a[i],a[i+1])
  
print(cou)

### FIXED CODE ###

N = int(input())

L = list(map(int, input().split()))

L.sort()

ans = 0

for i in range(N):
    ans = ans + L[i*2]
    
print(ans)
N = int(input())
L = [0]*(N+1)
L[0] = 2
L[1] = 1
if N<=2:
    print(L[i-1])
    exit()
for i in range(2,N+1):
    L[i] = L[i-1]+L[i-2]
print(L[N])


### FIXED CODE ###

N = int(input())
L = [0]*(N+2)
L[0] = 2
L[1] = 1
if N<=1:
    print(L[N])
else:
    for i in range(2,N+1):
        L[i] = L[i-1]+L[i-2]
    print(L[N])
import math

N = int(input())
T = []
[T.append(int(input())) for _ in range(N)]


ans = 1
for t in T:
    ans = ans * t // math.gcd(ans,t)

print(ans)

### FIXED CODE ###

N = int(input())
T = []
[T.append(int(input())) for _ in range(N)]

def gcd(a,b):
    if max(a,b)%min(a,b) == 0:
        return min(a,b)
    return gcd(max(a,b)%min(a,b),min(a,b))

ans = 1
for t in T:
    ans = ans * t // gcd(ans,t)

print(ans)
N = int(input())
fact = factorization(N)
fact_num = []
fact_num2 = []

    
for i in range(len(fact)):
    fact_num.append(fact[i][0])
    fact_num2.append(fact[i][1])

cnt=0

for j in range(1000000):
    for i in range(len(fact)):
        if N%fact_num[i]==0 and N%(fact_num[i]*(j+1))==0:
            N = N/(fact_num[i]*(j+1))
            cnt+=1

print(cnt)         
            




### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr
 
import sys     
N = int(input())
if N == 1:
    print(0)
    sys.exit()

fact = factorization(N)
fact_num = []
fact_num2 = []
 

for i in range(len(fact)):
    fact_num.append(fact[i][0])
    fact_num2.append(fact[i][1])

cnt=0

for j in range(max(fact_num2)+1):
    for i in range(len(fact)):
        if N%fact_num[i]==0 and N%(fact_num[i]**(j+1))==0:
            N = N/(fact_num[i]**(j+1))
            cnt+=1

            if N==1:
                print(cnt)
                sys.exit()
print(cnt)
def main():
    H,W,M = map(int,input().split())
    list = []
    dict_H = {key:0 for key in range(1,H+1,1)}
    dict_W = {key:0 for key in range(1,W+1,1)}
    for i in range(M):
        h,w = map(int,input().split())
        dict_H[h] += 1
        dict_W[w] += 1
        list.append((h,w))
    #print(list)
    maxH = max(dict_H.values())
    maxW = max(dict_W.values())
    wi = [i for i in range(1,W+1,1) if dict_H[i] == maxW]
    #print(retuH,gyoW,wi)
    for h in [i for i in range(1,H+1,1) if dict_W[i] == maxH]:
        for w in wi:
            if ((h,w) not in list):
                return maxH + maxW
    return maxH + maxW -1

print(main())


### FIXED CODE ###

def main():
    H,W,M = map(int,input().split())
    dict_gyo = {key: 0 for key in range(H)}
    dict_retu = {key: 0 for key in range(W)}
    dict_ichi = {}
    for i in range(M):
        h,w = map(int,input().split())
        dict_gyo[h-1] += 1
        dict_retu[w-1] += 1
        dict_ichi[(h-1,w-1)] = 1

    #print(dict_gyo,dict_ichi)

    maxgyo = max(dict_gyo.values())
    maxretu = max(dict_retu.values())
    #maxgyo_k = max(dict_gyo, key = dict_gyo.get)
    #maxretu_k = max(dict_retu, key = dict_gyo.get)
    #print(maxgyo_k,maxretu_k)
    result = maxgyo + maxretu - 1
    wi = [i for i in range(W) if dict_retu[i] == maxretu]
    for h in [i for i in range(H) if dict_gyo[i] == maxgyo]:
        for w in wi:
            if (h,w) not in dict_ichi:
                result = maxgyo + maxretu
                return result

    return result




print(main())
N,K = map(int,input().split())
 
P = [0]*N
m = 0
for i in range(K):
  a = int(input())
  b = list(int,input().split())
  for j in range(a):
    P[b[j]-1] = 1
    j += 1
    
print(P.count(0))

### FIXED CODE ###

n, k = map(int, input().split())
 
m = [0]*n
 
for i in range(k):
    d = int(input())
    a = [int(x) for x in input().split()]
    for j in range(d):
        m[a[j]-1] += 1
 
print(m.count(0))
, B, C, K = map(int, input().split())

ans = 0
for i in range(K):
    if A > 0:
        ans += 1
        A -= 1
    elif B > 0:
        B -= 1
    elif C > 0:
        ans -= 1
        C -= 1
        
        
print(ans)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

ans = 0
if K <= A:
    ans = K
elif K <= A + B:
    ans = A
else:
    ans = A  - (K - A - B) 
    
#rest = K - A - B    
print(ans)
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k, n, MOD) for i in range(1, k+1)]

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)


### FIXED CODE ###

# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)
X, Y = map(int, input().split())

c = 0
check = 0
X_k, Y_k = X, Y
while c < max([X, Y]):
    if (X_k / 2) == Y_k:
        check = 1
        c_r = Y_k
        break
    else:
        X_k -= 1
        Y_k -= 2
        c += 1

if check == 0:
    print(0)
else:
    N = c + c_r
    r = min([c, c_r])
    fact = [1, 1]
    inv = [0, 1] 
    factinv = [1, 1]
    p = 10 ** 9 + 7
    for i in range(2, N+1):
        fact.append(fact[-1] * i % p)
        inv.append(-inv[p%i] * (p // i) % p)
        factinv.append(factinv[-1] * inv[-1] % p)

print(fact[N] * factinv[r] * factinv[N-r] % p)

### FIXED CODE ###

import sys

X, Y = map(int, input().split())

n = (2*Y-X) / 3
m = (2*X-Y) / 3

if (X + Y) % 3 != 0 or n < 0 or m < 0:
    print(0)
    sys.exit(0)

N = int(n + m)
r = int(min([n, m]))
p = 10**9 + 7
fact = [1, 1]
inv = [0, 1]
factinv = [1, 1]

for i in range(2, N+1):
    fact.append(fact[-1]*i % p)
    inv.append(-inv[p%i] * (p//i) % p)
    factinv.append(factinv[-1] * inv[-1] % p)

print(fact[N] * factinv[r] * factinv[N-r] % p)
H,W= map(int,raw_input().split())

M = []
for i in range(H):
	M.append(raw_input().split())
	
flag_list_H = []
for i in range(H):
	if '#' in M[i]:
		flag_list_H.append(True)
	else:
		flag_list_H.append(False)

flag_list_W = []
for i in range(W):
	flag = False
	for j in range(H):
		if M[j][i]=='#':
			flag=True
	flag_list_W.append(flag)

for i in range(H):
	answer = ""
	for j in range(W):
		if flag_list_H[i] and flag_list_W[j]:
		answer+=M[i][j] + " "
	print answer[:-1]
	

### FIXED CODE ###


H,W= map(int,raw_input().split())

M = []
for i in range(H):
	M.append(raw_input())
	
flag_list_H = []
for i in range(H):
	if '#' in M[i]:
		flag_list_H.append(True)
	else:
		flag_list_H.append(False)

flag_list_W = []
for i in range(W):
	flag = False
	for j in range(H):
		if M[j][i]=='#':
			flag=True
	flag_list_W.append(flag)

for i in range(H):
	if flag_list_H[i]:
		answer = ""
		for j in range(W):
			if flag_list_W[j]:
				answer+=M[i][j]
		print answer
if 400 <= X <= 599:
    print(8)
if 600 <= X <= 799:
    print(7)
if 800 <= X <= 999:
    print(6)
if 1000 <= X <= 1199:
    print(5)
if 1200 <= X <= 1399:
    print(4)
if 1400 <= X <= 1599:
    print(3)
if 1600 <= X <= 1799:
    print(2)
if 1800 <= X <= 1999:
    print(1)

### FIXED CODE ###

X = int(input())

if 400 <= X <= 599:
    print(8)
if 600 <= X <= 799:
    print(7)
if 800 <= X <= 999:
    print(6)
if 1000 <= X <= 1199:
    print(5)
if 1200 <= X <= 1399:
    print(4)
if 1400 <= X <= 1599:
    print(3)
if 1600 <= X <= 1799:
    print(2)
if 1800 <= X <= 1999:
    print(1)
h, n = map(int, input().split())

S = []
for _ in range(n):
    D = list(map(int, input().split()))
    S.append(D)

dic={}

def rec(magic, nokori,sum_mp):
    if nokori<=0:
        return sum_mp
    if magic >= n:
        return 10**9

    if str(magic)+"_"+str(nokori) in dic:
        return dic[str(magic)+"_"+str(nokori)]

    dmg = S[magic][0]
    mp  = S[magic][1]

    min_mp = min(
        rec(magic  ,nokori-dmg,sum_mp+mp), # use this magic, and check this magic again
        rec(magic+1,nokori-dmg,sum_mp+mp), # use this magic, and check next magic                    rec(magic+1,nokori,sum_mp       ), # don't use this magic, and check next magic
    )

    dic[str(magic)+"_"+str(nokori)] = min_mp
    return min_mp

print(rec(0,h,0))

### FIXED CODE ###

h, n = map(int, input().split())
s = []
for _ in range(n):
    D = list(map(int, input().split()))
    s.append(D)

dp = [[10**10 for i in range(h+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    dmg=s[i][0]
    mp=s[i][1]
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][min(j+dmg,h)] = min(dp[i+1][min(j+dmg,h)], dp[i+1][j]+mp)

print(dp[-1][-1])
ans=max(max(a*c,a*d),max(b*c,b*d))
print(ans)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
ans=0
if a>=0:
    if c>=0:
        ans=b*d
    elif d>=0:
        ans=b*d
    else:
        ans=a*d
elif b>=0:
    if c>=0:
        ans=b*d
    elif d>=0:
        ans=max(b*d,a*c)
    else:
        ans=a*c
else:
    if c>=0:
        ans=b*c
    elif d>=0:
        ans=a*c
    else:
        ans=a*c
print(ans)
n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 0
checked_steps = {-1:0, 0:1, 1:1, 2:2}
divide_num = 1000000007 

for i in range(3, n):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count % divide_num)

### FIXED CODE ###

n, m = map(int, input().split())
now_step = 0
# count=1*a+2*bとなるような、0以上の全てのa,bについて、1をa個、2をb個並べる並べ方を返す.
# [1,(a+b)]からa個を選ぶ選び方と同じ
# ただし、これはnumber-1とnumber-2が分かっている場合は、number-1から1つ、あるいはnumber-2から二つ進む進み方の和で表せる
# よって、counte_steps(number) = count_steps(number-1) + count_steps(number-2)
# 初期値はcount_steps(1) = 1, count_steps(2) = 2,count_steps(0) = 1
checked_steps = {-1:0, 0:1, 1:1}
divide_num = 1000000007 

for i in range(2, n+1):
    checked_steps[i] = (checked_steps[i-1] + checked_steps[i-2]) % divide_num

all_count = 1
for i in range(m):
    a = int(input())
    if(a < now_step):
        continue
    all_count = (all_count * checked_steps[a - 1 - now_step]) % divide_num
    now_step = a + 1
all_count = (all_count * checked_steps[n - now_step]) % divide_num
print(all_count)
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2
    except:
        print(0)

ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
import sys

count = [0 for _ in range(100)]
mode = [0]

for s in sys.stdin:
    x = int(s)
    count[x-1] += 1

for i in range(len(count)):
    if count[i] > mode[0]:
        mode.clear()
        mode.append(i+1)
    elif count[i] == mode[0]:
        mode.append(i+1)

for i in mode:
    print(i)

### FIXED CODE ###

import sys

count = [0 for _ in range(101)]
mode = 0

for s in sys.stdin:
    x = int(s)
    count[x] += 1
    mode = max(mode, count[x])

for i in range(101):
    if count[i] == mode:
        print(i)
n=int(input())
d=sorted(list(map(int,input().split())))
print(d[n/2]-d[n/2-1])

### FIXED CODE ###

n=int(input())
d=sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append((b-1,i))
    graph[b-1].append((a-1,i))
ans = 0
print(graph)
pos = 0
for i in range(N-1):
    if ans < len(graph[i]):
        ans = len(graph[i])
        pos = i
print(ans)

color = [-1 for i in range(N-1)]
def dps(now,pare,par_col=-1):
    col = 1
    for u,idx in graph[now]:
        if u != pare :
            if col == par_col :
                col += 1
            color[idx] = col
            dps(u,now,col)
            col += 1

dps(0,-1,-1)
print("\n".join(map(str,color)))

### FIXED CODE ###

list = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
S = input()
for i in range(len(list)):
    if S == list[i] :
        print("{}".format(7 - i))
from collections import defaultdict
n,m= map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(m):
    b,c = map(int, input().split())
    d.append([b,c])
d = sorted(d, key=lambda x:x[1], reverse=True)
a = sorted(a)
itr = 0
for i in range(len(d)):
    change = d[i]

    for j in range(change[0]):
        if a[itr] > change[1]:
            print(sum(a))
            exit()
        else:
            a[itr] = change[1]
        itr+=1
print(sum(a))


### FIXED CODE ###

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

bc = []

for i in range(m):
    b,c=map(int,input().split())
    bc.append([b,c])

bc = sorted(bc, key=lambda x: x[1],reverse=True)
a = sorted(a)

itr = 0 
for i in bc:
    b, c = i[0], i[1]
    for j in range(b):
        if a[itr]>=c:
            print(sum(a))
            exit()
        else:
            a[itr]=c
            itr +=1
            if itr == n:
                print(sum(a))
                exit()
print(sum(a))
n, m = map(int, input().split())
A = set()
for i in range(m):
    a.append(int(input()))
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""

### FIXED CODE ###

n, m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""
import math
import numpy as np
n, x0 = map(int, input().split())
x = np.abs(np.array(list(map(int, input().split()))) - x0)
xx = x[0]
for i in range(1, n):
    xx = math.gcd(xx, x[i])
print(xx)

### FIXED CODE ###

from fractions import gcd
import numpy as np
n, x0 = map(int, input().split())
x = np.abs(np.array(list(map(int, input().split()))) - x0)
xx = x[0]
for i in range(1, n):
    xx = gcd(xx, x[i])
print(xx)
from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()
ss=''
tt=''

l=lcm(n,m)
x=['x']*l

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    x[i*(l//m)]=t[i]

for i in range(n):
    if x[i*(l//n)]!=s[i]:
        print(-1)
        exit()

for i in range(m):
    if x[i*(l//m)]!=t[i]:
        print(-1)
        exit()
print(l)


### FIXED CODE ###

from fractions import gcd
def lcm(x,y):
    return x*y//gcd(x,y)
n,m = map(int,input().split())
s=input()
t=input()

l=lcm(n,m)
x=dict()

for i in range(n):
    x[i*(l//n)]=s[i]

for i in range(m):
    j=i*(l//m)
    if j in x and x[j]!=t[i]:
        print(-1)
        exit()
print(l)