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 defaultdict, deque

N, u, v  = map(int, input().split())
way = defaultdict(list)
for _ in range(N-1):
    a, b =  map(int, input().split())
    
    way[a].append(b)
    way[b].append(a)
seen1 = [-1]*N
seen2 = [-1]*N
seen1[u-1] = 0
seen2[v-1]= 0

queue = deque([u])
while queue:
    q = queue.popleft()
    for i in way[q]:
        if seen1[i-1]==-1:
            queue.append(i)
            seen1[i-1] = seen1[q-1]+1

queue = deque([v])
while queue:
    q = queue.popleft()
    for i in way[q]:
        if seen2[i-1]==-1:
            queue.append(i)
            seen2[i-1] = seen2[q-1]+1
            



for i in range(N):
    if seen1[i]>=seen2[i]:
        seen2[i] = -1
print(max(seen2)-1)

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

INF = float('inf')

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

def bfsMinCosts(adjList, vSt, INF):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == INF:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s
    return costs

costUs = bfsMinCosts(adjL, u, INF)
costVs = bfsMinCosts(adjL, v, INF)

ans = 0
for x in range(N):
    if costUs[x] < costVs[x]:
        if costVs[x] > ans:
            ans = costVs[x]

print(ans-1)

Solution (Python):
from collections import deque
import sys

N, u, v = map(int, input().split())
u -= 1; v -= 1
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    A, B = map(lambda x: int(x) - 1, s.split())
    edge[A].append(B)
    edge[B].append(A)

INF = float('inf')


pathV = [INF] * N
pathV[v] = 0
q = deque()
q.append((v, 0))
while q:
    p, d = q.popleft()
    nd = d + 1
    for np in edge[p]:
        if pathV[np] > nd:
            pathV[np] = nd
            q.append((np, nd))


ans = 0
pathU = [INF] * N
pathU[u] = 0
q = deque()
q.append((u, 0))
while q:
    p, d = q.popleft()
    nd = d + 1
    if len(edge[p]) == 1:
        ans = max(ans, pathV[p] - 1)
    for np in edge[p]:
        if pathU[np] > nd and pathV[np] > nd:
            pathU[np] = nd
            q.append((np, nd))

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,u,v = map(int,ipt().split())
    way = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i in range(1,n+1):
        if tt[i] == -1:
            continue
        if ma < tt[i]+max(0,ta[i]-tt[i]-1):
            ma = tt[i]+max(0,ta[i]-tt[i]-1)
    print(ma)


    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def dfs_a(N,v,adjlist,cur):
    global depth_a
    depth_a[v]=cur
    for node in adjlist[v]:
        if depth_a[node]<0:
            dfs_a(N,node,adjlist,cur+1)
def dfs_t(N,v,adjlist,cur):
    global depth_t
    depth_t[v]=cur
    for node in adjlist[v]:
        if depth_t[node]<0:
            dfs_t(N,node,adjlist,cur+1)
    
    
    

from collections import deque

N,u,v=map(int,input().split())
adjlist=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    adjlist[a-1].append(b-1)
    adjlist[b-1].append(a-1)
depth_a=[-1]*N
depth_t=[-1]*N
dfs_a(N,v-1,adjlist,0)
dfs_t(N,u-1,adjlist,0)
M=0
for i in range(N):
    if depth_a[i]>depth_t[i]:
        curm=depth_a[i]-1
        if curm>M:
            M=curm
print(M)

Solution (Python):
from collections import deque

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

d_1 = deque()
d_1.append(u-1)
dist_1 = [-1] * n
dist_1[u-1] = 0
while d_1:
    node = d_1.popleft()
    for next_node in edge[node]:
        if dist_1[next_node] < 0:
            dist_1[next_node] = dist_1[node] + 1
            d_1.append(next_node)

d_2 = deque()
d_2.append(v-1)
dist_2 = [-1] * n
dist_2[v-1] = 0
while d_2:
    node = d_2.popleft()
    for next_node in edge[node]:
        if dist_2[next_node] < 0:
            dist_2[next_node] = dist_2[node] + 1
            d_2.append(next_node)

res = 0
for i in range(n):
    if dist_1[i] < dist_2[i]:
        res = max(res, dist_2[i]-1)
print(res)

