Problem:
 Score : 600 points    Problem Statement We have a tree with N vertices. The i -th edge connects Vertex A_i and B_i bidirectionally.  Takahashi is standing at Vertex u , and Aoki is standing at Vertex v .  Now, they will play a game of tag as follows:    1 . If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.    2 . If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.    3 . Go back to step 1 .    Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.  Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.  It can be proved that the game is bound to end.      Constraints  2 \leq N \leq 10^5  1 \leq u,v \leq N  u \neq v  1 \leq A_i,B_i \leq N  The given graph is a tree.         Input Input is given from Standard Input in the following format:  N  u  v  A_1  B_1  :  A_{N-1}  B_{N-1}       Output Print the number of moves Aoki will perform before the end of the game.        Sample Input 1 5 4 1
1 2
2 3
3 4
3 5      Sample Output 1 2  If both players play optimally, the game will progress as follows:   Takahashi moves to Vertex 3 .  Aoki moves to Vertex 2 .  Takahashi moves to Vertex 5 .  Aoki moves to Vertex 3 .  Takahashi moves to Vertex 3 .   Here, Aoki performs two moves.  Note that, in each move, it is prohibited to stay at the current vertex.       Sample Input 2 5 4 5
1 2
1 3
1 4
1 5      Sample Output 2 1       Sample Input 3 2 1 2
1 2      Sample Output 3 0       Sample Input 4 9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9      Sample Output 4 5

Solution (Python):
from collections import deque
 
N,u,v=map(int,input().split())
G=[[] for _ in range(N)]
for _ in range(N-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
 
def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)
 
print(max([d2[i] for i in range(N) if d1[i]<=d2[i]])-1)

Solution (Python):
"""
高橋君はとりあえず、青木君から最も遠い木の端を目指すのがベスト。
また、目指すべき木の端までの距離に関しては、高橋くんよりも自分の方が近くなくてはならない。
また、高橋君が捕まるときは、必ず木の端の一歩手前のノードになる。
つまり、青木君が移動しなくてはいけない最大距離は、高橋君が目指す木の端までの距離-1、ということになる。
とりま、高橋くん、青木君の初期位置から各ノードまでの距離を調べて、上記の条件にマッチする端を見つける。
"""
from collections import deque
N,u,v = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

takahashi = [None]*(N+1)
que = deque([(0,u,0)])
while que:
    step,cur,par = que.popleft()
    takahashi[cur] = step
    for nx in edges[cur]:
        if nx == par:
            continue
        que.append((step+1,nx,cur))

aoki = [None]*(N+1)
que = deque([(0,v,0)])
while que:
    step,cur,par = que.popleft()
    aoki[cur] = step
    for nx in edges[cur]:
        if nx == par:
            continue
        que.append((step+1,nx,cur))
