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

N = int(input())
S = input()

strs = []
for n in range(N):
    if S[n] not in strs:
        strs.append(S[n])
ans = 0
for x in strs:
    for n in range(N-1):
        if S[n] == x:
            for m in range(n+1, N):
                l = 0
                if S[m] == x:
                    l = 0
                    while l < m-n:
                        if S[n:n+l+1] != S[m:m+l+1]:
                            break
                        l += 1
                ans = max(ans, l)
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(N):
    k = ans + 1
    for j in range(k, N-i):
        if S[i:i+j] in S[i+j:]:
            ans = max(ans, j)
        else:
            break
print(ans)
### BUGGY CODE ###

n = int(input())
m = 0

for i in range(1,n):
    m += i
    
print(m)

### FIXED CODE ###

n = int(input())
m = (n-1)*n//2

print(m)
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,Q = [int(x) for x in input().split()]
S = list(input())
lrlist =[]
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    lrlist.append((l,r))

sumls =[0]*(N)
for i in range (N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        sumls[i] = 1
    else:
        sumls[i] = 0

for _ in range (Q):
    l = lrlist[_][0]
    r = lrlist[_][1]
    ans = sum(sumls[l-1:r-1])
    print(ans)






### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-

N,Q = [int(x) for x in input().split()]
S = list(input())
lrlist =[]
for _ in range(Q):
    l,r = [int(x) for x in input().split()]
    lrlist.append((l,r))

sumls =[0]*(N+1)
for i in range (N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        sumls[i+1] = sumls[i] + 1
    else:
        sumls[i+1] = sumls[i]

for _ in range (Q):
    l = lrlist[_][0]
    r = lrlist[_][1]
    ans = sumls[r-1]-sumls[l-1]
    print(ans)
### BUGGY CODE ###


N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)


### FIXED CODE ###

import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    if x < k: continue
    premin = sum(list[0 : x])
    premax = sum(list[n + 1 - x : n + 1])
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 1):
    premin += list[x]
    premax += list[n - x]
    if x < k - 1: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
x = N
while x > K/2:
  x = abs(K-x)
print(x)

### FIXED CODE ###

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

while x > K/2:
    x = abs(K-x)

print(x)
### BUGGY CODE ###

from time import*
from fractions import*
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    if time()-start>.7:
        s=max(a)
        break
    else:
        s=lcm(s,t)
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [a.index(i) for i in range(n)]
dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])



### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, ii])
    else:
        b.append([s, mi - s, ma - s, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in sss[heapq.heappop(heap)[-1]]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in reversed(sss[heapq.heappop(heap)[-1]]):
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


ok1(a)
ok(b)
print("Yes")


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok(a):
    s = 0
    for i, j, _, _ in a:
        if s + j < 0:
            print("No")
            exit()
        s += i

ok(a)
ok(b)
print("Yes")
### BUGGY CODE ###

import bisect

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

cnt = 0

for a in A:
    for b in B[bisect.bisect_left(B,a):]:
        for c in C [bisect.bisect_left(C,b):]:
            if a < b < c :
                cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
C = sorted(list(map(int,input().split())))

cnt = 0


for j in range(n) :
    a = bisect.bisect_left(A,B[j])
    c = bisect.bisect_right(C,B[j])
    cnt += a * (n-c)
    
print(cnt)
### BUGGY CODE ###

n,*p=map(int,open(0).read().split())
c=0
for i in range(n):
    if p[i]<=min(p[:i+1]):
        c+=1
print(c)

### FIXED CODE ###

n,*p=map(int,open(0).read().split())
c=0
min_p=p[0]
for i in range(n):
    min_p=min(min_p,p[i])
    if p[i]<=min_p:
        c+=1
print(c)
### BUGGY CODE ###

from itertools import accumulate

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


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)  # Binaryの先頭の分
lo, hi = -1, max(A) + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数を数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += j - BIT.sum(Binary_sorted[b])
        BIT.add(Binary_sorted[b], 1)

    # 転倒数の割合で分岐
    if inversion / (N * (N + 1) / 2) < 0.5:
        lo = X
    else:
        hi = X

print(lo)


### FIXED CODE ###

from itertools import accumulate
from math import ceil

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

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


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)  # Binaryの先頭の分
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2

    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]

    # 累積和をとる
    Binary = list(accumulate(Binary))

    # BITを初期化
    BIT.reset()

    # 転倒数っぽいものを数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)

    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X

print(lo)
### BUGGY CODE ###

N = input()
S = input()

R = []
G = []
B = []
i = 1
for c in S:
    if c == 'R':
        R.append(i)
    elif c == 'G':
        G.append(i)
    elif c == 'B':
        B.append(i)
    i += 1