Solution (Python):
N,u,v=map(int,input().split())
from collections import deque
g=[[] for _ in range(N)]
for i in range(N-1):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
def bfs(n):
  stack=deque([])
  depth=[-1]*N
  depth[n-1]=0
  stack.append(n-1)
  while stack:
    a=stack.popleft()
    for b in g[a]:
      if depth[b]==-1:
        depth[b]=depth[a]+1
        stack.append(b)
  return depth
U=bfs(u)
V=bfs(v)
List=[]
for i in range(N):
  if len(g[i])==1 and U[i]<V[i]:
    List.append(i)
ans=0

for i in List:
  ans=max(ans,V[i]-1)

print(ans)

Solution (Python):
n,t,aoki=map(int,input().split())

tree=[[] for _ in range(n)]

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

if tree[t-1]==[aoki-1]:
    print(0)
    exit()


from collections import deque
ans=[-1]*n
stack = deque([t-1])
ans[t-1]=0

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans[item]==-1:
            ans[item]=ans[tmp]+1
            stack.append(item)


ans2=[-1]*n
stack = deque([aoki-1])
ans2[aoki-1]=0

result=0


while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans2[item]==-1:
            ans2[item]=ans2[tmp]+1
            stack.append(item)
            if ans[item]<ans2[item]:
                result=max(result,ans2[item])-1
            elif ans[item]==ans2[item]:
                result=max(result,ans2[item])-1

print(result)

Solution (Python):
from collections import deque

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

not_yet = deque([u-1])
already = [False]*n
already[u-1] = True
dist = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist[value] = dist[key] + 1
    already[value] = True
    not_yet.append(value)
  
not_yet = deque([v-1])
already = [False]*n
already[v-1] = True
dist2 = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist2[value] = dist2[key] + 1
    already[value] = True
    not_yet.append(value)

judge = dist[v-1]
ans = 0
for i in range(n):
  if dist[i]+dist2[i] > judge:
    if dist[i] >= dist2[i]:
      continue
    sub = dist2[i]-1
  else:
    sub = judge-1
  if sub > ans:
    ans = sub
print(ans)

Solution (Python):
from collections import deque


def calc_dist(head, my_dict, dist_a):
    deq = deque()
    deq.append((head, 0))
    visited = set()
    visited.add(head)

    while deq:
        ptr, length = deq.pop()
        dist_a[ptr] = length
        for item in my_dict[ptr]:
            if item not in visited:
                visited.add(item)
                deq.append((item, length+1))


n, u, v = map(int, input().split())
my_dict = dict()

for i in range(n-1):
    a, b = map(int, input().split())
    if a in my_dict:
        my_dict[a].append(b)
    else:
        my_dict[a] = [b]
    if b in my_dict:
        my_dict[b].append(a)
    else:
        my_dict[b] = [a]

dist_a = dict()
dist_b = dict()

calc_dist(u, my_dict, dist_a)
calc_dist(v, my_dict, dist_b)
ret = 0

for i in range(1, n+1):
    if dist_a[i] > dist_b[i]:
        continue
    else:
        ret = max(ret, dist_b[i] - 1)

print(ret)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N,u,v=map(int, input().split())
D=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  a-=1
  b-=1
  D[a].append(b)
  D[b].append(a)
Taka=[0]*(N+1)
Aoki=[0]*(N+1)
def f(n,p,A):
  for i in D[n]:
    if i!=p:
      A[i]=A[n]+1
      f(i,n,A)
      