ans = 0
for i in range(1,N+1):
    if takahashi[i] < aoki[i]:
        ans = max(ans,aoki[i]-1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
I=lambda:int(input())
MI=lambda:map(int,input().split())
LI=lambda:list(map(int,input().split()))
from collections import deque

res=0
INF=10**9


N,u,v=MI()
G=[[] for _ in [0]*(N+1)]
for i in range(N-1):
    a,b=MI()
    G[a].append(b)
    G[b].append(a)


def bfs(a):
    q=deque()
    q.append(a)
    d=[INF]*(N+1)
    d[a]=0
    res=0
    while q:
        r=q.popleft()
        for nr in G[r]:
            if d[nr]==INF:
                q.append(nr)
                d[nr]=d[r]+1
                res+=1
    return d

aoki=bfs(v)
taka=bfs(u)

m=0
for i in range(1,N+1):
    if taka[i]<aoki[i]:
        m=max(aoki[i],m)
print(m-1)

Solution (Python):
from collections import defaultdict, deque

N, u, v = map(int, input().split())
G = defaultdict(lambda: [])

for _ in range(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)


if G[u] == [v]:
    print(0)
    exit()


def bfs(v):
    seen = [0]*(N+1)
    queue = deque()
    dist = [-1]*(N+1)
    dist[v] = 0
    seen[v] = 1
    queue.append(v)
    while queue:
        q = queue.popleft()
        for nx in G[q]:
            if seen[nx]:
                continue
            dist[nx] = dist[q] + 1
            seen[nx] = 1
            queue.append(nx)
    return dist

d_u = bfs(u)
d_v = bfs(v)
ans = 0
for node in range(1, N+1):
    if d_u[node] < d_v[node] and len(G[node]) == 1:
        ans = max(ans, d_v[node]-1)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n, u, v = map(int,input().split())
    if u == v:
        print(0)
        sys.exit()

    graph = [[] for _ in range(n)]
    depth_u = [-1] * (n) 
    depth_v = [-1] * (n) 
    u -= 1 
    v -= 1 
    for i in range(n-1):
        a, b = map(int,input().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    
    
    queue = deque([u])
    visited = [False]*n
    visited[u] = True
    depth_u[u] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_u[xnode] = depth_u[node] + 1
                queue.append(xnode)
    
    queue = deque([v])
    visited = [False]*n
    visited[v] = True
    depth_v[v] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_v[xnode] = depth_v[node] + 1
                queue.append(xnode)
    ans = 0
    max_d_v = 0
    for i in range(n):
        if depth_u[i] < depth_v[i]:
            max_d_v = max(max_d_v, depth_v[i])
    print(max_d_v - 1)



if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n, u, v = map(int,input().split())
    if u == v:
        print(0)
        sys.exit()

    graph = [[] for _ in range(n)]
    depth_u = [-1] * (n) 
    depth_v = [-1] * (n) 
    u -= 1 
    v -= 1 
    for i in range(n-1):
        a, b = map(int,input().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    
    
    queue = deque([u])
    visited = [False]*n
    visited[u] = True
    depth_u[u] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_u[xnode] = depth_u[node] + 1
                queue.append(xnode)
    
    queue = deque([v])
    visited = [False]*n
    visited[v] = True
    depth_v[v] = 0
    while queue:
        node = queue.popleft()
        for xnode in graph[node]:
            if not visited[xnode]:
                visited[xnode] = True
                depth_v[xnode] = depth_v[node] + 1
                queue.append(xnode)
    ans = 0
    max_d_v = 0
    for i in range(n):
        if depth_u[i] < depth_v[i]:
            max_d_v = max(max_d_v, depth_v[i])
    print(max_d_v - 1)



if __name__=='__main__':
    main()

Solution (Python):
n,u,v=map(int,input().split())
ki=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  ki[a].append(b)
  ki[b].append(a)

dn=[len(ki[i]) for i in range(n)]
inf=float('inf')
dt=[inf]*n
da=[inf]*n
u,v=u-1,v-1
from collections import deque
todo=deque([u])
dt[u]=0
while todo:
  x=todo.popleft()
  for nx in ki[x]:
    if dt[nx]>dt[x]+1:
      dt[nx]=dt[x]+1
      todo.append(nx)
todo=deque([v])
da[v]=0
while todo:
  x=todo.popleft()
  for nx in ki[x]:
    if da[nx]>da[x]+1:
      da[nx]=da[x]+1
      todo.append(nx)
ans=0
for i in range(n):
  if dn[i]>1 and dt[i]<=da[i]:ans=max(ans,da[i])
print(ans)
exit()
print(dn)
print(dt)
print(da)

Solution (Python):
from collections import deque
n, u, v = map(int, input().split())
u -= 1
v -= 1
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
def bfs(u):
    visited = [-1] * n
    Q = deque()
    visited[u] = 0
    Q.append(u)
    while Q:
        p = Q.popleft()
        for v in edges[p]:
            if visited[v] == -1:
                visited[v] = visited[p] + 1
                Q.append(v)
    return visited
tak_dist = bfs(u)
aok_dist = bfs(v)
ans = []
for i in range(n):
    if tak_dist[i] < aok_dist[i]:
        ans.append(aok_dist[i])
print(max(ans) - 1)

Solution (Python):
N, u, v = map(int, input().split())
u, v = u-1, v-1

ABs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]


roots = [[] for _ in range(N)]

for AB in ABs:
    roots[AB[0]].append(AB[1])
    roots[AB[1]].append(AB[0])


def BFS(roots, start):
    from collections import deque
    seen = [-1 for _ in range(N)]
    seen[start] = 0
    todo = deque([start])
    while len(todo) > 0:
        checking = todo.pop()
        for root in roots[checking]:
            if seen[root] == -1:
                seen[root] = seen[checking] +1
                todo.append(root)
    return seen

from_u = BFS(roots, u)
from_v = BFS(roots, v)

from collections import deque
todo = deque([u])
max_distance = from_v[u]
position = u
seen = [False for _ in range(N)]
seen[u] = True
while len(todo) > 0:
    checking = todo.pop()
    for root in roots[checking]:
        if from_u[root] < from_v[root] and seen[root] == False:
            seen[root] = True
            todo.append(root)

            if max_distance < from_v[root]:
                max_distance = from_v[root]
                position = root
            
print(max_distance-1)

Solution (Python):
from collections import deque

N,u,v = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

distA = {}
que = deque([(u,0)])
while que:
    n,step = que.popleft()
    if n not in distA:
        distA[n] = step
        for nx in edges[n]:
            que.append((nx,step+1))

distB = {}
que = deque([(v,0)])
while que:
    n,step = que.popleft()
    if n not in distB:
        distB[n] = step
        for nx in edges[n]:
            que.append((nx,step+1))
ans = 0
for i in range(1,N+1):
    dist = distB[i]-distA[i]
    if dist > 0:
        ans = max(ans,distB[i]-1)
print(ans)

Solution (Python):
import sys
from collections import deque


def main():
    N, p, q, *AB = map(int, sys.stdin.buffer.read().split())
    p -= 1
    q -= 1

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

    if len(G[p]) == 1 and G[p][0] == q:
        print(0)
        return

    dist1 = [-1] * N
    dist1[p] = 0
    queue = deque([p])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                queue.append(nv)

    dist2 = [-1] * N
    dist2[q] = 0
    queue = deque([q])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                queue.append(nv)

    max_d = 0
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_d < d2:
            max_d = d2

    print(max_d - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, p, q, *AB = map(int, read().split())
    p -= 1
    q -= 1

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

    if len(G[p]) == 1 and G[p][0] == q:
        print(0)
        return

    dist1 = [-1] * N
    dist1[p] = 0
    queue = deque([p])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                queue.append(nv)

    dist2 = [-1] * N
    dist2[q] = 0
    queue = deque([q])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                queue.append(nv)

    max_d = 0
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_d < d2:
            max_d = d2

    print(max_d - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, ta, ao, *AB = map(int, read().split())
    ta -= 1
    ao -= 1

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

    dist_ta = [-1] * N
    dist_ta[ta] = 0
    queue = deque([ta])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ta[nv] == -1:
                dist_ta[nv] = dist_ta[v] + 1
                queue.append(nv)

    dist_ao = [-1] * N
    dist_ao[ao] = 0
    queue = deque([ao])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist_ao[nv] == -1:
                dist_ao[nv] = dist_ao[v] + 1
                queue.append(nv)

    d_ao = 0
    for d1, d2 in zip(dist_ta, dist_ao):
        if d1 < d2 and d_ao < d2:
            d_ao = d2

    if d_ao == 0:
        if dist_ta[ao] == 1:
            print(0)
        else:
            print(1)

    print(d_ao - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)

    ans = 0
    for v in sorted(du.keys()):
        if du[v] < dv[v]:
            ans = max(ans, dv[v] - 1)

    return ans


def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)


    ans = 0
    for v in sorted(du.keys()):
        if du[v] < dv[v]:
            ans = max(ans, dv[v] - 1)

    return ans


def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    s = [U]
    prev = {}
    prev[U] = -1
    while s:
        u = s.pop()
        for v in g[u]:
            if v in prev:
                continue
            prev[v] = u
            s.append(v)

    p = [V]
    v = V
    while v != U:
        v = prev[v]
        p.append(v)
    p.reverse()
    nu = p[len(p)//2-1]
    ans = len(p)//2-1
    if len(p) % 2 == 1:
        ans += 1

    done = set(p[len(p)//2-1:])

    d = {nu: 0}
    s = [nu]
    while s:
        u = s.pop()
        for v in g[u]:
            if v in done:
                continue
            d[v] = d[u] + 1
            done.add(u)
            s.append(v)

    return ans + max(d.values())





def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, u, v = read_values()
    u -= 1
    v -= 1
    F = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = read_index()
        F[a].add(b)
        F[b].add(a)

    D = [-1] * N
    S = deque()
    S.append((0, v))
    D[v] = 0
    while S:
        c, p = S.popleft()
        for q in F[p]:
            if D[q] != -1:
                continue
            D[q] = c + 1
            S.append((c + 1, q))

    E = [-1] * N
    S.append((0, u))
    E[u] = 0
    while S:
        c, p = S.popleft()
        for q in F[p]:
            if E[q] != -1  or D[q] < c + 1:
                continue
            E[q] = c + 1
            S.append((c + 1, q))
    
    res = 0
    for i in range(N):
        if E[i] < 0:
            continue
        res = max(res, D[i])
    print(res - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
最初から高橋くんが葉にいる&その隣接に青木くん，というパターン以外は
葉の1個手前で終わるかな，
ある点に対しての距離を見ればいい，ゴールがそこなら青木くんはそこに最短で行くので．
ある点が青木くんよりの場合，そこはゴールにならない
"""
def main():

    
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        


        class Edge():
            

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            
            self.inf=10**20
            self.G = [[] for _ in range(V)] 
            self. _E = 0 
            self._V = V 

        
        def E(self):
            return self._E

        
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * self.V()

            
            

            d[s] = 0
            heapq.heappush(que,(0,s)) 

            while len(que)!=0:
                
                cost,v = heapq.heappop(que)

                
                if d[v] < cost:
                    continue

                
                for i in range(len(self.G[v])):
                    e = self.G[v][i] 
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost 

                        
                        

                        heapq.heappush(que,(d[e.to],e.to)) 

            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            

            return d
    
    mod=10**9+7
    N,u,v=MI()
    u-=1
    v-=1
    
    dim=[0]*N
    adj=[[]for _ in range(N)]
    
    djk=Dijkstra(N)
    for _ in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        djk.add2(a,b,1)
        dim[a]+=1
        dim[b]+=1
        adj[a].append(b)
        adj[b].append(a)
        
    if dim[u]==1:
        if adj[u][0]==v:
            print(0)
            exit()
            
    L=[]
    for i in range(N):
        if dim[i]==1:
            L.append(adj[i][0])
        
    ans=0
    lt=djk.shortest_path(u)
    la=djk.shortest_path(v)
    
    for i in L:
        if lt[i]<=la[i]:
            ans=max(ans,la[i])
            
    print(ans)
            
            
    

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

N, u, v = map(int, input().split())
u -= 1
v -= 1
Tree = [[] for _ in range(N)]

for _ in range(N-1):
  A, B = map(lambda x:int(x)-1, input().split())
  Tree[A].append(B)
  Tree[B].append(A)


path = []
def connected(v, tv, p=-1):
  if v == tv:
    return True
  for w in Tree[v]:
    if w == p:
      continue
    elif connected(w, tv, v):
      path.append(w)
      return True
  return False

connected(v, u)
path.append(v)




def dfs(v, p):
  d = -1
  for w in Tree[v]:
    if w == p:
      continue
    else:
      d = max(d, dfs(w, v))
  return d + 1

dist = len(path)
mid = path[dist//2 - 1]
par = path[dist//2]
ans = dfs(mid, par)

print(ans + (dist-1)//2)

Solution (Python):
from collections import deque

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d
  
d1 = bfs(u-1)
d2 = bfs(v-1)

print(max([d2[i] for i in range(N) if d1[i]<=d2[i]])-1)

Solution (Python):
"""
シミュレートしてみればわかるが、高橋君は青木君よりも自分の方が近いようなノードのうち、青木君から最も遠いノードに向かって逃げるのが最善手。
そのようなノードをXとおくと、青木君と高橋君が鉢合わせるノードはXの一つ手前のノードになる。
したがって、青木君が動かす手の数はXまでの手数-1となる。
"""
from collections import deque
N,u,v = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)

takahashiDist = [None]*(N+1)
que = deque([(u,0)])
while que:
    n,step = que.popleft()
    takahashiDist[n] = step
    for nx in edges[n]:
        if takahashiDist[nx] == None:
            que.append((nx,step+1))


aokiDist = [None]*(N+1)
que = deque([(v,0)])
while que:
    n,step = que.popleft()
    aokiDist[n] = step
    for nx in edges[n]:
        if aokiDist[nx] == None:
            que.append((nx,step+1))
ans = 0
for i in range(1,N+1):
    if aokiDist[i] > takahashiDist[i]:
        ans = max(ans,aokiDist[i]-1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,u,v=map(int, input().split())
u-=1
v-=1
es=[[] for i in range(n)]
for i in range(n-1):
    a0,b0=map(int, input().split())
    es[a0-1].append(b0-1)
    es[b0-1].append(a0-1)
aoki=[-1]*n
aoki[v]=0
choku=[-1]*n
choku[u]=0
from collections import deque
que=deque([])
que.append(u)
while que:
    now=que.popleft()
    step=choku[now]
    for e in es[now]:
        if choku[e]==-1:
            choku[e]=step+1
            que.append(e)

que=deque([])
que.append(v)
while que:
    now=que.popleft()
    step=aoki[now]
    for e in es[now]:
        if aoki[e]==-1:
            aoki[e]=step+1
            que.append(e)

end=None
for i in range(n):
    if len(es[i])==1: 
        if choku[i]==0 and aoki[i]==1:
            print(0)
            exit()
        elif end==None and aoki[i]>choku[i]:
            end=(i, aoki[i])
        elif aoki[i]>choku[i] and end[1]<aoki[i]:
            end=(i, aoki[i])
print(end[1]-1)

Solution (Python):
N, u, v = map(int, input().split())
u -= 1
v -= 1
tonari = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tonari[a].append(b)
  tonari[b].append(a)

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0

now = [v] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit



now = [u] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] <= d: 
        continue
      elif d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit


distance = []
ans = 0
for U, V in zip(d_from_u, d_from_v):
  if U < N+1: 
    ans = max(ans, V-1)
print(ans)

Solution (Python):
N, u, v = map(int, input().split())
u -= 1
v -= 1
tonari = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tonari[a].append(b)
  tonari[b].append(a)

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0

now = [v] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit



now = [u] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] <= d: 
        continue
      elif d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit


distance = []
ans = 0
for U, V in zip(d_from_u, d_from_v):
  if U < N+1: 
    ans = max(ans, V-1)
print(ans)

Solution (Python):
N, u, v = map(int, input().split())
u -= 1
v -= 1
tonari = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tonari[a].append(b)
  tonari[b].append(a)

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0

now = [v] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit



now = [u] 
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] <= d: 
        continue
      elif d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit


distance = []
for U, V in zip(d_from_u, d_from_v):
  if U < N+1: 
    distance.append((U, V))

if distance:
  ans = max(distance, key= lambda x: x[1])[1] - 1
else:
  ans = 0
print(ans)

Solution (Python):
N, u, v = map(int, input().split())
u -= 1
v -= 1
tonari = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  tonari[a].append(b)
  tonari[b].append(a)

d_from_u = [float('inf') for _ in range(N)]
d_from_v = [float('inf') for _ in range(N)]
d_from_u[u] = 0
d_from_v[v] = 0


now = [u]
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_u[t] > d:
        d_from_u[t] = d
        nextvisit.append(t)
  now = nextvisit

now = [v]
d = 0
while now:
  d += 1
  nextvisit = []
  for n in now:
    for t in tonari[n]:
      if d_from_v[t] > d:
        d_from_v[t] = d
        nextvisit.append(t)
  now = nextvisit




distance = []
for U, V in zip(d_from_u, d_from_v):
  distance.append((U, V))

distance.sort(key = lambda x: x[1])


ans = 0
while distance:
  d = distance.pop()
  if d[0] < d[1]:
    ans = d[1] - 1
    break
print(ans)

Solution (Python):
import collections

n,u,v=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=collections.deque()
q.append((v,0))
checked=[0]*(n+1)
dist1=[0]*(n+1)
while len(q)!=0:
  tv,td=q.popleft()
  checked[tv]=1
  dist1[tv]=td
  for tu in g[tv]:
    if checked[tu]==1:
      continue
    q.append((tu,td+1))
q=collections.deque()
q.append((u,0))
checked=[0]*(n+1)
dist2=[0]*(n+1)
while len(q)!=0:
  tv,td=q.popleft()
  checked[tv]=1
  dist2[tv]=td
  for tu in g[tv]:
    if checked[tu]==1:
      continue
    q.append((tu,td+1))
ans=0
for tv in range(1,n+1):
  if dist1[tv]>dist2[tv]:
    ans=max(ans,dist1[tv]-1)
print(ans)