ans = 0

for r in R:
    for g in G:
        for b in B:
            if abs(r-g) != abs(r-b) and abs(r-b) != abs(g-b) and abs(r-g) != abs(g-b):
                ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

rcnt = 0
gcnt = 0
bcnt = 0

for c in S:
    if c == 'R':
        rcnt += 1
    elif c == 'G':
        gcnt += 1
    elif c == 'B':
        bcnt += 1

ans = rcnt * gcnt * bcnt
for i in range(N):
    for j in range(i+1,N):
        k = 2 * j - i
        if k >= N:
            continue
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n,k=[int(x) for x in input().split()]
#Sequence decreases first then starts increasing.This point has to be identified.
prev,cur=n+1,n
if k<=0:
  print(n)
else:
  while cur<prev:
    prev = cur
    cur = abs(cur-k)
  print(prev)
  	

### FIXED CODE ###

n,k=[int(x) for x in input().split()]
#Sequence decreases first then starts increasing.This point has to be identified.
prev,cur=n+1,n
if k<=0:
  print(n)
else:
	rem = n%k
	print(min(rem,abs(rem-k)))
### BUGGY CODE ###

import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import collections as cl
import functools as ft
import numpy as np

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def count_lr(n, m, a):
    count = 0
    for l in range(n):
        for r in range(l, n):
            if not sum(a[l:r+1]) % m:
                count += 1
    return count


if __name__ == "__main__":
    n, m = LI()
    a = LI()

    print(count_lr(n, m, a))


### FIXED CODE ###

import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import collections as cl
import functools as ft
import numpy as np

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def count_lr_old(n, m, a):
    count = 0
    for l in range(n):
        for r in range(l, n):
            if not sum(a[l:r+1]) % m:
                count += 1
    return count


def count_lr(n, m, a):
    b_acm = 0
    mod_m_counts = {}
    for ai in a:
        b_acm = (b_acm + ai) % m
        mod_m_counts.setdefault(b_acm, 0)
        mod_m_counts[b_acm] += 1

    # print(mod_m_counts)

    # print('len a:', len(a))
    count = 0
    all_ = 0
    for k, v in mod_m_counts.items():
        all_ += v
        count += v * (v - 1) // 2
        if k == 0:
            count += v

    # print('all_', all_)
    return count


if __name__ == "__main__":
    n, m = LI()
    a = LI()

    print(count_lr(n, m, a))
### BUGGY CODE ###

import sys
import re
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
f = False
for l in range(n//2, 0, -1):
    for j in range(n):
        ptn = S[j:j+l]
        ptn = re.compile(ptn)
        result = ptn.findall(S)
        if len(result) >=2:
            print(len(result[0]))
            f = True
            break
    if f == True:
        break
else:
    print(0)

### FIXED CODE ###

import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, j-i)

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)
### BUGGY CODE ###

import math
import itertools
N=int(input())
for n in range(1,N+1):
    ans=0
    if n<=5:
        print(ans)
        continue
    X=math.floor(n**0.5)
    com=itertools.combinations_with_replacement(range(1,X+1),3)
    for x,y,z in com:
                if x**2 + y**2 + z**2 + x*y + y*z + x*z==n:
                    if (x==y and y!=z and z!=x) or (x!=y and y==z and z!=x) or (x!=y and y!=z and z==x): 
                        ans+=3
                    elif x==y and y==z and z==x:
                        ans+=1
                    else:
                        ans+=6
    print(ans)


### FIXED CODE ###

N = int(input())
ans = [0] * 100000
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###

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

ans=[]
for i in range(1, N+1):
    ans.append(1+A.index(i))

print(*ans, sep=" ")

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [[A[i], i+1] for i in range(N)]
B = sorted(B, key=lambda x:x[0])
print(*[B[i][1] for i in range(N)])
### BUGGY CODE ###

n,m=map(int, input().split())
a=sorted(map(int, input().split()), reverse=True)

while(m>0):
    a[0]=a[0]//2
    m-=1
    a=sorted(a,reverse=True)
print(sum(a))

### FIXED CODE ###

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

from heapq import heappush, heappop
hq=[]

for a_val in a:
    # heappopで最も小さい値が取り出されるため、(-1)をかけて入れる
    heappush(hq, -a_val)
