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

def main():
    from itertools import permutations

    n, m, r, *x = map(int, open(0).read().split())
    to = x[:r]

    dis = [[float("Inf")] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dis[i][i] = 0

    for a, b, c in zip(*[iter(x[r:])] * 3):
        dis[a][b] = c
        dis[b][a] = c

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

    ans = float("Inf")
    done = []
    for p in permutations(to, r):
        tmp = 0
        if list(p) in done:
            continue
        q = list(p)
        done.append(sorted(q))
        for i, j in zip(p, p[1:]):
            tmp += dis[i][j]
        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
from itertools import permutations
def main():
    def warshall_floyd(d):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
 
    n, m, r = map(int, input().split())
    rs = tuple(map(int, input().split()))
    d = [[10**9] * n for _ in range(n)]
    m = map(int, read().split())
    mmm = zip(m, m, m)
    for s, t, dis in mmm:
        s -= 1
        t -= 1
        d[t][s] = d[s][t] = dis
    for j1 in range(n):
        d[j1][j1] = 0
    res = warshall_floyd(d)
    rsp = tuple(permutations(rs))
    result = float('inf')
    for rspe in rsp:
        res_t = 0
        for i1 in range(r - 1):
            res_t += res[rspe[i1]-1][rspe[i1+1]-1]
        result = min(result, res_t)
    print(result)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###


def bisect(a,A,lo,hi):
    if hi-lo==1:
        return hi
    if A[(hi+lo)//2]>=a:
        return bisect(a,A,(hi+lo)//2,hi)
    else:
        return bisect(a,A,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else:
            B[bisect(A[i],B,0,len(B)-1)]=A[i]

print(len(B))

### FIXED CODE ###


def bisect(a,B,lo,hi):
    if hi-lo<=1:
        return hi
    elif B[(hi+lo)//2]>=a:
        return bisect(a,B,(hi+lo)//2,hi)
    else:
        return bisect(a,B,lo,(hi+lo)//2)

N = int(input())

A = [int(input()) for i in range(N)]

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else: 
            B[bisect(A[i],B,0,len(B)-1)]=A[i]
print(len(B))
### BUGGY CODE ###

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

for _ in range(K):
  B = [0] * (N+1)
  for i in range(N):
    l = max(0, i-A[i])
    r = min(i+A[i]+1, N)
    B[l] += 1
    B[r] -= 1

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

  if B[:-1] == A: break
  A = B

for i in range(N):
  print(A[i])


### FIXED CODE ###

from itertools import accumulate

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

for _ in range(K):
  arr = [0]*(N+1)
  for i, a in enumerate(A):
    left = max(0, i-a)
    right = min(N, i+a+1)
    arr[left] += 1
    arr[right] -= 1
  
  A = list(accumulate(arr[:-1]))
  if all(a == N for a in A):
    break

print(*A, sep=" ")
### BUGGY CODE ###

from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0

@lru_cache(maxsize=None)
def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now+d
        next = now + d
        prevy, prevx = pos[now-1][1], pos[now-1][2]
        nexty, nextx = pos[next-1][1], pos[next-1][2]
        ans += (abs(nexty - prevy) + abs(nextx - prevx))
    return ans

for pr, ne in way:
    print(solve(pr, ne))

### FIXED CODE ###

from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = time[l] + (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return time[en-1] - time[st-1]


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))
### BUGGY CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)

### FIXED CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)
### BUGGY CODE ###

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def same(self, x, y):  # x,yが同じ集合に属するか判定する
		return self.find(x) == self.find(y)

	def group_size(self, x):  # xが属する集合の大きさを返す
		return self.size[self.find(x)]

N, M = map(int, input().split())
X, Y, Z = [0] * M, [0] * M, [0] * M
for i in range(M):
	X[i], Y[i], Z[i] = map(int, input().split())

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

ans = 0
root = []
for k in range(N):
	tmp = uf.find(k)
	if tmp not in root:
		ans += 1
		root.append(tmp)
print(ans)


### FIXED CODE ###

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

	def find(self, x):  # xの親を返す
		if self.par[x] == x:
			return x
		else:
			return self.find(self.par[x])

	def unite(self, x, y):  # x,yの属する集合をマージする
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

N, M = map(int, input().split())
X, Y, Z = [0] * M, [0] * M, [0] * M
for i in range(M):
	X[i], Y[i], Z[i] = map(int, input().split())

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

roots = set([])
for k in range(N):
	roots.add(uf.find(k))
print(len(roots))
### BUGGY CODE ###

import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]

d = defaultdict(int)
ans = 0

def paint(str, ptn):
  red = ''.join(s for i, s in enumerate(str) if 2**i & ptn)
  blue = ''.join(s for i, s in enumerate(str) if not 2**i & ptn)
  return (red, blue)

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]
  
print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]

d = defaultdict(int)
ans = 0

def paint(str, ptn):
  p = ['', '']
  for i in range(N):
    p[int(2**i & ptn > 0)] += str[i]
  return tuple(p)

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]
  
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
b=[]
count=0
count_1=0

for i in range(M):
    if ps[i][1]=="AC" and ps[i][0] not in a:
        a.append(ps[i][0])

for j in range(M):
    if ps[j][0] not in a:
        pass
    elif ps[j][0] not in b:
        if ps[j][1]=="WA":
            count+=1
        elif ps[j][1]=="AC":
            b.append(ps[j][0])

print(len(a),count)


### FIXED CODE ###

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

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

from itertools import *
N = int(input())
A = list(map(int,input().split()))
ans = 0
a = combinations(range(N),2)
for i in a:
    ans += A[i[0]] * A[i[1]]

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
s = [0]
for i in range(N):
    s.append(s[i] + A[i])
ans = 0
for i in range(N):
    ans += A[i] * (s[N] - s[i + 1])
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

a,b,n=map(int ,input().split())
val=0
for x in range(n+1):
    tmp_val=int(a*x/b)-a*int(x/b)
    val=max(tmp_val,val)
print(val)

### FIXED CODE ###

A,B,N=map(int,input().split())
if(N>=B-1):
    x=B-1
if(N<B-1):
    x=N
ans=int(A*x/B)-A*int(x/B)
print(ans)
### BUGGY CODE ###

import math

N = int(input())
a = list(map(int,input().split()))
a_odds = []
a_even = []

for i in range(N):
    if a[i]%2 != 0:
        a_odds.append(a[i])
    else:
        a_even.append(a[i])

a_odds.sort()
a_odds.reverse()
a_even.sort()
a_even.reverse()

count = 0
alist = []
num= 0
if a_odds!=[] and a_even!=[]:
    num = max(a_odds[0],a_even[0])
elif a_odds ==[]:
    num= a_even[0]
elif a_even == []:
    num = a_odds[0]
    
for i in range(round(math.log2(num))+1,0,-1):
    alist.append(2**i)


while(a_odds!=[]):
    temp = a_odds[0]
    a_odds.pop(0)
    if a_odds ==[]:
        break
    for i in alist:
        b = i-temp
        if (i-temp) in a_odds:
            count += 1
            a_odds.pop(a_odds.index(i-temp))
            break
    
    
while(a_even!=[]):
    temp = a_even[0]
    a_even.pop(0)
    if a_even==[]:
        break
    for i in alist:
        if (i-temp) in a_even:
            count += 1
            a_even.pop(a_even.index(i-temp))
            break
    

print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)
### BUGGY CODE ###

import sys

def main():
    ans = [input()]
    n = int(input())
    vec = 1
    for i in range(n):
        q = sys.stdin.readline().rstrip()
        if q == "1":
            vec *= -1
        else:
            if ((q[2] == "1") and (vec == 1)) or ((q[2] == "2") and (vec == -1)):
                ans.insert(0, q[4])
            else:
                ans.append(q[4])
    ans = ''.join(ans)
    if vec == -1:
        ans = ans[::-1]
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

def main():
    ans = deque(input())
    n = int(input())
    vec = 1
    for i in range(n):
        q = input()
        if q == "1":
            vec *= -1
        else:
            _,o,s = q.split()
            if ((o == "1") and (vec == 1)) or ((o == "2") and (vec == -1)):
                ans.appendleft(s)
            else:
                ans.append(s)
    if vec == -1:
        ans.reverse()
    ans = ''.join(ans)
    print(ans)

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

As, Bs, Ms = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

mm = [[0 for i in range(Bs)] for j in range(As)]
for i in range(Ms):
  a, b, c = map(int, input().split())
  if c > mm[a-1][b-1]:
    mm[a-1][b-1] = c

ans = 1000000
for i,a in enumerate(A):
  for j,b in enumerate(B):
    if ans > a+b-mm[i][j]:
      ans = a+b-mm[i][j]
print(ans)

### FIXED CODE ###

As, Bs, Ms = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

bas = min(A) + min(B)

ans = bas
for i in range(Ms):
  a, b, c = map(int, input().split())
  if A[a-1]+B[b-1]-c < ans:
    ans = A[a-1]+B[b-1]-c

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

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

odd = False
count = 0

while True:
    for i in A:
        if i%2 != 0:
            odd = True

    if odd:
        break

    for i in A:
        i = int(i/2)

    count += 1

print(count)


### FIXED CODE ###

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

count = -1
flag = True

while flag == True:
    count += 1
    for i in range(N):
        if A[i]%2 == 0:
            A[i] /= 2

        else:
            flag = False
            break



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

N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: format(x, '0b').zfill(60), A))

