Harryxun/stf_run huggingface dataset:
MOD = (10 ** 9) + 7

f_list = [1] * 100000
f_r_list = [1] * 100000

for i in range(99999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100002 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))

### FIXED CODE ###

MOD = (10 ** 9) + 7

f_list = [1] * 100001
f_r_list = [1] * 100001

for i in range(100000):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, 100002):
	f_r_list[-i] = int((f_r_list[-i + 1] * (100003 - i)) % MOD)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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


doubled = sum(a) - n * (n + 1) / 2
x = a.index(doubled)
y = a_r.index(doubled)
num = x + y

print(n)

for i in range(2, n + 2):
	if num >= i - 1:
		print(int((comb(n + 1, i) - comb(num, i - 1)) % MOD))
	else:
		print(comb(n + 1, i))
def main():
    input = input()
    if 0 <= input < 86400:
        hour = int(input % 3600)
        minute = int((input / 60) % 60)
        seconde = int(input % 60)
        print("{0}:{1}:{2}".format(hour,minute,seconde))

if __name__ == "__main__":
    main()

### FIXED CODE ###

input = int(input())
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))
N = int(input())
sum = 0.0
for i in range(N):
    x,u = map(float,input().split())
    if u == 'BTC':
        x *= 380000.0
    sum += x
print(sum)

### FIXED CODE ###

N = int(input())
sum = 0.0
for i in range(N):
    x,u = input().split()
    x = float(x)
    if u == 'BTC':
        x *= 380000.0
    sum += x
print(sum)
r,g,b=input().split()
if int(t+g+b)%4==0:
  print("YES")
else:
  print("NO")
  

### FIXED CODE ###

r,g,b=input().split()
if int(r+g+b)%4==0:
  print("YES")
else:
  print("NO")
s = list(input())
s = s[::-1]
s = ''.join(s)
n = len(s)
dp = [0]*2018
now = 0

dp[0] = 1
for i in range(n):
    now += 10**i * int(s[i])
    tmp = now % 2019
    dp[tmp] += 1

ans = sum([i*(i-1)/2 for i in dp if i > 1])
print(int(ans))


### FIXED CODE ###

s = input()
n = len(s)
dp = [1] + [0]*2019
now = 0
i = 1

for c in reversed(s):
    now = (now+i*int(c))%2019
    dp[now] += 1
    i *= 10
    i %= 2019

ans = sum([i*(i-1)/2 for i in dp])
print(int(ans))
N,X=map(int,input().split())
L=list(map(int,input().split()))

D=0
i=0
count=0

while D<=X and i<=N:
    D+=L[i]
    i+=1
    count+=1
print(count)
    

### FIXED CODE ###

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


if L[0]>X:
    print(1)
else:
    D=0
    i=0
    count=1
    while D<=X and i<=N-1:
        if D+L[i]<=X:
            D+=L[i]
            i+=1
            count+=1
        else:
            break
    print(count)
a,b = input().split()
print(a - b + 1)

### FIXED CODE ###

a = list(map(int,input().split()))
print(a[0] - a[1] + 1)
newarr = input()
newarr = newarr.split()
n = int(newarr[0])
m = int(newarr[1])
dicts = {}
ans = [0] * (n + 1)
for line in range(m):
    newarr = input()
    newarr = newarr.split()
    froom = int(newarr[0])
    sroom = int(newarr[1])
    if froom not in dicts:
        dicts[froom] = []
    if sroom not in dicts:
        dicts[sroom] = []
    dicts[froom].append(sroom)
    dicts[sroom].append(froom)
queue = []
if 1 not in dicts:
    print("No")
else:
    ans[1] = 1
    curarr = dicts[1]
    for i in curarr:
        queue.append(i)
        ans[i] = 1 
    while queue:
        curitem = queue.pop(0)
        if curitem not in dicts:
            continue 
        curarr = dicts[curitem]
        for i in curarr:
            if ans[i] == 0:
                ans[i] = curitem 
                queue.append(i)

    finalans = []
    flag = 0 
    for i in range(2, n + 1):
        if i == 0 :
            flag = 1 
            break 
        finalans.append(ans[i])
    if flag == 1:
        print("No")
    else:
        print("Yes")
        for i in finalans:
            print(i)




