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

#!/usr/bin/env python3

s = str(input())
k = int(input())

sets = set([])
for i in range(0, len(s)):
    for j in range(0, len(s)-i):
        sets.add(s[j:j+i+1])
print(sorted(list(sets))[k-1])


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque


def search(moji):
    num = len(moji)
    setsn = set([])
    for i in range(len(s)-num+1):
        if s[i:i+num] == moji:
            str_ = s[i:i+num+1]
            if len(str_) == num+1:
                setsn.add(str_)
    sorted_setsn = sorted(setsn, reverse=True)

    return sorted_setsn


s = str(input())
k = int(input())
n = len(s)

sets1 = set([])
for i in range(0, len(s)):
    sets1.add(s[i])

sorted_sets1 = sorted(sets1)

# if k == 1:
#     print(sorted_sets1[0])
#     exit()
# else:
#     k -= 1

dq = deque(sorted_sets1)

while(len(dq)):
    # print(dq, k)
    moji = dq.popleft()
    k -= 1
    if k == 0:
        print(moji)
        exit()
    sorted_setsn = search(moji)

    # print(sorted_setsn)
    dq.extendleft(sorted_setsn)
### BUGGY CODE ###

N, x, y = list(map(int, input().split()))

cnt = [0] * (N)
for i in range(1, N+1):
  for j in range(i+1, N+1):
    temp = min(abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x))
    cnt[min(abs(j-i), temp)] += 1

for i in range(1, N):
  print(cnt[i])

### FIXED CODE ###

N, x, y = [int(i) for i in input().split()]

cnt = [0] * N
for i in range(1, N+1):
  for j in range(i+1, N+1):
    temp = min(abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x))
    cnt[temp] += 1

for i in range(1, N):
  print(cnt[i])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

def pairORSum(arr, n) : 
    ans = 0
    for i in range(0, n) : 
        for j in range(i + 1, n) : 
            ans = ans + (arr[i] ^ arr[j]) 
            ans %= MOD
    return ans 
  
n = int(input())
a = [int(item) for item in input().split()]
  
print(pairORSum(a, n)) 

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

def sumXOR(arr, n): 
    sumation = 0
    for i in range(0, 64): 
        zc = 0
        oc = 0
        idsum = 0
        for j in range(0, n): 
            if (arr[j] % 2 == 0): 
                zc = zc + 1
            else: 
                oc = oc + 1
            arr[j] = arr[j] // 2
        idsum = oc * zc * (1 << i) 
        sumation = sumation + idsum
        sumation %= MOD
      
    return sumation
  
n = int(input())
a = [int(item) for item in input().split()]
  
print(sumXOR(a, n))
### BUGGY CODE ###

import sys

n = int(input())

for i in range(1, 3500):
  for j in range(1, 3500):
    try:
        x = int(1 / (4/n - 1/i - 1/j))
        if x >= 1 and 4/n == 1/i + 1/j + 1/x:
            print(i, j, x)
            sys.exit()
    except:
        pass



### FIXED CODE ###

import sys

n = int(input())

def main():
    for i in range(1, 3500):
        for j in range(1, 3500):
            z = 4 * i * j - n * i - n * j
            if z > 0:
                x = n * i * j / z
                if x == int(x):
                    print(i, j, int(x))
                    sys.exit()


main()
### BUGGY CODE ###

k = int(input())
t = 7
kou = 1

if k % 2 == 0:
  print(-1)
  quit()
  
while t % k != 0:
    kou += 1
    t = 10 * t + 7
    
print(kou)

### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()

i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % K
    i += 1
    if ai == 0:
        break
print(i)
### BUGGY CODE ###

s = input()
k = len(s)
f = 0
while f == 0: 
  s = s.replace('01', '')
  s = s.replace('10', '')
  if s.count('0') == 0 or s.count('1') == 0:
    f =1 
    break
print(k - len(s))

### FIXED CODE ###

s = input()
k = len(s)
a = s.count('0')
b = s.count('1')
ans = 0
if a >= b:
  ans = k - a + b
else:
  ans = k + a - b
print(ans)
### BUGGY CODE ###

from numba import njit,jit

@jit
def main():
  # Worst Case
  #n,k=100000,100
  #a=[p for p in range(100000)]
  
  kl=[p for p in range(1,k+1)]
  dp=[10**9]*(n)
  dp[0]=0
  for i in range(n):
    for j in kl:
      ij=i+j
      if ij < n:
        m=dp[i]+abs(a[i]-a[ij])
        if m < dp[ij]:
          dp[ij]=m

  print(dp[n-1])

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

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100000,100
#a=[i for i in range(100000)]