for _ in range(m):
    heappush(hq, -(heappop(hq)//(-2)))
print(-sum(hq))
### BUGGY CODE ###

n = int(input())

for i in range(1, n+1):
    cnt = 0
    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                
                if i == ((x+y+z)**2 - z*(x+y) - (x*y)):
                    cnt += 1

    print(cnt)

### FIXED CODE ###

n = int(input())

ANS = [0] * (n+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp = (x + y + z)**2 - z*(x + y) - (x*y)
            if tmp > n: continue
            ANS[tmp] += 1

for ans in ANS[1:]:
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
ans,sums = 0,[0]*K
for i,pi in enumerate(map(int, input().split())):
  sums[i%K] = (pi+1)/2
  ans = max(ans, sum(sums))
print(ans)

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
ans = [0] + list(accumulate(map(lambda x: (int(x)+1)/2., input().split())))
print(max([y-x for x,y in zip(ans, ans[K:])]))
### BUGGY CODE ###

from collections import deque

H,W=map(int,input().split())
field=[]
spos=deque([])
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="#":
      spos.append((j,i))
  field.append(s)
  
dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans=-1
while spos:
  for _ in range(len(spos)):
    x,y=spos.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="#"
        spos.append((nx,ny))
  ans+=1

print(ans)


### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
field=[]
spos=deque([])
for i in range(H):
  s=list(input())
  for j in range(W):
    if s[j]=="#":
      spos.append((j,i))
  field.append(s)
  

dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans=-1
while spos:
  for _ in range(len(spos)):
    x,y=spos.popleft()
    for i in range(4):
      nx=x+dx[i]
      ny=y+dy[i]
      if nx<0 or nx>=W or ny<0 or ny>=H:
        pass
      elif field[ny][nx]==".":
        field[ny][nx]="#"
        spos.append((nx,ny))
  ans+=1

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

import numpy as np
N = int(input())
A_list = sorted(list(map(int, input().split())), reverse=True)

ar_list = [A_list[0]]
edge_list = [A_list[0]]
score = 0
for a in A_list[1:]:
    maxidx = np.argmax(edge_list)
    score += edge_list[maxidx]
    #print(edge_list, maxidx, score)
    edge_list[maxidx] = a
    edge_list.insert(maxidx, a)
    #print(edge_list)

print(score)
    

### FIXED CODE ###

import queue

N = int(input())
A_list = sorted(list(map(int, input().split())), reverse=True)

edge_que = queue.Queue()
edge_que.put(A_list[0])
score = 0
for i, a in enumerate(A_list[1:]):
    score += edge_que.get()
    edge_que.put(a)
    edge_que.put(a)
print(score)
### BUGGY CODE ###

big = 10**18
bad = False
n = int(input())
start = 1
numbs = list(map(int, input().split()))
for x in numbs:
	start *= x
if start > big:
	bad = True


print(-1) if bad else print(start)

### FIXED CODE ###

big = 10**18
n = int(input())
things = list(map(int, input().split()))
result = 1
good = True
if 0 in things:
	print(0)
else:
	for x in things:
		result *= x
		if result > big:
			print(-1)
			good = False
			break
	if good:
		print(result)
### BUGGY CODE ###

s = str(input())

sum = 0
while True:
    count = s.count('BW')
    if count > 0:
        sum += count
        s = s.replace('BW','WB')
    else:
        break
print(sum)

### FIXED CODE ###

s = list(str(input()))

sum = 0
bcount = 0
for i in range(len(s)):
    if s[i] == 'B' :
        bcount += 1
    else :
        sum += bcount

print(sum)
### BUGGY CODE ###

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

n, u, v = map(int, sys.stdin.readline().split())
a, b = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(-1, 2).T - 1
graph = csr_matrix(([1] * (n-1), (a, b)), (n, n))

def main():
    dist_u, dist_v = dijkstra(graph, directed=False, indices=[u-1, v-1])
    
    ans = np.amax(dist_v[dist_v >= dist_u]) - 1
    return int(ans)

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)


def main():
    dist_u = [None] * (n + 1)
    dist_u[u] = 0
    stack = [u]

    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_u[y] is None:
                dist_u[y] = dist_u[x] + 1
                stack.append(y)

    dist_v = [None] * (n + 1)
    dist_v[v] = 0
    stack = [v]
    contain_v = [False] * (n + 1)
    contain_v[v] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_v[y] is None:
                dist_v[y] = dist_v[x] + 1
                stack.append(y)

    d = 1
    for i in range(1, n+1):
        if dist_v[i] >= dist_u[i]:
            d = max(d, dist_v[i])
    ans = d - 1
    return ans

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

a,b,c,k=map(int,input().split())
value=[]
for i in range(a):
  value.append(1)
for i in range(b):
  value.append(0)
for i in range(c):
  value.append(-1)
sum=0
for i in range(k):
  sum+=value[i]
print(sum)

### FIXED CODE ###

a,b,c,k=map(int,input().split())
if k<=a:
  print(k)
elif k<=a+b:
  print(a)
elif k<=a+b+c:
  print(a-(k-(a+b)))