### FIXED CODE ###

n = int(input())
ones = n % 10 

if ones == 2 or ones == 4 or ones == 5 or ones == 7 or ones == 9:
    print("hon")
elif ones == 0 or ones == 1 or ones == 6 or ones == 8:
    print("pon")
else:
    print("bon")
n = int(input())
h = list(map(int, input().split()))


dp =[[-2] * 2 for i in range(n)]


def f(index, is_sub):
    if(dp[index][is_sub] != -2):
        return dp[index][is_sub]

    v = h2[index][is_sub]
    if(index == 0):
        dp[index][is_sub] = h2[index][is_sub]
        #print(dp)
        return dp[index][is_sub]

    pre_v = f(index-1, 0)
    dp[index][is_sub] = -2
    if(pre_v != -1 and pre_v <= v):
        dp[index][is_sub] = v
        #print("set value",index,is_sub,pre_v,v)
    pre_v = f(index-1, 1)
    if(pre_v != -1 and pre_v <= v):
        dp[index][is_sub] = v
        #print("set value",index,is_sub,pre_v,v)

    if(dp[index][is_sub]!=v):
        #print("set value",index,is_sub,"NO")
        dp[index][is_sub] = -1
    
    #print(dp)
    return dp[index][is_sub]


h2 = [[i,i-1] for i in h]
#print(dp)
if(f(n-1,1)!=-1 or f(n-1,0)!=-1):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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


h[0] = h[0] -1
for i in range(1,n):
    if(h[i-1] < h[i]):
        h[i] = h[i]-1

flag = True
for i in range(1,n):
    if(h[i-1]>h[i]):
        flag = False

if(flag):
    print("Yes")
else:
    print("No")
n,m=map(int,input().split())
s=input()
t=input()

if n<m:
  n,m=m,n
  s,t=t,s

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(10**5)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)]=s[i]
for i in range(1,m):
  if X[int(i*L/m)] !="":
    if X[int(i*L/m)] !=t[i]:
      print(-1)
      exit()
print(L)

### FIXED CODE ###

n,m=map(int,input().split())
s=input()
t=input()

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
g=gcd(n,m)
for i in range(g):
  if s[int(i*n/g)]!=t[int(i*m/g)]:
    print(-1)
    exit()
print(L)
#test
def hersCode(L, n):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue()
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()


### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, K = map(int, input().split())

    if K > (N-1)*(N-2)//2:
        print(-1)
    else:
        edges = []
        m = N-1+(N-1)*(N-2)//2-K
        for i in range(1, N+1):
            edges.append("{} {}".format(1, i))

        add_edge = (N-1)*(N-2)//K

        fr = 2
        to = 3
        while add_edge:
            edges.append("{} {}".format(fr, to))
            to += 1
            if to >= N:
                fr += 1
                to = fr+1
            add_edge -= 1
        print(m)
        print("\n".join(edges))


solve()


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, K = map(int, input().split())

    if K > (N-1)*(N-2)//2:
        print(-1)
    else:
        edges = []
        m = N-1+(N-1)*(N-2)//2-K
        for i in range(2, N+1):
            edges.append("{} {}".format(1, i))

        add_edge = (N-1)*(N-2)//2-K

        fr = 2
        to = 3
        while add_edge:
            edges.append("{} {}".format(fr, to))
            to += 1
            if to > N:
                fr += 1
                to = fr+1
            add_edge -= 1
        print(m)
        print("\n".join(edges))


solve()
import math

x, y, X, Y = [int(i) for i in input().split()]
print(math.sqrt((x-X)**2 + abs(y-Y)**2))

### FIXED CODE ###

import math

x, y, X, Y = [float(i) for i in input().split()]
print(math.sqrt((x-X)**2 + (y-Y)**2))
n, m = map(int, input().split())

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

dp = [-1 for _ in range(n+1)]

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(n+1):
    longest_path(u)

print(max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

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

edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)

dp = [-1 for _ in range(n+1)]

def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d

for u in range(1, n+1):
    longest_path(u)

print(max(dp))
a = int(input())
b = int(input())
if a<10 and b<10:
  print(a*b)
  
else:
  print('-1')


### FIXED CODE ###

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