p = int(1e9+7)
res = 0
d = [0]*60

for a in A:
    for i in range(60):
        d[i] += int(a[i])

for i, d in enumerate(d[::-1]):
    res += d*(N-d)*2**i
    res %= p

print(res)

### FIXED CODE ###

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

p = int(1e9+7)
res = 0

for i in range(60):
    zc = 0
    oc = 0
    for j in range(len(A)):
        if A[j] % 2 == 0:
            zc += 1
        else:
            oc += 1
        A[j] = A[j] >> 1

    res += zc*oc*2**i
    res %= p

print(res)
### BUGGY CODE ###

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

''' ?????? '''


class Dictionary(object):
    """ Dictionary """

    def __init__(self):
        self.dict = []

    def insert(self, x):
        self.dict.append(x)

    def find(self, x):
        if x in self.dict:
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    N = int(input())

    d = Dictionary()

    for _ in range(N):
        command, key = list(input().split())
        if command == 'insert':
            d.insert(key)
        elif command == 'find':
            d.find(key)

### FIXED CODE ###

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

''' ?????? '''


class Dictionary(object):
    """ Dictionary """

    def __init__(self):
        self.dict = {}

    def insert(self, x):
        self.dict[x] = 0

    def find(self, x):
        if x in self.dict.keys():
            print('yes')
        else:
            print('no')