kl=[i for i in range(1,k+1)]

dp=[float("inf")]*(n)
dp[0]=0
for i in range(1,n):
  dp[i] = min(dp[j] + abs(a[i] - a[j]) for j in range(max(0, i - k), i))

print(dp[n-1])
### BUGGY CODE ###

S=list(input())
S.reverse()
N=len(S)
R=[0]*N
m=2019
K=0

for i in range(N):
    K+=int(S[i])*10**i
    R[i]=K%m
d={}
for i in range(2019):
    d[i]=0

for i in range(N):
    d[R[i]]+=1
ans=0
for i in range(2019):
    if i == 0:
        ans += d[i]
        ans +=d[i]*(d[i]-1)//2
    else:
        ans +=d[i]*(d[i]-1)//2
print(ans)



### FIXED CODE ###

S=list(input())
S.reverse()
N=len(S)
R=[0]*N
R10=[0]*N
m=2019
K=0

R10[0]=1
R[0]=int(S[0])%m
for i in range(1,N):
    R10[i]=(R10[i-1]*10)%m
    R[i]=(R[i-1]+int(S[i])*R10[i])%m
d={}
for i in range(2019):
    d[i]=0

for i in range(N):
    d[R[i]]+=1
ans=0
for i in range(2019):
    if i == 0:
        ans += d[i]
        ans +=d[i]*(d[i]-1)//2
    else:
        ans +=d[i]*(d[i]-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Mar  1 01:07:09 2019

@author: yuta
"""

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

"""
TLE解法
def main(nk,a):
    k = nk[1]
    a_uni = list(set(a)) #重複なし数列
    a_uni_num = [0]*len(a_uni) #各数字の重複個数
    for i in range(len(a_uni)):
        for j in range(len(a)):
            if a[j] == a_uni[i]:
                a_uni_num[i] += 1
    a_uni_num_sort = sorted(a_uni_num) #重複個数を昇順で並び替え
    red_num = len(a_uni) - k #減らす種類の数
    print(sum(a_uni_num_sort[:red_num]))

main(NK,A)
"""
def main(nk,a):
    k = nk[1]
    a_uni = list(set(a)) #重複なし数列
    a_uni_num = [0]*len(a_uni) #各数字の重複個数
    for i in range(len(a_uni)):
        a_uni_num[i] = a.count(a_uni[i])
    a_uni_num_sort = sorted(a_uni_num) #重複個数を昇順で並び替え
    red_num = len(a_uni) - k #減らす種類の数
    print(sum(a_uni_num_sort[:red_num]))

main(NK,A)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Mar  1 01:07:09 2019

@author: yuta
"""
import collections

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

"""
TLE解法
def main(nk,a):
    k = nk[1]
    a_uni = list(set(a)) #重複なし数列
    a_uni_num = [0]*len(a_uni) #各数字の重複個数
    for i in range(len(a_uni)):
        for j in range(len(a)):
            if a[j] == a_uni[i]:
                a_uni_num[i] += 1
    a_uni_num_sort = sorted(a_uni_num) #重複個数を昇順で並び替え
    red_num = len(a_uni) - k #減らす種類の数
    print(sum(a_uni_num_sort[:red_num]))

main(NK,A)
"""
def main(nk,a):
    k = nk[1]
    values,counts = zip(*collections.Counter(a).most_common())
    print(sum(counts)-sum(counts[:k]))
main(NK,A)
### BUGGY CODE ###

N = int(input())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
C = [0 for i in range(N)]
st = input().split()
for i in range(N):
    A[i] = int(st[i])
st = input().split()
for i in range(N):
    B[i] = int(st[i])
st = input().split()
for i in range(N):
    C[i] = int(st[i])
A.sort();C.sort()
M = 0
for i in range(N):
    low = 0
    high = N - 1
    t = (low + high) // 2
    if A[N-1] < B[i]:
        t = N-1
    elif A[0] >= B[i]:
        t = -1
    else:
        while (low <= high):
            if A[t] < B[i] <= A[t+1]:
                break
            elif B[i] <= A[t]:
                high = t
            elif A[t+1] < B[i]:
                low = t+1
            t = (low + high) // 2
    low = 0
    high = N - 1
    s = (low + high) // 2
    if C[N-1] <= B[i]:
        s = N-1
    elif B[i] < C[0]:
        s = -1
    else:
        while (low <= high):
            if C[s] <= B[i] < C[s+1]:
                break
            elif B[i] < C[s]:
                high = s
            elif C[s+1] <= B[i]:
                low = s + 1
            s = (low + high) // 2
    M += (t+1)*(N-s-1)
print(M)

### FIXED CODE ###

N = int(input())
A = [0 for i in range(N)]
B = [0 for i in range(N)]
C = [0 for i in range(N)]
st = input().split()
for i in range(N):
    A[i] = int(st[i])
st = input().split()
for i in range(N):
    B[i] = int(st[i])
st = input().split()
for i in range(N):
    C[i] = int(st[i])
A.sort();C.sort()
M = 0
for i in range(N):
    low = 0
    high = N - 1
    t = (low + high) // 2
    if A[N-1] < B[i]:
        t = N-1
    elif A[0] >= B[i]:
        t = -1
    else:
        while (low <= high):
            if A[t] < B[i] <= A[t+1]:
                break
            elif B[i] <= A[t]:
                high = t
            elif A[t+1] < B[i]:
                low = t+1
            t = (low + high) // 2
    low = 0
    high = N - 1
    s = (low + high) // 2
    if C[N-1] <= B[i]:
        s = N-1
    elif B[i] < C[0]:
        s = -1
    else:
        while (low <= high):
            if C[s] <= B[i] < C[s+1]:
                break
            elif B[i] < C[s]:
                high = s
            elif C[s+1] <= B[i]:
                low = s + 1
            s = (low + high) // 2
    M += (t+1)*(N-s-1)
print(M)
### BUGGY CODE ###

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

a = abs(N-K)

b = abs(a-K)

while a >= b:
    a = b
    b = abs(b-K)

print(a)

### FIXED CODE ###

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

a = N%K

b = abs(a-K)

while a > b:
    a = b
    b = abs(b-K)

print(a)
### BUGGY CODE ###

N = int(input())
Mmax = 0
for i in range(N-1):
    Mmax += i+1

print(Mmax)

### FIXED CODE ###

N = int(input())

a = N/2
b = int(N/2)
if not(N%2 == 0):
    Mmax = N*b
elif N%2 == 0:
    Mmax = N*(b-1) + b



print(Mmax)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
X = {i:0 for i in range(-2*N,4*N+2)}
k = 0
while k<K:
    for i in range(1,N+1):
        d = A[i]
        X[2*i-2*d-1] += 1
        X[2*i+2*d+1] -= 1
    for i in range(-2*N+1,4*N+2):
        X[i] += X[i-1]
    for i in range(1,N+1):
        A[i] = X[2*i]
    X = {i:0 for i in range(-2*N,4*N+2)}
    cnt = 0
    for i in range(1,N):
        cnt += A[i]
    if cnt==N*N:
        break
    k += 1
print(*A[1:])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
cnt = 0
while cnt<K:
    B = [0 for _ in range(N+1)]
    for i in range(N):
        a = A[i]
        B[max(i-a,0)] += 1
        B[min(i+a,N-1)+1] -= 1
    for i in range(1,N+1):
        B[i] += B[i-1]
    A = B[:N]
    flag = 0
    for i in range(N):
        if A[i]<N:
            flag = 1
            break
    if flag==0:break
    cnt += 1
print(*A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
List = list(map(int, input().split()))

for i in range(1,n):
  print(List.count(i))
print("0")


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

n = int(input())
List = list(map(int, input().split()))
c = collections.Counter(List)
for i in range(1,n):
  print(c[i])
print("0")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(m):
    i=a.index(max(a))
    a[i]=int(a[i]/2)
print(sum(a))

### FIXED CODE ###

import sys
import heapq
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(a)
for _ in range(m):
    mina=int(heapq.heappop(a)/2)
    heapq.heappush(a,mina)
print(sum(a)*(-1))
### BUGGY CODE ###

from collections import deque

def solve(h, w, a):
    used = [[False] * (w+2) for _ in range(h+2)]
    for r in range(h+2):
        used[r][0] = True
        used[r][-1] = True
    for c in range(w+2):
        used[0][c] = True
        used[-1][c] = True
    que = deque([])
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
                used[r+1][c+1] = 0
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))