if a<10 and b<10:
  print(a*b)
  
else:
  print('-1')
from _collections import deque

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

r = deque(['1'])

fhinish_roop = 0
index = 0
while not fhinish_roop:
    if str(a[index]) not in r:
        r.append(str(a[index]))
        index = a[index] - 1
    else:
        fhinish_roop = 1
        r_2 = "".join(r)
# print(r, index)
roop_l = r_2.find(str(a[index]))
# print(roop_l)
roop_len = len(r) - roop_l
roop_start_index = roop_l
# print(roop_len)

if k < roop_start_index:
    print(a[k - 1])

else:
    ans = (k - roop_start_index) % roop_len
    # print('ans={}'.format(ans))
    print(r[roop_start_index + ans])


### FIXED CODE ###

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

for i in range(n):
    a[i] -= 1

memo = [0] * n

index = 0
memo_index = 0
cnt_k = 1
while 1:
    tmp_move_to = a[index]
    if not memo[tmp_move_to]:
        memo[tmp_move_to] = 1
        index = tmp_move_to
        if cnt_k == k:
            print(tmp_move_to + 1)
            exit()
        cnt_k += 1
    else:
        break
k -= cnt_k

kaburi = tmp_move_to
circle = [kaburi]

index = kaburi
while 1:
    if kaburi == a[index]:
        break
    else:
        circle.append(a[index])
        index = a[index]
# print(circle)
print(circle[k % len(circle)] + 1)
# -*- coding: utf-8 -*-
def get_numbers():
    return map(int, input().split())

a, b = get_numbers()
if a % 2 == 1:
    ans = a
    numbers = list(range(a + 1, b + 1))
else:
    ans = 0
    numbers = list(range(a, b + 1))

mod = len(numbers) % 4


if mod == 0:
    print(ans)
elif mod == 1:
    print(ans ^ b)
elif mod == 2:
    print(ans ^ 1)
elif mod == 3:
    print(ans ^ 1 ^ b)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def get_numbers():
    return map(int, input().split())


def xor(n):
    if n % 4 == 3:
        return 0
    if n % 4 == 0:
        return n
    if n % 4 == 1:
        return 1
    if n % 4 == 2:
        return 1 ^ n


a, b = get_numbers()
print(xor(a - 1) ^ xor(b))
a,b = (int(i) for i in input().split())
print(len(str(a+b)))

### FIXED CODE ###

import sys
array = []
for inp in sys.stdin.readlines():
    array.append(inp.split())
for i in range(len(array)):
    a =int(array[i][0]) + int(array[i][1])
    print(len(str(a)))
n=int(input())
a=[]
r=[]
for i in input().split():
  a.append(int(i))
a.sort()
t=a.pop(-1)
b=a(0)
for i in a:
  if i>=0:
    r.append([b,i])
    b=b-i
  else:
    r.append([t,i])
    t=t-i
print(t-b)
r.append([t,b])
for i in r:
  print(r[0],r[1])


### FIXED CODE ###

n=int(input())
a=[]
r=[]
for i in input().split():
  a.append(int(i))
a.sort()
t=a.pop(-1)
b=a.pop(0)
for i in a:
  if i>=0:
    r.append([b,i])
    b=b-i
  else:
    r.append([t,i])
    t=t-i
print(t-b)
r.append([t,b])
for i in r:
  print(i[0],i[1])
n=int(input())
a=[int(input()) for _ in range(n)]
aa=sorted(a[:])
for i in range(n):
  k=a[i]
  t=-1
  while True:
      if aa[t] != k:
          print(aa[t])
          break
      else: t -= 1

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
aa=sorted(list(set(a[:])),reverse=True)
maxa=aa[0]
f=False if a.count(maxa) != 1 else True
for i in range(n):
    if a[i] == maxa and f:
        print(aa[1] if len(aa) != 1 else maxa)
    else:
        print(maxa)
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
M = 10**9 + 7

dp = [[None] * (k + 1) for _ in range(n + 1)]
def dfs(i=0, at=k):
    if dp[i][at] is not None:
        return dp[i][at]

    if i == n:
        r = int(at == 0)
        dp[i][at] = r
        return r

    cnt = 0
    for v in range(a[i] + 1):
        if v > at:
            break
        cnt += dfs(i + 1, at - v)
    dp[i][at] = cnt
    return cnt