if __name__ == '__main__':
    N = int(input())

    d = Dictionary()

    for _ in range(N):
        command, key = list(input().split())
        if command == 'insert':
            d.insert(key)
        elif command == 'find':
            d.find(key)
### BUGGY CODE ###

import heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]
h.sort()
p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**18
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)

### FIXED CODE ###

import heapq
n,a,b= map(int,input().split())
h =[int(input()) for i in range(n)]

p = a-b
def c(w):
    #w de umakuikkuka
    k = 0
    for i in range(n):
        l[i] = l[i]-b*w
        if l[i] > 0:
            k += l[i]//p
            if l[i] % p != 0:
                k += 1
    if w >= k:
        return True

s = 0
f = 10**9
while f-s >=2:
    m = (f+s)//2
    l = h[::]
    if c(m):
        f = m
    else:
        s = m
l = h[::]
if c(s):
    print(s)
else:
    print(f)
### BUGGY CODE ###

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

for num in range(0, K):
  if A > 0:
    A -= 1
  elif B > 0:
    B -= 1
print(A, B)

### FIXED CODE ###

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

if A < K:
  K -= A
  A = 0
else:
  A -= K
  K = 0
  
if B < K:
  K -= B
  B = 0
else:
  B -= K
  K = 0

print(A, B)
### BUGGY CODE ###