### FIXED CODE ###

from collections import deque

def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k

h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[99999999] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if costs[px][py] < costs[x][y] + 1:
                break
            costs[px][py] = costs[x][y] + 1
            q.append((px, py))

print(-1 if costs[x2][y2] == 99999999 else costs[x2][y2])


### FIXED CODE ###

from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    l,r=map(int,input().split())
    
    if(i==0):
        x=set(range(l,r+1))
    else:
        y=set(range(l,r+1))
        x=x.intersection(y)
print(len(x))


### FIXED CODE ###

from collections import Counter as co
n,m=map(int,input().split())
a=[]
x=0
y=10**6
for i in range(m):
    l,r=map(int,input().split())
    if(l>x):
        x=l
    if(r<y):
        y=r
if(y>=x):
    print(y-x+1)
else:
    print(0)
### BUGGY CODE ###

from collections import Counter
N = int(input())
a = list(map(int,input().split()))
b = list(set(a))
c = Counter(a)
cnt = 0
for i in range(len(b)):
  if b[i] <= c[b[i]]:
    cnt += c[b[i]] - b[i]
  else:
    cnt += a.count(b[i])
print(cnt)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
b = list(set(a))
ans = 0
for i in range(len(b)):
  cnt = 1
  while len(a) > 1 and a[-1] == a[-2]:
    a.pop()
    cnt += 1
  c = a.pop()
  if c <= cnt:
    ans += cnt - c
  else:
    ans += cnt