#
# print(dfs())
# for v in dp:
#     print(v)

def fm(array):
    return ["*" if v is None else v for v in array]

def mod(v):
    if v >= M:
        return v % M
    return v

def addmod(a, b):
    return mod(a + b)

# for at in range(k + 1):
for i in reversed(range(n + 1)):
    for at in range(k + 1):
        if i == n:
            dp[i][at] = int(at == 0)
            continue
        cnt = 0
        # print(*fm(dp[i]), end=" -> ")
        # for v in range(min(a[i], at) + 1):
        #     cnt += dp[i + 1][at - v]
        # dpcnt = cnt
        cnt = cs[at] - cs[at - min(a[i], at) - 1]
        dp[i][at] = mod(cnt)
        # print(*fm(dp[i]), "@", at - min(a[i], at), "~", at)
        # print(cnt, "@", at - min(a[i], at), "~", at, ":", *fm(dp[i + 1])[at - min(a[i], at):at + 1])
        # print(dpcnt, cnt)
    cs = list(itertools.accumulate(dp[i], addmod)) + [0]
    # print(*cs, "cs")
    # print(*dp[i], "dp")
    # print("-----")
print(dp[0][k] % M)

# for v in dp:
#     print(*fm(v))


### FIXED CODE ###

import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
M = 10**9 + 7

dp = [[None] * (k + 1) for _ in range(n + 1)]
def dfs(i=0, at=k):
    if dp[i][at] is not None:
        return dp[i][at]

    if i == n:
        r = int(at == 0)
        dp[i][at] = r
        return r

    cnt = 0
    for v in range(a[i] + 1):
        if v > at:
            break
        cnt += dfs(i + 1, at - v)
    dp[i][at] = cnt
    return cnt
#
# print(dfs())
# for v in dp:
#     print(v)

def fm(array):
    return ["*" if v is None else v for v in array]

def mod(v):
    if v >= M:
        return v % M
    return v

# def addmod(a, b):
#     return mod(a + b)

# for at in range(k + 1):
for i in reversed(range(n + 1)):
    for at in range(k + 1):
        if i == n:
            dp[i][at] = int(at == 0)
            continue
        cnt = 0
        # print(*fm(dp[i]), end=" -> ")
        # for v in range(min(a[i], at) + 1):
        #     cnt += dp[i + 1][at - v]
        # dpcnt = cnt
        cnt = cs[at] - cs[at - min(a[i], at) - 1]
        dp[i][at] = mod(cnt)
        # print(*fm(dp[i]), "@", at - min(a[i], at), "~", at)
        # print(cnt, "@", at - min(a[i], at), "~", at, ":", *fm(dp[i + 1])[at - min(a[i], at):at + 1])
        # print(dpcnt, cnt)
    # cs = list(itertools.accumulate(dp[i], func=addmod)) + [0]
    cs = list(itertools.accumulate(dp[i])) + [0]
    cs = [mod(v) for v in cs]
    # print(*cs, "cs")
    # print(*dp[i], "dp")
    # print("-----")
print(dp[0][k] % M)

# for v in dp:
#     print(*fm(v))
a, b, c, k = [int(e) for e in input().split()]

import numpy as np

all = np.zeros(k)
all[:a] +=1
all[a+b:] -=1

print(sum(all))

### FIXED CODE ###

a, b, c, k = [int(e) for e in input().split()]

count=0

if k <= a:
    count +=k
elif k <= a+b:
    count +=a
else:
    count = 2*a + b - k

print(count)
N, K, Q = [int(e) for e in input().split()]
A = [0] * N

for index in range(Q):
    temp = int(input())
    A[temp - 1] += 1

for index in range(N):
    if A[index] > Q - K:
        print("Yes")
    else:
 

### FIXED CODE ###

N, K, Q =  map(int, input().split())
A = [0] * N

for index in range(Q):
    temp = int(input())
    A[temp - 1] += 1

for index in range(N):
    if A[index] > Q - K:
        print("Yes")
    else:
        print("No")
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,-1,-1):
    for j in range(W,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M,-1,-1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)

