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):
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)

depth = 0
already = [0 for i in range(n)]
already[v] = 1
nodes = [v]
while nodes != []:
    depth += 1
    next_nodes = []
    for node in nodes:
        children = edges[node]
        for child in children:
            if already[child] == 0:
                already[child] = depth
                next_nodes.append(child)
    nodes = next_nodes
already[v] = 0

depth = 0
already_u = [0 for i in range(n)]
already_u[u] = 1
nodes = [u]
while nodes != []:
    depth += 1
    next_nodes = []
    for node in nodes:
        children = edges[node]
        for child in children:
            if already_u[child] == 0:
                already_u[child] = depth
                next_nodes.append(child)
    nodes = next_nodes
already_u[u] = 0

maxi = 0
for i in range(n):
    if already_u[i] < already[i]:
        maxi = max(maxi, already[i])

print(maxi-1)

Solution (Python):
N,u,v=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
T=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)


def dfs(start):
    tolist=T[start]
    nowd=done[start]
    for next_n in tolist:
        if done[next_n]==-1:
            done[next_n]=nowd+1
            dfs(next_n)

done=[-1]*N
done[u-1]=0
dfs(u-1)
dtaka=done.copy()
done=[-1]*N
done[v-1]=0
dfs(v-1)
dao=done.copy()
ans=0
for i in range(N):
    t=dtaka[i]
    a=dao[i]
    if a>t:
        ans=max(ans, a)
print(ans-1)

Solution (Python):
N, U, V = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)


def dist(s):
    dist = [-1] * (N + 1)
    node = [s]
    dist[s] = 0
    while node:
        s = node.pop()
        for t in edge[s]:
            if dist[t] == -1:
                dist[t] = dist[s] + 1
                node.append(t)
    return dist


taka = dist(U)
aoki = dist(V)
can_go = taka[V]

ans = 0
for t, a in zip(taka[1:], aoki[1:]):
    if t <= a:
        ans = max(ans, a - 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
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
                
                if s==V-1:
                    is_leaf[v] = False
        
    return dist

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)

is_leaf = [True]*N
d1 = bfs(V-1)
d2 = bfs(U-1)
ans = 0

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

Solution (Python):
n,u,v=map(int,input().split())
u-=1
v-=1
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
aoki=[10**10]*n
taka=[10**10]*n
aoki[v]=0
taka[u]=0
Q=[v]
visited={v}
co=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      aoki[j]=co
      visited.add(j)
      P.append(j)
  Q=P
  co+=1
Q=[u]
visited={u}
co=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      taka[j]=co
      visited.add(j)
      P.append(j)
  Q=P
  co+=1
ans=0
for i in range(n):
  if taka[i]<aoki[i]:ans=max(ans,aoki[i]-1)
print(ans)

Solution (Python):
from collections import deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
graph = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

def bfs(s):
  dist = [-1]*N
  q = deque([s])
  dist[s] = 0

  while q:
    u = q.popleft()
    for v in graph[u]:
      if dist[v] == -1:
        dist[v] = dist[u] + 1
        q.append(v)

  return dist

d1 = bfs(u)
d2 = bfs(v)
ans = 0
for i in range(N):
  if d1[i] < d2[i]:
    ans = max(ans, d2[i]-1)

print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
n,u,v = ma()
u,v = u-1,v-1
tree = [[] for i in range(n)]
import collections

for i in range(n-1):
    a,b = ma()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
que = collections.deque([(v,0)])
vis = [False]*n
dist_v = [0]*n
while que:
    now,c = que.popleft()
    vis[now] = True
    dist_v[now] = c
    for node in tree[now]:
        if not vis[node]:
            que.append((node,c+1))
que = collections.deque([(u,0)])
vis = [False]*n
dist_u = [0]*n
while que:
    now,c = que.popleft()
    vis[now] = True
    dist_u[now] = c
    for node in tree[now]:
        if not vis[node]:
            que.append((node,c+1))