print(ans)
### BUGGY CODE ###

X = int(input())

#x^5-y^5=(x-y)(x^4+x^3y+x^2y^2+xy^3+y^4)

#for x in range(1, 121):
#  if ((x**5) - ((x-1)**5)) >= 1000000000:
#    print(x)

for a in range(1, 121):
  for b in range(-100000, 120):
    if b**5 == a**5-X:
      print(a, b)
      break



### FIXED CODE ###

X = int(input())

#x^5-y^5=(x-y)(x^4+x^3y+x^2y^2+xy^3+y^4)

#for x in range(1, 121):
#  if ((x**5) - ((x-1)**5)) >= 1000000000:
#    print(x)

for a in range(0, 121):
  for b in reversed(range(-122, 120)):
    if b**5 == a**5-X:
      print(a, b)
      exit()
### BUGGY CODE ###

from collections import Counter


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

R = [None] * (N + 1)
R[N] = Counter()
L = [None] * (N + 1)
L[0] = Counter()

# n < i
# for i in range(N):
#     c = Counter()
#     c[A[i] + i] = 1
#     L[i + 1] = L[i] | c

# n >= i
c = Counter()
for n in range(N - 1, -1, -1):
    R[n] = R[n + 1] | c
    R[n][(n + 1) - A[n]] += 1

ans = 0
for i, Ai in enumerate(A):
    # n < a
    # c0 = i - a
    # l = L[i][c0]

    # n >= a
    c1 = Ai + (i + 1)
    r = R[i + 1][c1]

    ans += r

print(ans)


### FIXED CODE ###

from collections import Counter


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

# R = [None] * (N + 1)
# R[N] = Counter()

R = Counter()
cnt = 0
for n in range(N - 1, 0, -1):
    R[(n + 1) - A[n]] += 1
    c = A[n - 1] + ((n - 1) + 1)
    cnt += R[c]

# ans = 0
# for i, Ai in enumerate(A):
#     # n < a
#     # c0 = i - a
#     # l = L[i][c0]

#     # n >= a
#     c1 = Ai + (i + 1)
#     r = R[i + 1][c1]

#     ans += r

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

n, q = map(int, input().split())
s = input()
indices = {}
for i in range(n):
    indices.setdefault(s[i], [])
    indices[s[i]].append(i)
g = [1 for _ in range(n)]
for _ in range(q):
    t, d = input().split()
    for i in indices.get(t, []):
        if s[i] == t:
            if d == 'L':
                if i != 0:
                    g[i-1] += g[i]
            else:
                if i != n-1:
                    g[i+1] += g[i]
            g[i] = 0
print(sum(g))

### FIXED CODE ###

import sys
def vanish_on_left(i, n, s, tds):
    for t, d in tds:
        if s[i] != t:
            continue
        if d == 'L':
            if i == 0:
                return True
            i -= 1
        else:
            if i == n-1:
                return False
            i += 1
    return False

def vanish_on_right(i, n, s, tds):
    for t, d in tds:
        if s[i] != t:
            continue
        if d == 'L':
            if i == 0:
                return False 
            i -= 1
        else:
            if i == n-1:
                return True
            i += 1
    return False


n, q = map(int, input().split())
s = input()
tds = []
for _ in range(q):
    tds.append(tuple(input().split()))