### FIXED CODE ###

N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(M+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,0,-1):
    for j in range(M,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)
for*_,i in sorted((t[:5],-int(t[-4:]),i)for i,t in enumerate(open(0)))[1:]:print(i)

### FIXED CODE ###

for *_,a in sorted([input().split()+[i]for i in range(int(input()))],key=lambda x:(x[0],-int(x[1]))):print(a+1)
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)

finished = set()
dfs(v,0,aoki)
finished = set()
path = []
pre_node = [0 for i in range(n+1)]
#最短炉を出す
search_path(u,v)
while v != u:
    path = [v] + path
    v = pre_node[v]
start = u
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set()
ans_path = [0 for i in range(n+1)]
dfs(start,0,ans_path)
ans = 0
for i in range(1,n+1):
    if aoki[i] > ans_path[i]:
        ans = max(ans, ans_path[i])
print(ans + aoki[start] - 1)


### FIXED CODE ###

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

n,u,v = map(int, input().split())
adjacent_list = [[] for i in range(n+1)]
aoki = [0 for i in range(n+1)]
takahashi = [0 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    global node_par
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            node_par[i] = node
            dfs(i, count + 1,li)
        
node_par = [0 for i in range(n+1)]

finished = set()
dfs(u,0,takahashi)

#辿って親保存しとく
finished = set()
dfs(v,0,aoki)

#さかのぼれるとこまで行く,startがさかのぼれる最大のノーど
par = u
start = u
while takahashi[par] < aoki[par]:
    start = par
    par = node_par[start]

ans_height = [0 for i in range(n+1)]
finished = set([node_par[start]])
dfs(start,0,ans_height)
print(max(ans_height) + aoki[start] - 1)
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) 
  c=factorial(n-k) 
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
 
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
 
H,W,A,B=map(int, input().split())
p=10**9+7
alls=comb(H+W-2,W-1,10**9+7)
for i in range(B):
  alls-=comb(H-A-1+i,H-A-1,p)*comb(W+A-2-i,A-1,p)
 
print(alls)

### FIXED CODE ###

N,K=map(int,input().split())
D=list(map(int,input().split()))
def solve():
  for i in range(10*N+2):
    if i>=N:
      s=str(i)
      for j in range(len(s)):
        if int(s[j]) in D: break
      else:
        print(i)
        return 0

solve()
a,b=(int(x) for x in input().split())
 
import math 
 
i=0
while i<10001:
  i++
  if math.float(i)==a and math.float(i)==b:
    print(i)
    break
else:
  print(-1)

### FIXED CODE ###

a,b=(int(x) for x in input().split())
 
import math 
 
i=0
while i<10001:
  i+=1
  if math.floor(i*0.08)==a and math.floor(i*0.1)==b:
    print(i)
    break
else:
  print(-1)
import sys
x = input()
y = input()
print x*y ,(x+y)*2

### FIXED CODE ###

a, b = map(int,raw_input().split())
print a*b, 2*(a+b)
import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, A = map(int, input().split())

    assert N <= 16

    x = [int(i) for i in input().split()]
    cnt = 0

    for i in range(1, 2**N):
        bs = bin(i)[2:].zfill(N)
        bitpop = bs.count('1')
        tmp = sum(x[i] for i, b in enumerate(bs) if b == '1')
        cnt += (tmp // bitpop == A and tmp % bitpop == 0)

    print(cnt)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, A = map(int, input().split())
    x = [int(i) for i in input().split()]

    # 3d DP
    max_x = max(x)

    dp = [[[0] * (max_x * N + 1) for j in range(N + 1)]
                                 for i in range(N + 1)]

    dp[0][0][0] = 1

    for i in range(0, N):
        for k in range(0, N + 1):
            for y in range(max_x * N + 1):
                if dp[i][k][y]:
                    dp[i + 1][k][y] += dp[i][k][y]
                    dp[i + 1][k + 1][y + x[i]] += dp[i][k][y]

            # print(dp[i][k])
        # print()

    cnt = 0
    for k in range(1, N + 1):
        for y in range(1, max_x * N + 1):
            if y // k == A and y % k == 0:
                cnt += dp[N][k][y]

    print(cnt)

if __name__ == '__main__':
    solve()