f(u-1,-1,Taka)
f(v-1,-1,Aoki)
ans=0
for i in range(N):
  if Taka[i]<Aoki[i]:
    ans=max(ans,Aoki[i]-1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
def input():
    return sys.stdin.readline()[:-1]

n,u,v = map(int,input().split())
u-=1
v-=1
g = [[]for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
seen = [-1 for i in range(n)]
taka = []
aok = []
def dfs(s,lis):
    nec = g[s]
    if len(nec)==1:
        lis.append(s)
    for i in nec:
        if seen[i]!=-1:
            continue
        seen[i] = seen[s]+1
        dfs(i,lis)

seen[u]=0
dfs(u,taka)
takadist = [i for i in seen]
seen = [-1 for i in range(n)]
seen[v]=0
dfs(v,aok)
ans = 0
for i in aok:
    if takadist[i]<seen[i]:
        ans = max(ans,seen[i])
if g[u]==[v]:
    print(0)
else:
    print(ans-1)

Solution (Python):
n,u,v=map(int,input().split())
u-=1;v-=1
ki=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
ha=[]
for i in range(n):
  if len(ki[i])==1:
    ha.append(i)
ta=[0]*n
ao=[0]*n
from collections import deque
d=deque()
d.append(u)
visited=[False]*n
visited[u]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    ta[i]=ta[g]+1
d=deque()
d.append(v)
visited=[False]*n
visited[v]=True
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    ao[i]=ao[g]+1
if u in ha and ki[u][0]==v:
  print(0)
  exit()
m=0
for i in ha:
  if ta[i]<ao[i]:
    m=max(m,ao[i])
print(m-1)

Solution (Python):
from collections import deque
n,u,v=map(int, input().split())
edgelist = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    edgelist[a-1].append(b-1)
    edgelist[b-1].append(a-1)
dist = [[0,0] for _ in range(n)]
def distance(start, id):
    que=deque()
    visited = [0]*n

    found = False
    que.append([edgelist[start],start])
    while que:
        ver=que.popleft()
        visited[ver[1]]=1
        for next_v in ver[0]:
            if not visited[next_v]:
                dist[next_v][id]=dist[ver[1]][id]+1
                que.append([edgelist[next_v], next_v])
distance(u-1,0)
distance(v-1,1)
dist.sort(key = lambda x:x[1],reverse = True)
ans=0
for i in range(n):
    if dist[i][1]-dist[i][0]>=1:
        print(dist[i][1]-1)
        exit()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 5 + 1)


def dfsu(s, p):
    for t in g[s]:
        if t == p:
            continue
        du[t] = du[s] + 1
        dfsu(t, s)


def dfsv(s, p):
    for t in g[s]:
        if t == p:
            continue
        dv[t] = dv[s] + 1
        dfsv(t, s)


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

du = [0] * n
dv = [0] * n
dfsu(u, -1)
dfsv(v, -1)

mx = 0
for i in range(n):
    if du[i] < dv[i]:
        mx = max(mx, dv[i])
print(mx - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n,g,s = map(int,input().split())
G = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(V,v,d):
  if V[v] != -1:
    return
  V[v] = d
  for nv in G[v]:
    dfs(V,nv,d+1)
  
if len(G[g-1])==1 and G[g-1][0]==s-1:
  print(0)
else:
  vs = [-1]*n
  vg = [-1]*n
  dfs(vs,s-1,0)
  dfs(vg,g-1,0)
  
  ans = 0
  for i in range(n):
    if vs[i]>vg[i]:
      ans = max(ans,vs[i])
      
  print(ans-1)

Solution (Python):
n,u,v=map(int,input().split())
u-=1
v-=1
ki=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  ki[a].append(b)
  ki[b].append(a)
du=[0]*n
dv=[0]*n
from collections import deque
def distance(i):
  seen=[-1]*n
  seen[i]=0
  todo=deque([i])
  while todo:
    t=todo.popleft()
    l=ki[t]
    d=seen[t]
    for li in l:
      if seen[li]==-1:
        seen[li]=d+1
        todo.append(li)
  return seen
du=distance(u)
dv=distance(v)
ans=0
for i in range(n):
  if dv[i]>du[i]:
    ans=max(ans,dv[i])
print(ans-1)

Solution (Python):
import sys
import  math
import fractions
from collections import deque
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,u,v=nm()
u=u-1
v=v-1
INF=10**18
edge=[[] for i in range(N)]

def bfs(start,edge):
    d=[INF]*N
    d[start]=0
    q=deque([start])
    while (q):
        e=q.popleft()
        for i in edge[e]:
            if(d[e]+1<d[i]):
                d[i]=d[e]+1
                q.append(i)   
    return d


for i in range(N-1):
    A,B=nm()
    edge[B-1].append(A-1)
    edge[A-1].append(B-1)


d_A=bfs(u,edge)
d_B=bfs(v,edge)

ans=0
for i in range(N):
    
    
    
    if(d_A[i]<d_B[i]):
        tmp=max(d_A[i],d_B[i])
        ans=max(ans,tmp)

print(ans-1)

Solution (Python):
import sys

sys.setrecursionlimit(10**5)
n, u, v = map(int, input().split())
u -= 1
v -= 1
m_mat = [[] for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    m_mat[a].append(b)
    m_mat[b].append(a)
u_map = [-1]*n
v_map = [-1]*n
u_map[u] = 0
v_map[v] = 0


def dfs(current, depth, ma):
    for nex in m_mat[current]:
        if ma[nex] > -1:
            continue
        ma[nex] = depth
        dfs(nex, depth+1, ma)


dfs(u, 1, u_map)
dfs(v, 1, v_map)

ans = -1
for i in range(n):
    if u_map[i] < v_map[i] and v_map[i] > ans:
        ans = v_map[i]

print(ans-1)

Solution (Python):
from collections import deque
n,u,v=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

leaf=[]
for i in range(1,n+1):
    if(len(g[i])==1):
        leaf.append(i)

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

def bfs(start,d):
    d[start]=0
    q=deque([start])

    while(len(q)>0):
        qi=q.popleft()
        di=d[qi]

        next_qi=g[qi]
        for i in next_qi:
            if(d[i]==-1):
                d[i]=di+1
                q.append(i)

    return d


d_u=bfs(u, d_u)
d_v=bfs(v, d_v)


if(u in leaf and list(g[u])[0]==v):
    print(0)
else:
    ans=0
    for li in leaf:
        if(d_u[li]<d_v[li]):
            ans=max(ans,d_v[li]-1)
    print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**6
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,u,v = LI()
    root = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        root[a-1].append(b-1)
        root[b-1].append(a-1)
    T = [INF for _ in range(N)]
    A = [INF for _ in range(N)]

    def calc_d(m,x):
        q = collections.deque()
        q.append((x,0))
        while q:
            a,d = q.popleft()
            m[a] = d
            for b in root[a]:
                if m[b] > d+1:
                    q.append((b,d+1))

    calc_d(T,u-1)
    calc_d(A,v-1)
    ans = 0
    for i in range(N):
        if T[i] < A[i]:
            ans = max(ans,A[i] - 1)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N,U,V = map(int,input().split())
U,V = U-1,V-1
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

prev = [-1] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        prev[to] = v
        dfs(to,v)
dfs(U)

path = [V]
while prev[path[-1]] >= 0:
    path.append(prev[path[-1]])
ban = set(path[:(len(path)+1)//2])

reach = [0] * N
reach[U] = 1
def dfs2(v,p=-1):
    for to in es[v]:
        if to==p: continue
        if to in ban: continue
        reach[to] = 1
        dfs2(to,v)
dfs2(U)

depth = [0] * N
ans = 0
def dfs3(v,p=-1):
    global ans
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        if reach[to]:
            ans = max(ans, depth[v])
        dfs3(to,v)
dfs3(V)

print(ans)

Solution (Python):



from collections import deque

import sys
input = sys.stdin.readline
N, U, V = map(int, input().split())
U -= 1
V -= 1
G = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

INF = 10**10

T = [INF]*N
T[U] = 0
A = [INF]*N
A[V] = 0


def bfs(v, dist):
    q = deque()
    q.append(v)
    k = 0
    visited = [0]*N
    while q:
        v = q.popleft()
        visited[v] = 1
        k = dist[v]

        for u in G[v]:
            if visited[u]:
                continue
            q.append(u)
            dist[u] = k+1


bfs(U, T)
bfs(V, A)

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

farthest = 0
node = -1
for i, (t, a) in enumerate(zip(T, A)):
    if t < a and farthest < a:
        farthest = a
        node = i

print(farthest-1)

Solution (Python):
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for i, (Ai, Bi) in enumerate(AB):
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq
MY_INF = 10 ** 18

q = [(0, u - 1)]
d_u = [MY_INF] * N
d_u[u - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_u[dst] > dist_tmp:
            d_u[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))

q = [(0, v - 1)]
d_v = [MY_INF] * N
d_v[v - 1] = 0
while len(q) > 0:
    dist, src = heapq.heappop(q)
    for dst in graph[src]:
        dist_tmp = dist + 1
        if d_v[dst] > dist_tmp:
            d_v[dst] = dist_tmp
            heapq.heappush(q, (dist_tmp, dst))



            
ans = 0
for i in range(N):
    if d_u[i] < d_v[i] and ans < d_v[i] - 1:
        ans = d_v[i] - 1

print(ans)

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

def bfs(s):
    q = deque([s])
    dist = [-1]*N
    dist[s] = 0
    leaf = set()
    
    while q:
        v = q.popleft()
        flag = True
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
                flag = False
                
        if flag:
            leaf.add(v)
    
    return dist, leaf

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)

d1, _ = bfs(u-1)
d2, leaf = bfs(v-1)
ans = 0

for i in range(N):
    if i not in leaf and d1[i]<=d2[i]:
        ans = max(ans, d2[i])

print(ans)

Solution (Python):
N, S, T = map(int, input().split())
S -= 1
T -= 1

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

def calc(s):
    minDist = [10**18] * N
    minDist[s] = 0
    st = [s]
    while st:
        now = st.pop()
        d = minDist[now] + 1
        for to in edges[now]:
            if minDist[to] > d:
                minDist[to] = d
                st.append(to)

    return minDist

minDistS = calc(S)
minDistT = calc(T)

ans = 0
for s, t in zip(minDistS, minDistT):
    if s <= t:
        ans = max(ans, t - 1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
        
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
    
def depth(v,p,d):
    global maxd
    maxd=max(maxd,dist[v])
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
N,u,v=map(int,input().split());u,v=u-1,v-1
if u==v:
    print(0)
    exit()

G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    
dist=[-1]*N
dfs(v,-1,0)

lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
 
maxd=-1
depth(SP,-1,0)

print(maxd-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
        
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
    
def depth(v,p,d):
    global maxd
    maxd=max(maxd,dist[v])
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
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(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    
dist=[-1]*N
dfs(v,-1,0)

lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
 
maxd=-1
depth(SP,-1,0)

print(maxd-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def dfs(v,p,d):
    dist[v]=d
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,d+1)
def getSP(v):
    p=v
    if dist[v]==lim:
        return p
    for nv in G[v]:
        if dist[nv]<dist[v]:
            p=getSP(nv)
    return p
def depth(v,p,d):
    sdist[v]=d
    for nv in G[v]:
        if dist[nv]<dist[v]:
            continue
        depth(nv,v,d+1)
    
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(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
dist=[-1]*N
dfs(v,-1,0)
lim=dist[u]-(dist[u]-1)//2
SP=getSP(u)
sdist=[-1]*N
depth(SP,-1,0)
D,tmp=-1,-1
for i in range(N):
    if sdist[i]>tmp:
        D=i
        tmp=sdist[i]
print(dist[D]-1)

Solution (Python):
def dfs(c,lst):
 n=len(lst)
 ans=[0]*n
 stack = [c-1]
 check = [0]*n 
 while stack != [] :
  d=stack.pop()
  if check[d]==0:
   check[d]=1
   for i in lst[d]:
    if check[i]==0:
     stack.append(i)
     ans[i]=ans[d]+1
 return(ans)
import sys
input = sys.stdin.readline
N,u,v=map(int,input().split())
ki=[[] for f in range(N)]
for i in range(N-1):
 a,b = map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
U=dfs(u,ki)
V=dfs(v,ki)
ans=0
for i in range(N):
 if V[i]>U[i]:
  ans=max(ans,V[i]-1)
print(ans)

Solution (Python):
def dfs(c,lst):
 n=len(lst)
 ans=[0]*n
 stack = [c-1]
 check = [0]*n 
 while stack != [] :
  d=stack.pop()
  if check[d]==0:
   check[d]=1
   for i in lst[d]:
    if check[i]==0:
     stack.append(i)
     ans[i]=ans[d]+1
 return(ans)
import sys
input = sys.stdin.readline
N,u,v=map(int,input().split())
ki=[[] for f in range(N)]
for i in range(N-1):
 a,b = map(int,input().split())
 ki[a-1].append(b-1)
 ki[b-1].append(a-1)
U=dfs(u,ki)
V=dfs(v,ki)
ans=0
for i in range(N):
 if V[i]>U[i]:
  ans=max(ans,V[i]-1)
print(ans)

Solution (Python):
def bfs(p):
    stack=[p]
    check = [-1]*n
    check[p] = 0
    while len(stack):
        v = stack.pop()
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                stack.append(i)
    return check
    


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

move_count_u = bfs(u)
move_count_v = bfs(v)

ans = 0

for i in range(n):
    if move_count_u[i] < move_count_v[i]:
        ans = max(move_count_v[i]-1, ans)
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def dist_on_tree(tree, s, N):
    '''tree...(to,cost)の隣接リスト形式
    s...始点ノード
    N...ノード数'''
    from collections import deque
    D = [-1] * N
    D[s] = 0
    que = deque([(s, 0)])  
    while que:
        now, dist = que.popleft()
        for to, cost in tree[now]:
            if D[to] != -1:
                continue
            D[to] = dist + cost
            que.append((to, dist + cost))
    return D


INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations

N, u, v = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a -= 1
    b -= 1
    tree[a].append((b, 1))
    tree[b].append((a, 1))






ud = dist_on_tree(tree, u - 1, N)
vd = dist_on_tree(tree, v - 1, N)
dist = ud[v - 1]



ans = 0
for x in range(N):
    
    
        
    if ud[x] >= vd[x]:
        continue
    ans = max(ans, vd[x] - 1)

print(ans)

Solution (Python):
from collections import defaultdict as d
from collections import deque

def bfs(adj, start, n):
	visited = [0] * (n + 1)
	tab = [0] * n
	q = deque([start])
	visited[start] = 1
	while q:
		s = q.popleft()
		for i in adj[s]:
			if visited[i] == 0:
				q.append(i)
				visited[i] = 1
				tab[i - 1] = tab[s - 1] + 1
	return tab

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

takahashi = bfs(adj, u, n)
aoki = bfs(adj, v, n)
res = -1
for i in range(n):
	if takahashi[i] <= aoki[i]:
		res = max(res, aoki[i] - 1)

print(res)

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

def distances(sommet):
	d = [-1]*(N+1)
	File = [sommet]
	d[sommet] = 0
	while File:
		s = File.pop()
		for x in adj[s]:
			if d[x]==-1:
				d[x] = 1+d[s]
				File.append(x)
	return d


t = distances(u)
a = distances(v)




ans = -1
for i in range(1,N+1):
	if t[i]<a[i]:
		ans = max(ans, a[i]-1)
		
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n, u, v = map(int, input().split())
u, v = u-1, v-1
edges = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    edges[ai].append(bi)
    edges[bi].append(ai)

def dfs(already, node, depth):
    depth += 1
    children = edges[node]
    for child in children:
        if already[child] == 0:
            already[child] = depth
            already = dfs(already, child, depth)
    return already

already_u = [0 for i in range(n)]
already_u[u] = -1
already_u = dfs(already_u, u, 0)
already_u[u] = 0
already_v = [0 for i in range(n)]
already_v[v] = -1
already_v = dfs(already_v, v, 0)
already_v[v] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already_v[i]:
        maxi = max(maxi, already_v[i])
print(maxi-1)

Solution (Python):
n,u,v = list(map(int,input().split()))

graph = [[] for i in range(n)]

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

stack = [u-1]
check = [False]*n
check[u-1] = True
check[v-1] = True
takahasi = [0]*n

while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        takahasi[graph[now][i]] = 1 + takahasi[now]

aoki = [0]*n
stack = [v-1]
check = [False]*n
check[v-1] = True
while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        aoki[graph[now][i]] = 1 + aoki[now]




ans = 0
ans_= n+1
takahasi[u-1] = -1

henone = [0]*n
for i in range(n):
    if len(graph[i]) == 1:
        henone[i] = 1

for i in range(n):
    if henone[i] == 1 and takahasi[i] != 0 and takahasi[i] < aoki[i]:
        ans = max(aoki[i]-1,ans)
    """
    if takahasi[i] == 0:continue
    if takahasi[i] < aoki[i]:
        if (aoki[i] - takahasi[i]) % 2 == 1:
            ans = max(ans,aoki[i]-1)
        else:
            ans = max(ans,aoki[i])
    elif takahasi[i] == aoki[i]:
        ans_ = min(ans_,takahasi[i])
    """
print(ans)

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

N,u,v=map(int,input().split())
E=[tuple(map(int,input().split())) for i in range(N-1)]

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

for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)

from collections import deque
T=[-1]*(N+1)

Q=deque()
Q.append(u)
T[u]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if T[to]==-1:
            T[to]=T[x]+1
            Q.append(to)

A=[-1]*(N+1)

Q=deque()
Q.append(v)
A[v]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if A[to]==-1:
            A[to]=A[x]+1
            Q.append(to)


OK=[0]*(N+1)

for i in range(N+1):
    if T[i]<A[i]:
        OK[i]=1

ANS=0
for i in range(N+1):
    if OK[i]==1:
        ANS=max(ANS,A[i])

print(max(0,ANS-1))