if vanish_on_left(0, n, s, tds):
    if vanish_on_left(n-1, n, s, tds):
        print(0)
        sys.exit()
    l0, r0 = 1, n-1
    while l0 < r0:
        k = (l0 + r0) // 2
        if vanish_on_left(k, n, s, tds):
            l0 = k+1
        else:
            r0 = k
else:
    l0 = 0
if vanish_on_right(n-1, n, s, tds):
    if vanish_on_right(l0, n, s, tds):
        print(0)
        sys.exit()
    l1, r1 = l0, n-2
    while l1 < r1:
        k = (l1 + r1 + 1) // 2
        if vanish_on_right(k, n, s, tds):
            r1 = k-1
        else:
            l1 = k
else:
    l1 = n-1
print(l1 - l0 + 1)
### BUGGY CODE ###

import math
import fractions
import collections
import itertools
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=1
flag=1
for i in range(N):
    ans=ans*A[i]
    if ans>10**18:
        flag=0
if flag==1:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

import math
import fractions
import collections
import itertools
N=int(input())
A=list(map(int,input().split()))
A.sort()
#A=[10**5]*(10**5)
#N=10**5
ans=1
flag=1
for i in range(N):
    ans=ans*A[i]
    if ans>10**18:
        flag=0
        break
if flag==1:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

s = input()
q = int(input())
flag = 0
cnt = 0

for i in range(q):
    t = input()
    if len(t) == 1:
        cnt += 1
        if flag == 0:
            flag = 1
        elif flag == 1:
            flag = 0
    else:
        _, a, b = (str(i) for i in t.split())
        if a == "1":
            if flag == 0:
                s = b + s
            elif flag == 1:
                s = s + b
        elif a == "2":
            if flag == 0:
                s = s + b
            elif flag == 1:
                s = b + s

if cnt % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    flag = 0
    cnt = 0
    front = []
    back = []

    for i in range(q):
        t = input()
        if len(t) == 1:
            cnt += 1
            if flag == 0:
                flag = 1
            elif flag == 1:
                flag = 0
        else:
            _, a, b = (str(i) for i in t.split())
            if a == "1":
                if flag == 0:
                    front.append(b)
                elif flag == 1:
                    back.append(b)
            elif a == "2":
                if flag == 0:
                    back.append(b)
                elif flag == 1:
                    front.append(b)

    if cnt % 2 == 0:
        front = front[::-1]
        s = ''.join(front) + s + ''.join(back)
    else:
        back = back[::-1]
        s = ''.join(back) + s[::-1] + ''.join(front)

    print(s)

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

# ref https://atcoder.jp/contests/abc153/submissions/9758833
# ref http://drken1215.hatenablog.com/entry/2020/01/26/225000

# coding: utf-8
H, N = map(int, input().split())
A = [0]
B = [0]

for i in range(N):
    a, b = (list(map(int, input().split())))
    A.append(a)
    B.append(b)

dp = [[float('inf') for i in range(H+1)] for j in range(N+1)]

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

for i in range(1, N+1):
    for j in range(1, H+1):
        dp[i][j] = min(dp[i-1][j],  # do not use magic
                       #    dp[i-1][max(j-A[i], 0)] + B[i],  # use i-th magic
                       dp[i][max(j-A[i], 0)] + B[i])   # use i-th magic
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])


print(dp[N][H])


### FIXED CODE ###

# ref https://atcoder.jp/contests/abc153/submissions/9758833
# ref http://drken1215.hatenablog.com/entry/2020/01/26/225000

# coding: utf-8
H, N = map(int, input().split())
A = [0]
B = [0]

for i in range(N):
    a, b = (list(map(int, input().split())))
    A.append(a)
    B.append(b)

dp = [[float('inf') for i in range(H+1)] for j in range(N+1)]

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

for i in range(1, N+1):
    for j in range(1, H+1):
        dp[i][j] = min(dp[i-1][j],
                       dp[i-1][max(j-A[i], 0)] + B[i],
                       dp[i][max(j-A[i], 0)] + B[i])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])


print(dp[N][H])
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())
AB = np.array(AB, np.int32).reshape(N - 1, 2)

a = AB[:, 0]
b = AB[:, 1]
d = np.ones_like(a, np.int32)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
graph.tocsr()
takahashi = dijkstra(graph, directed=False, indices=u)
aoki = dijkstra(graph, directed=False, indices=v)

print(int(aoki[takahashi < aoki].max()) - 1)

### FIXED CODE ###

import sys

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    dist = [-1] * (N + 1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist


DU, DV = dfs(u), dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if u < v:
        tmp = v - 1
        if answer < tmp:
            answer = tmp

print(answer)