ans = 0
for i in range(n):
    if dist_u[i] < dist_v[i]:
        ans = max(ans,dist_v[i])
print(ans-1)

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


def solve(x):
    visit = [-1 for _ in range(n+1)]
    visit[x] = 0
    q = deque([x])
    while q:
        p = q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                visit[i] = visit[p]+1
                q.append(i)
    return visit

visit_a = solve(v)
visit_t = solve(u)

x, y = [], []
for i in range(1, n+1):
    if visit_a[i] >= visit_t[i]:
        x.append(visit_a[i])
        y.append(visit_t[i])
p = x.index(max(x))

print(x[p]-1)

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


def solve(x):
    visit = [-1 for _ in range(n+1)]
    visit[x] = 0
    q = deque([x])
    while q:
        p = q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                visit[i] = visit[p]+1
                q.append(i)
    return visit

visit_a = solve(v)
visit_t = solve(u)

x, y = [], []
for i in range(1, n+1):
    if visit_a[i] >= visit_t[i]:
        x.append(visit_a[i])
        y.append(visit_t[i])
p = x.index(max(x))

print(x[p]-1)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
node=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
	node[b-1].append(a-1)
def dfs(i):
	visited[i]=1
	for x in node[i]:
		if visited[x]==0:
			dis[x]=dis[i]+1
			dfs(x)
inf=10**9
dis=[inf]*n;dis[u-1]=0;visited=[0]*n
dfs(u-1)
dis2=[]
from copy import copy
dis_dash=copy(dis)
dis2.append(dis_dash)
dis[v-1]=0;visited=[0]*n
dfs(v-1)
dis2.append(dis)
cnt=0
for i in range(n):
	if dis2[0][i]<dis2[1][i]:
		cnt=max(cnt,dis2[1][i])