n,m = map(int,input().split())
l = list(list(map(int,input().split())) for _ in range (m))
p = set(i for i in range(1,n+1))
for i in l:
  s,t = i
  a = set(q for q in range(s,t+1))
  p = p&a
print(len(p))

### FIXED CODE ###

n,m = map(int,input().split())
l = list(list(map(int,input().split())) for _ in range (m))
a = l[0][0]
b = l[0][1]
for s,t in l:
  a = max(a,s)
  b = min(b,t)
print(max(b-a+1,0))
### BUGGY CODE ###

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


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    AB = [tuple(map(int, input().split())) for _ in range(M)]

    result = 0

    for i in range(N):
        arr = []
        for ab in AB:
            if i + 1 in ab:
                arr.extend(ab)
        H_list = [H[a - 1] for a in set(arr)]
        if H_list == []:
            result += 1
        elif H[i] == max(H_list)and H_list.count(H[i]) == 1:
            result += 1

    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    result = [1] * N

    for i in range(M):
        a, b = map(int, input().split())
        if H[a - 1] <= H[b - 1]:
            result[a - 1] *= 0
        if H[a - 1] >= H[b - 1]:
            result[b - 1] *= 0
    print(result.count(1))


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

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

ans=0
for i in a_uniq:
  if a.count(i)>i:
    ans+=a.count(i)-i
  elif a.count(i)<i:
    ans+=a.count(i)

print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dict={}
for i in a:
  if i not in dict:
    dict[i]=1
  else:
    dict[i]+=1

ans=0
for i in dict.keys():
  count=dict[i]
  if count>i:
    ans+=count-i
  elif count<i:
    ans+=count

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

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


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

is_leaf = [0]*n
def dfs(c,p,d):
    dep[c] = d
    f = True
    for to in G[c]:
        if to != p:
            dfs(to, c, d+1)
            f = False
    if f:
        is_leaf[c] = 1


dep = [0]*n
dfs(v, -1, 0)
a = dep[:]
leaf = is_leaf[:]
dfs(u, -1, 0)
b = dep

ans = 0
for i in range(n):
    if not leaf[i]:
        continue
    if b[i] >= a[i]:
        continue
    tmp = 0
    d = b[i]
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = a[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)

### FIXED CODE ###

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

from collections import deque

def main():
    n, u, v = map(int, input().split())
    u, v = u-1, v-1
    G = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int, input().split())
        a,b = a-1,b-1
        G[a].append(b)
        G[b].append(a)

    def bfs(start):
        dist = [0]*n
        is_leaf = [0]*n
        que = deque()
        que.append((start, -1, 0))
        while que:
            c,p,d = que.pop()
            dist[c] = d
            cnt = 0
            for to in G[c]:
                if to != p:
                    que.append((to,c,d+1))
                    cnt += 1
            if not cnt:
                is_leaf[c] = 1
        return dist, is_leaf

    a, is_leaf = bfs(v)
    b, _ = bfs(u)

    ans = 0
    for i in range(n):
        if not is_leaf[i]:
            continue
        if b[i] >= a[i]:
            continue
        tmp = 0
        d = b[i]
        if d != 0:
            tmp = 2*d
            aoki = d
        else:
            aoki = 0
        tak = a[i]
        m = tak-aoki
        if m%2==1:
            tmp += 2*m -1
        else:
            tmp += 2*(m-1)
        ans = max(ans, tmp)
    print(ans//2)

if __name__ == "__main__":
    main()