print(cnt-1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
N, u, v = map(int, input().split())
u -= 1
v -= 1
edges = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

dist = [0] * N
def dfs(v, d=0, p=-1):
    global dist
    dist[v] = d
    for u in edges[v]:
        if u == p:
            continue
        dfs(u, d + 1, v)

def calc_dist(s):
    global dist
    dist = [0] * N
    dfs(s)
    return dist

distS = calc_dist(u)
distT = calc_dist(v)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Solution (Python):
from collections import deque, defaultdict
from copy import deepcopy
import sys
import resource

sys.setrecursionlimit(10**5)

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

depth = dict(zip(list(range(1,N+1)),[-1]*N))

def bfs(s):
    if graph[s]:
        for v in graph[s]:
            if depth[v] == -1:
                depth[v] = depth[s] + 1
                bfs(v)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[v] = 0
bfs(v)
depth_v = deepcopy(depth)

depth = dict(zip(list(range(1,N+1)),[-1]*N))
depth[u] = 0
bfs(u)
depth_u = depth
depth_v = sorted(depth_v.items(), key = lambda x:x[0])
depth_u = sorted(depth_u.items(), key= lambda x:x[0])

MAX = 0
for v,u in zip(depth_v, depth_u):
    if u[1] < v[1]:
        MAX = max(MAX,v[1])
print(MAX-1)

Solution (Python):


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

    
    st = [u]
    prev = [None for i in range(n)]
    while st:
        x = st.pop()
        for y in adj[x]:
            if y == prev[x]: continue
            prev[y] = x
            st.append(y)
    path = [v]
    while path[-1] != u:
        path.append(prev[path[-1]])
    path = list(reversed(path))

    
    l = len(path) - 1
    cross = path[(l - 1) // 2]
    square = path[(l - 1) // 2 + 1]
    st = [(cross, 0)]
    prev = [None for i in range(n)]
    dist = [-1 for i in range(n)]
    while st:
        x, d = st.pop()
        dist[x] = d
        for y in adj[x]:
            if y == prev[x]: continue
            if y == square: continue
            prev[y] = x
            st.append((y, d + 1))
    star_square = max(dist)

    if l % 2 == 1:
        res = (l - 1) // 2 + star_square
    else:
        res = (l - 1) // 2 + star_square + 1
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):
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)
va=[-1]*n
q=[v-1]
va[v-1]=0
while q:
    x=q.pop()
    for j in tree[x]:
        if va[j]==-1:
            q.append(j)
            va[j]=va[x]+1
q=[u-1]
vt=[-1]*n
vt[u-1]=0
ans=0
while q:
    x=q.pop()
    ans=max(ans,va[x])
    for j in tree[x]:
        if vt[j]==-1:
            if vt[x]+1<va[j]:
                q.append(j)
                vt[j]=vt[x]+1
            elif vt[x]+1==va[j]:
                vt[j]=vt[x]+1
print(ans-1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    
    
    
    n,u,s = map(int, input().split())
    adj = [[] for _ in range(n)] 
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
    ta = [-1]*n
    ao = [-1]*n

    d = deque([s-1])
    ao[s-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ao[nv] == -1:
                ao[nv] = ao[v] + 1
                d.append(nv)

    d = deque([u-1])
    ta[u-1] = 0
    while d:
        v = d.popleft()
        for nv in adj[v]:
            if ta[nv] == -1:
                ta[nv] = ta[v] + 1
                d.append(nv)

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

if __name__ == '__main__':
    main()

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

N, s, t = map(int, input().split())
s -= 1; t -= 1
to = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)

def calcDist(u):
    dfs(u)
    return dist

def dfs(v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, d+1, v)

dist = [0 for _ in range(N)]
distS = calcDist(s)
dist = [0 for _ in range(N)]
distT = calcDist(t)

ans = 0
for i in range(N):
    if distS[i] < distT[i]:
        ans = max(ans, distT[i])

print(ans-1)

Solution (Python):
import queue

n,u,v = map(int, input().split())
u -= 1
v -= 1

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

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

t = [10**9]*n
t[u]=0
q = queue.Queue()

q.put(u)

while not q.empty():
    p = q.get()
    for x in path[p]:
        if t[x]>t[p]+1:
            q.put(x)
            t[x]=t[p]+1

a = [10**9]*n
a[v]=0
q = queue.Queue()

q.put(v)

while not q.empty():
    p = q.get()
    for x in path[p]:
        if a[x]>a[p]+1:
            q.put(x)
            a[x]=a[p]+1

c = [a[i] for i in range(n) if a[i]>t[i]]
print(max(c)-1)

Solution (Python):
f=lambda:map(int,input().split())
n,st,sa=f()
g=[set() for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st-1)
la=bfs(sa-1)
print(max(la[i] for i in range(n) if lt[i]<la[i])-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,sys.stdin.readline().split())
n,st,sa=f()
g=[set() for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].add(b-1)
  g[b-1].add(a-1)
def dfs(l,v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c!=p: dfs(l,c,v,d+1)
lt=[0]*n
dfs(lt,st-1)
la=[0]*n
dfs(la,sa-1)
print(max(la[i] for i in range(n) if lt[i]<la[i])-1)

Solution (Python):
import sys
f=lambda:map(int,sys.stdin.readline().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st)
la=bfs(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Solution (Python):
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def bfs(s):
  l=[-1]*n; l[s]=0; q=[s]
  while q:
    v=q.pop(); d=l[v]+1
    for c in g[v]:
      if l[c]<0: l[c]=d; q+=[c]
  return l
lt=bfs(st)
la=bfs(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
f=lambda:map(int,input().split())
n,st,sa=f()
st-=1
sa-=1
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=f()
  g[a-1].append(b-1)
  g[b-1].append(a-1)
def dfs(v,p=-1,d=0):
  l[v]=d
  for c in g[v]:
    if c==p: continue
    dfs(c,v,d+1)
def dist(s):
  global l
  l=[0]*n
  dfs(s)
  return l
lt=dist(st)
la=dist(sa)
m=0
for i in range(n):
  if lt[i]<la[i]: m=max(m,la[i])
print(m-1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**5)
def input(): return sys.stdin.readline().strip()

"""
Pypyは再帰が遅いらしいのでPythonで通してみる
"""

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

    """
    まずu, vを結ぶ単純パス上にあるnodeを列挙する。
    これはvを根とする根付き木に対するdfs（再帰）により求まる（参考：ABC152F）
    """

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

    """
    次にu, vを結ぶ単純パスP上の各頂点wに対して、wからPに沿わない向きにどれだけ深く潜れるかを求める。
    しかし最終的には「頂点vから（高橋君が逃げ込める中で）最も遠い頂点」を求めればよいので、
    uvの中点からdfsすれば十分。
    """

    def dfs(v, p): 
        d = -1
        for w, _ in repn[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)
   


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline().strip()

n, u, v = map(int, input().split())
u, v = u-1, v-1

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)

from queue import Queue


aoki = [-1 for _ in range(n)]
aoki[v] = 0
todo = Queue()
todo.put(v)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if aoki[j] == -1:
            todo.put(j)
            aoki[j] = aoki[i] + 1


taka = [-1 for _ in range(n)]
taka[u] = 0
todo = Queue()
todo.put(u)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if taka[j] == -1:
            if taka[i] + 1 < aoki[j]:
                todo.put(j)
            taka[j] = taka[i] + 1


ans = 0
for i in range(n):
    if taka[i] != -1:
        if aoki[i] - 1 > ans:
            ans = aoki[i] - 1

print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline().strip()

n, u, v = map(int, input().split())
u, v = u-1, v-1

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)

from queue import Queue


aoki = [-1 for _ in range(n)]
aoki[v] = 0
todo = Queue()
todo.put(v)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if aoki[j] == -1:
            todo.put(j)
            aoki[j] = aoki[i] + 1


taka = [-1 for _ in range(n)]
taka[u] = 0
todo = Queue()
todo.put(u)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if taka[j] == -1:
            if taka[i] + 1 < aoki[j]:
                todo.put(j)
            taka[j] = taka[i] + 1


ans = 0
for i in range(n):
    if taka[i] != -1:
        if aoki[i] - 1 > ans:
            ans = aoki[i] - 1

print(ans)

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

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)

from queue import Queue


aoki = [-1 for _ in range(n)]
aoki[v] = 0
todo = Queue()
todo.put(v)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if aoki[j] == -1:
            todo.put(j)
            aoki[j] = aoki[i] + 1


taka = [-1 for _ in range(n)]
taka[u] = 0
todo = Queue()
todo.put(u)
while not todo.empty():
    i = todo.get()
    for j in tree[i]:
        if taka[j] == -1:
            if taka[i] + 1 < aoki[j]:
                todo.put(j)
            taka[j] = taka[i] + 1


ans = 0
for i in range(n):
    if taka[i] != -1:
        if aoki[i] - 1 > ans:
            ans = aoki[i] - 1

print(ans)

Solution (Python):
from collections import deque
n,u,v=map(int,input().split())
edge=[[] for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
visitedu=[-1]*n
visitedv=[-1]*n
def bfs(s,visited):
    q=deque([s])
    visited[s]=0
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==-1:
                visited[nx]=visited[x]+1
                q.append(nx)
    return
bfs(u-1,visitedu)
bfs(v-1,visitedv)
a=0
b=10**10
for i in range(n):
    if visitedu[i]<visitedv[i]:
        a=max(a,visitedv[i])
    elif visitedu[i]==visitedv[i]:
        b=min(b,visitedv[i])


if b==10**10:
    b=-1
if a<=b:
    print(b)
else:
    print(a-1)

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

parent={i:-1 for i in range(1,N+1)}
depth={i:-1 for i in range(1,N+1)}
parent[v]=0
depth[v]=0
q=set([v])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if parent[i]==-1:
                parent[i]=x
                depth[i]=depth[x]+1
                sub.add(i)

        if not q:
            q=sub
            sub=set([])
            break

if depth[u]%2==1:
    i=depth[u]//2
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)
else:
    i=depth[u]//2-1
    stand=u
    while i>0:
        stand=parent[stand]
        i-=1
    test=depth[stand]
    q=set([stand])
    sub=set([])
    while q:
        while q:
            x=q.pop()
            for i in edge[x]:
                if i!=parent[x]:
                    test=max(test,depth[i])
                    sub.add(i)

            if not q:
                q=sub
                sub=set([])
                break

    print(test-1)

Solution (Python):
import copy
import sys
sys.setrecursionlimit(10**9)

def dfs(G, v, p, d, depth):
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        dfs(G, nv, v, d+1, depth)
    return G, depth


n, T, A = map(int,input().split())
T, A = T-1, A-1
g = [[] for _ in range(n)]
for i in range(n-1):
    x, y = map(int,input().split())
    x, y = x-1, y-1
    g[x].append(y)
    g[y].append(x)

depth = [0]*n
GT = copy.deepcopy(g)
GT[T].append(-1)
GT, dt = dfs(GT, T, -1, 0, depth)

depth = [0]*n
GA = copy.deepcopy(g)
GA[A].append(-1)
GA, da = dfs(GA, A, -1, 0, depth)

ans = 0
for t, a in zip(dt, da):
    if t <= a:
        ans = max(ans, a)
print(ans-1)

Solution (Python):
from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    dist = [-1] * (n + 1)
    dist[s] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist

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)
dist1 = bfs(u)
dist2 = bfs(v)
ans = 0
for i in range(1, n + 1):
    if dist1[i] <= dist2[i]:
        ans = max(ans, dist2[i] - 1)
print(ans)

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N, u, v = map(int, input().split())

E = [[] for _ in range(N+1)]
for _ in range(N-1):
	ta, tb = map(int, input().split())
	E[ta].append(tb)
	E[tb].append(ta)
E = np.array(E)

inf = 10**9
taka = np.full(N+1, inf, dtype = np.int64)
ao = np.full(N+1, inf, dtype = np.int64)
taka[u] = 0
ao[v] = 0
def solve(dist, start):
	q = [start]
	while q:
		cp = q.pop()
		for nep in E[cp]:
			if dist[nep] != inf:
				continue
			else:
				dist[nep] = dist[cp] + 1
				q.append(nep)

solve(taka, u)
solve(ao, v)
ind = taka < ao
ao_max = np.max(ao[ind])
print(ao_max - 1)

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

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

for x,y in a:
    b[x-1].append(y-1)
    b[y-1].append(x-1)

import collections
from collections import deque
def tree(s):

    INF=-10**9
    dis = [INF for i in range(n)]
    dis[s]=0
    def bfs():
        d = deque()
        d.append(s)

        while len(d):
            x = d.popleft()

            for i in range(len(b[x])):
                y=b[x][i]
                if dis[y] == INF:
                    d.append(y)
                    dis[y]=dis[x]+1


        return dis
    return bfs()


q1=tree(u-1)
q2=tree(v-1)
ans=0

for i in range(n):
    if q2[i]>q1[i]:
        ans=max(q2[i],ans)
print(ans-1)

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

from collections import deque, defaultdict



n, u, v = map(int, input().split())
u, v = u-1, v-1

G = defaultdict(lambda:deque([])) 


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(start, player):
    que = deque([(start, -1, 0)])
    while que:
        node, par, dst = que.popleft() 
        if len(G[node]) == 1:
            dst_dict[player][node] = dst
            
        for nxt in G[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))
            
dst_dict = [{}, {}]

bfs(u, 0)
bfs(v, 1)

max_time = 0
for k in dst_dict[0]:
    if dst_dict[0][k] < dst_dict[1][k]:
        max_time = max(max_time, dst_dict[1][k]-1)
    
print(max_time)

Solution (Python):


from collections import deque
import sys
si = sys.stdin.readline


def BFS(g, n, s):
    d = 0
    dt = [0 for _ in range(n+1)]
    dt[s] = 0
    visited = set()
    visited.add(s)
    Q = deque([s])

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q.popleft()
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt[1:]


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, n, u)
    vdt = BFS(graph, n, v)
    print(-1+max([v for u, v in zip(udt, vdt) if u < v]))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
si = sys.stdin.readline


def BFS(g, s):
    d = 0
    dt = dict()
    visited = set()
    visited.add(s)
    Q = deque([s])

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q.popleft()
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, u)
    vdt = BFS(graph, v)
    udt[u], vdt[v] = 0, 0

    vdmax = 0
    for i in range(1, n+1):
        if (vdt[i]-udt[i]) > 0 and vdt[i] > vdmax:
            vdmax = vdt[i]
    print(vdmax-1)


if __name__ == '__main__':
    main()

Solution (Python):

"""
与えられるグラフは木構造
青木くん(追いかける方)がいる頂点を根とすると、この問題は解きやすくなる。
そうした場合、高橋くんが追いつかれずに行ける頂点の中で、最も深さが深い葉に行くのが最適。
そのような頂点は頂点u,vからの距離によって求めることができ、結果的に高橋くんが行ける最深部の葉から
根までの距離が答えとなる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,u,v = map(int,readline().split())
u,v = u-1,v-1 

g = [[] for _ in range(n+1)] 
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)



root = v
rank = [0]*n
new = [root] 
c = 1
while len(new):
    tank = []
    for e in new:
        for go in g[e]:
            if go != root and rank[go] == 0:
                rank[go] = c
                tank.append(go)
    c += 1
    new = tank


now = u
res = rank[u]-(rank[u]-1)//2 
ans = (rank[u]-1)//2 
while True:
    for e in g[now]:
        if rank[e] < rank[now]:
            if rank[e] < res: 
                break
            else:
                now = e 
        else:
            continue
    if rank[e] < res: 
        break


new = [now]
while new:
    tank = []
    for e in new:
        for go in g[e]:
            if rank[go] > rank[e]: 
                tank.append(go)
    ans += 1
    new = tank

print(ans-1 if rank[u]%2==1 else ans)

Solution (Python):
from collections import deque
n,u,v=map(int,input().split())
u=u-1
v=v-1
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  G[a].append(b)
  G[b].append(a)
P=[0]*n 
P[v]=-1
F=[0]*n
D=deque([v])
V=[0]*n
V[v]=1
GG=[[] for i in range(n)]
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(G[x])):
    if V[G[x][i]]==0:
      V[G[x][i]]=1
      D.append(G[x][i])
      P[G[x][i]]=x
      GG[x].append(G[x][i])
      F[G[x][i]]=F[x]+1
a=F[u]
ans1=(a-1)//2 
b=F[u]%2
if b==0:
  b=2 
for i in range(ans1):
  u=P[u]
V=[0]*n
V[u]=1
V[P[u]]=1
F=[0]*n
D=deque([u])
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(GG[x])):
    D.append(GG[x][i])
    F[GG[x][i]]=F[x]+1
ans2=max(F)
print(ans1+ans2+b//2)

Solution (Python):


import sys


















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n, u, v = mi()
    u -= 1
    v -= 1
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = mi_0()
        adj[a].append(b)
        adj[b].append(a)
    dist = [[None, None] for _ in range(n)]
    def dfs(current, key, previous=-1, depth=0):
        dist[current][key] = depth
        for v in adj[current]:
            if v != previous:
                dfs(v, key, current, depth+1)
    dfs(current=u, key=0, previous=-1, depth=0)
    dfs(current=v, key=1, previous=-1, depth=0)
    ans = -1
    for i in range(n):
        if dist[i][0] < dist[i][1]:
            ans = max(ans, dist[i][1] - 1)
    print(ans)


if __name__ == "__main__":
    main()