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
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, u, v = LI_()
    n += 1
    edg = [[] for i in range(n)]
    for _ in range(n-1):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dist_u = [-1] * n
    dist_u[u] = 0
    dist_v = [-1] * n
    dist_v[v] = 0
    q = deque([u])
    while q:
        p = q.pop()
        dp = dist_u[p]
        for e in edg[p]:
            if dist_u[e] < 0:
                dist_u[e] = dp + 1
                q.append(e)
    q = deque([v])
    while q:
        p = q.pop()
        dp = dist_v[p]
        for e in edg[p]:
            if dist_v[e] < 0:
                dist_v[e] = dp + 1
                q.append(e)
    ans = 0
    while dist_u[v] - dist_u[u] > 2:
        for e in edg[u]:
            if dist_v[e] < dist_v[u]:
                u = e
                continue
        for e in edg[v]:
            if dist_u[v] > dist_u[e]:
                v = e
                continue
        ans += 1
    f = dist_u[v]-dist_u[u] == 2
    ans += f
    q = deque([u])
    dist_u = [-1] * n
    for e in edg[v]:
        dist_u[e] = 1
    dist_u[u] = 0
    while q:
        u = q.pop()
        dp = dist_u[u]
        for e in edg[u]:
            if dist_u[e] < 0 and v != e:
                dist_u[e] = dp + 1
                q.append(e)
    if f and max(dist_u) == 1:
        ans -= 1
    print(max(dist_u)+ ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 5)

def search(n, total, dic):
    if dic[n] >= 0:
        return
    else:
        dic[n] = total
    for i in br[n]:
        search(i, total + 1, dic)

n, u, v = map(int, input().split())
br = {}
disu = {}
disv = {}
for i in range(n):
    br[i + 1] = []
    disu[i + 1] = -1
    disv[i + 1] = -1
for i in range(n - 1):
    a, b = map(int, input().split())
    br[a].append(b)
    br[b].append(a)

search(u, 0, disu)
search(v, 0, disv)
far = 0
for i in range(1, n + 1):
    if disv[i] < disu[i]:
        continue
    else:
        far = max(far, disv[i])

print(far - 1)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
N, u, v = map(int, input().split())
 
u -= 1
v -= 1
 
graph = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
 
lst = []
def calcDist(cur, par, dst):
    global lst
    lst[cur] = dst
    for neighbour in graph[cur]:
        if neighbour == par: continue
        calcDist(neighbour, cur, dst + 1)
        
uDist = [None for i in range(N)]
vDist = [None for i in range(N)]
lst = uDist
calcDist(u, -1, 0)
lst = vDist
calcDist(v, -1, 0)
 
best = 0
 
for node in range(N):
    if uDist[node] < vDist[node]: best = max(best, vDist[node] - 1)
print(best)

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

n,u,v = map(int,input().split())
edges = [[] for _ in range(n)]

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

visit1 = [False] * n
visit2 = [False] * n
visit1[u-1] = True
visit2[v-1] = True

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

stack1 = [u-1]
stack2 = [v-1]

while stack1:
    l = stack1.pop(-1)
    for i in edges[l]:
        if visit1[i] == False:
            visit1[i] = True
            dis1[i] = dis1[l] + 1
            stack1.append(i)

while stack2:
    l = stack2.pop(-1)
    for i in edges[l]:
        if visit2[i] == False:
            visit2[i] = True
            dis2[i] = dis2[l] + 1
            stack2.append(i)

ans = 0

for i in range(n):
    if dis1[i] < dis2[i]:
        ans = max(ans, dis2[i])

print(ans-1)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, u, v = inpl()
u -= 1
v -= 1
edges = [set() for _ in range(N)]
AB = []
for i in range(N-1):
    A, B = inpl()
    edges[A-1].add(B-1)
    edges[B-1].add(A-1)

parent = [None]*N
position = [0]*N
depth = [0]*N
head, tail = 0, 1
pool = [(v, None, 0, head)]
while pool:
    n, p, d, pos = pool.pop()
    if pos == head:
        pool.append((n, p, d, tail))
        for c in edges[n]:
            if c == p:
                continue
            parent[c] = n
            position[c] = d+1
            pool.append((c, n, d+1, head))
    else:
        if p is not None:
            depth[p] = max(depth[n]+1, depth[p])

turn_d = position[u]//2 + 1
turn_node = u
for i in range(turn_d, position[u]):
    turn_node = parent[turn_node]

print(turn_d + depth[turn_node] - 1)

Solution (Python):
import queue

INF = 1 << 30

s = [-1, -1]
n, s[0], s[1] = map(int, input().split())
s[0] -= 1
s[1] -= 1

g = [[] for i 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)

cost = [[INF for j in range(n)] for i in range(2)]

for i in range(2):
    cost[i][s[i]] = 0
    que = queue.Queue(n)
    que.put(s[i])

    while not que.empty():
        now = que.get()
        for j in range(len(g[now])):
            if cost[i][g[now][j]] > cost[i][now] + 1:
                cost[i][g[now][j]] = cost[i][now] + 1
                que.put(g[now][j])

maxi = -1
maxdex = -1
for i in range(n):
    if len(g[i]) == 1 and maxi < cost[1][i] and cost[0][i] < cost[1][i]:
        maxi = cost[1][i]
        maxdex = i

dif = cost[1][maxdex] - cost[0][maxdex]

ans = cost[0][maxdex] + dif - 1
print(ans)

Solution (Python):
from collections import deque
N, ta, ao = map(int, input().split())  
ta -= 1
ao -= 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)

takahashi_distant = [10**9] * N
aoki_distant = [10**9] * N


q = deque([ta])
takahashi_distant[ta] = 0
visited = [False] * N
visited[ta] = True
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        takahashi_distant[e] = takahashi_distant[v] + 1
        q.append(e)


q = deque([ao])
aoki_distant[ao] = 0
visited = [False] * N
visited[ao] = True
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        aoki_distant[e] = aoki_distant[v] + 1
        q.append(e)




ans = 0
for i in range(N):
    if aoki_distant[i] > takahashi_distant[i]:
        ans = max(ans, aoki_distant[i])
print(ans-1)

Solution (Python):
from collections import deque

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

def bfs(x):
    dist = [-1]*n
    dist[x] = 0
    que = deque([x])
    while que:
        now = que.pop()
        for nex in G[now]:
            if dist[nex] != -1:continue
            dist[nex] = dist[now] + 1
            que.appendleft(nex)
    return dist

dist_u = bfs(u)
dist_v = bfs(v)

ans = 0
for i in range(n):
    if dist_u[i] < dist_v[i]:
        ans = max(ans,dist_v[i]-1)

print(ans)

Solution (Python):
from collections import deque
n,u,v=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
Q=deque([v-1])
Vert=[[0,0] for i in range(n)]
visited=[False]*n
visited[v-1]=True
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][0]=Vert[V][0]+1
    Q.append(i)
visited=[False]*n
visited[u-1]=True
Q.append(u-1)
while Q:
  V=Q.popleft()
  visited[V]=True
  for i in graph[V]:
    if visited[i]:continue
    if i == V:continue
    Vert[i][1]=Vert[V][1]+1
    Q.append(i)
ans=0
for i in Vert:
  if i[0]>i[1]:
    if i[0]>ans:
      ans=i[0]
print(ans-1)

Solution (Python):
from collections import deque
N,ppl,oni = map(int,input().split())
ppl -= 1
oni -= 1
AB = [ []for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    AB[a-1].append(b-1)
    AB[b-1].append(a-1)

def dfs(start):
    dist = [-1 for i in range(N)]
    dist[start] = 0
    que = deque()
    que.append(start)
    while que:
        q = que.popleft()
        for nextr in AB[q]:
            if dist[nextr] == -1:
                dist[nextr] = dist[q] +1
                que.append(nextr)
    return dist
    
if len(AB[ppl]) == 1 and oni in AB[ppl]:
    print(0)
else:
    ppldist = dfs(ppl)
    onidist = dfs(oni)
    maxa = max(onidist)
    ans = 0
    for i in range(N):
        if ppldist[i] < onidist[i]:
            ans = max(ans,onidist[i]-1)
    print(ans)

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

dist1 = [100005]*(n+1)

q = []
q.append(v)
dist1[v] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist1[next] == 100005:
            q.append(next)
            dist1[next] = dist1[now] + 1


dist2 = [100005]*(n+1)

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1

for i in range(1, n+1):
    if dist1[i] <= dist2[i]:
        dist2[i] = -1

for i in range(1, n+1):
    if dist2[i] != -1:
        dist2[i] = 100005

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1



ans = 0
for i in range(1, n+1):
    if dist2[i] != -1:
        ans = max(ans, dist1[i])

print(ans-1)

Solution (Python):
def bfs(k):
    flag=[-1]*(n+1)
    que=[k]
    flag[k]=0
    cnt=1
    while que:
        h=[]
        for uu in que:
            for vv in data[uu]:
                if flag[vv]==-1:
                    flag[vv]=cnt
                    h.append(vv)
        que=h
        cnt+=1
    return flag

n,u,v=map(int,input().split())
data=[[] for i in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
T=bfs(u)
A=bfs(v)
ans=0
for i in range(1,n+1):
    if T[i]<A[i]:
        ans=max(ans,A[i]-1)
print(ans)

Solution (Python):

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

def dfs_deep_measure(st, n, reach):
    deep = [-1] * n
    check = [0] * n
    stack = [st]
    check[st] = 1
    deep[st] = 0
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                deep[i] = deep[tmp]+1
    return deep

a_route = dfs_deep_measure(v, n, reach)
t_route = dfs_deep_measure(u, n, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i] < a_route[i]:
        ans = max(ans, a_route[i]-1)

print(ans)

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

def x_route(x, reach):
    x_route = [-1] * n
    check = [0] * n
    stack = [x]
    check[x] = 1
    x_route[x] = 0
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] != 1:
                stack.append(i)
                check[i] = 1
                x_route[i] = x_route[tmp]+1
    return x_route

a_route = x_route(v, reach)
t_route = x_route(u, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i] < a_route[i]:
        ans = max(ans, a_route[i]-1)

print(ans)

Solution (Python):

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

def x_route(x, reach):
    x_route = [[-1, -1] for _ in range(n)]
    check = [0] * n
    stack = [x]
    check[x] = 1
    x_route[x] = [-1, 0]
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] == 1:
                pass
            else:
                stack.append(i)
                check[i] = 1
                x_route[i] = [tmp, x_route[tmp][1]+1] 
    return x_route

a_route = x_route(v, reach)
t_route = x_route(u, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Solution (Python):

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

def x_route(x, reach):
    x_route = [[-1, -1] for _ in range(n)]
    check = [0] * n
    stack = [x]
    check[x] = 1
    x_route[x] = [-1, 0]
    while len(stack) > 0:
        tmp = stack.pop(-1)
        tmp_list = reach[tmp]
        for i in tmp_list:
            if check[i] == 1:
                pass
            else:
                stack.append(i)
                check[i] = 1
                x_route[i] = [tmp, x_route[tmp][1]+1] 
    return x_route

a_route = x_route(v, reach)
t_route = x_route(u, reach)
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Solution (Python):

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

a_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [v]
check[v] = 1
a_route[v] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            a_route[i] = [tmp, a_route[tmp][1]+1]

t_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [u]
check[u] = 1
t_route[u] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            t_route[i] = [tmp, t_route[tmp][1]+1]
    
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Solution (Python):

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




a_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [v]
check[v] = 1
a_route[v] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            a_route[i] = [tmp, a_route[tmp][1]+1]

tmp = -1
for i in range(len(a_route)):
    if a_route[i][1] > tmp:
        tmp = a_route[i][1]
        AA = i

aoki_A = [AA]
tmp = AA
while True:
    tmp = a_route[tmp][0]
    if tmp == -1:
        break
    aoki_A.append(tmp)
"""
print('aoki')
print(a_route)
print('AA', AA)
print(aoki_A)
print('------------------')
"""




t_route = [[-1, -1] for _ in range(n)]
check = [0] * n
stack = [u]
check[u] = 1
t_route[u] = [-1, 0]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            t_route[i] = [tmp, t_route[tmp][1]+1]

takahashi_A = [AA]
tmp = AA
while True:
    tmp = t_route[tmp][0]
    if tmp == -1:
        break
    takahashi_A.append(tmp)
"""
print('takahashi')
print(t_route)
print(AA)
print(takahashi_A)
print('---------------')
"""



tmp = -1
CC = -1
for i in range(min(len(aoki_A), len(takahashi_A))):
    if aoki_A[i] != takahashi_A[i]:
        CC = tmp
        break
    tmp = aoki_A[i]
"""
print('CC', CC)
('----------------------------------')
"""



x_route = [[-1, -1, -1] for _ in range(n)]
check = [0] * n
stack = [CC]
check[CC] = 1
x_route[CC] = [-1, 0, -1]

while len(stack) > 0:
    tmp = stack.pop(-1)
    tmp_list = reach[tmp]
    for i in tmp_list:
        if check[i] == 1:
            pass
        else:
            stack.append(i)
            check[i] = 1
            x_route[i] = [tmp, x_route[tmp][1]+1, x_route[tmp][2]]
            if i == u:
                x_route[i] = [tmp, x_route[tmp][1]+1, 1]

tmp = -1
for i in range(len(x_route)):
    if x_route[i][1] > tmp and x_route[i][2] == 1:
        tmp = x_route[i][1]
        BB = i
"""
print('CC - BB')
print(x_route)
print('BB', BB)
"""


('
dai = [AA, BB, CC]
aoki = []
takahashi = []
for i in range(3):
    aoki.append(a_route[dai[i]][1])
    takahashi.append(t_route[dai[i]][1])
"""
print(aoki)
print(takahashi)
"""
"""

if takahashi[2] < aoki[2]:
    print(aoki[0]-1)
else:
    print(max(aoki[2], aoki[1]-1))






"""
    
ans = 0
for i in range(len(a_route)):
    if t_route[i][1] < a_route[i][1]:
        ans = max(ans, a_route[i][1]-1)

print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[考察]
　高橋君が最も遠くに逃げる場合
　:= (高橋君が先に行ける頂点)Λ(青木君から最も遠い頂点)

⇒高橋君が先に行ける頂点
　高橋君からの各頂点の距離(高橋君を根としたときの木の深さ),
　青木君からの各頂点の距離(青木君を根としたときの木の深さ)を求めて、
　高橋君からの距離と青木君からの距離を比較
⇒青木君から最も遠い頂点
　青木君からの各頂点の距離の最大値
"""
n,V,U = LI()
V -= 1
U -= 1

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

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
else:
    depth_v = [None]*n
    depth_v[V] = 0
    que = deque()
    que.append(V)
    while que:
        v = que.popleft()
        for u in edges[v]:
            if depth_v[u] == None:
                depth_v[u] = depth_v[v]+1
                que.append(u)
    
    depth_u = [None]*n
    depth_u[U] = 0
    que = deque()
    que.append(U)
    while que:
        u = que.popleft()
        for v in edges[u]:
            if depth_u[v] == None:
                depth_u[v] = depth_u[u] + 1
                que.append(v)
    
    ans = 0
    for v in range(n):
        if depth_v[v] < depth_u[v]:
            ans = max(ans,depth_u[v]-1)
    print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,V,U = LI()
V -= 1
U -= 1

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

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

if n == 2:
    print(0)
else:
    depth_v = [None]*n
    depth_v[V] = 0
    que = deque()
    que.append(V)
    while que:
        v = que.popleft()
        for u in edges[v]:
            if depth_v[u] == None:
                depth_v[u] = depth_v[v]+1
                que.append(u)
    
    depth_u = [None]*n
    depth_u[U] = 0
    que = deque()
    que.append(U)
    while que:
        u = que.popleft()
        for v in edges[u]:
            if depth_u[v] == None:
                depth_u[v] = depth_u[u] + 1
                que.append(v)
    
    ans = 0
    for v in range(n):
        if depth_v[v] < depth_u[v]:
            ans = max(ans,depth_u[v]-1)
    print(ans)

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

ans = 0
if u==v:
    print(0)
    exit()


r = []
parent = [-1]*N
def dfs(root,end):
    global r
    stack = []
    stack.append(root)
    parent[root] = root
    while len(stack)>0:
        p = stack.pop()
        if p==end:
            break
        for e in E[p]:
            if parent[e]==-1:
                parent[e] = p
                stack.append(e)
    p=end
    while p!=root:
        r.append(p)
        p = parent[p]
    r.append(root)

dfs(v,u)
ans += (len(r)//2)+(len(r)&1)
v = r[len(r)//2]
u = r[(len(r)//2)-1]


dmax = 0
depth = [-1]*N
def dfs2(root,end,d):
    global dmax
    stack = []
    stack.append(root)
    depth[root] = d
    depth[end] = 0
    while len(stack)>0:
        p = stack.pop()
        for e in E[p]:
            if depth[e]==-1:
                depth[e] = depth[p]+1
                dmax = max(dmax,depth[e])
                stack.append(e)

dfs2(u,v,0)
ans += dmax - 1

print(ans)

Solution (Python):
n,u,v=map(int,input().split())
u-=1
v-=1
path=[[] for _ in range(n)]
for i in range(n-1):
  a,b = [int(x)-1 for x in input().split()]
  path[a].append(b)
  path[b].append(a)
parent = [-1]*n
rank = [-1]*n
que = []
que.append(v)
rank[v]=0

while(que):
  cur = que.pop()
  for nxt in path[cur]:
    if rank[nxt]==-1:
      rank[nxt]=rank[cur]+1
      parent[nxt]=cur
      que.append(nxt)
up = (rank[u]-1)//2
upto=u
for i in range(up):
  upto = parent[upto]
depth=0
que = [upto]
while(que):
  cur = que.pop()
  if len(path[cur])==1:
    depth = max(depth,rank[cur])
  else:
    for nxt in path[cur]:
      if nxt != parent[cur]:
        que.append(nxt)
print(depth-1)

Solution (Python):
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  
rs = lambda: stdin.readline().rstrip()  

N, U, V = rl()
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = rl()
    edges[a].append(b)
    edges[b].append(a)

def dfs(v):
    dist = [-1] * (N+1)
    dist[v] = 0
    stack = []
    stack.append(v)
    while stack:
        s = stack.pop()
        for t in edges[s]:
            if dist[t] >= 0:
                continue
            dist[t] = dist[s] + 1
            stack.append(t)
    return dist

DU, DV = dfs(U), dfs(V)
answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if v > u:
        x = v - 1
        if x > answer:
            answer = x

print(answer)

Solution (Python):
N,U,V=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
inf=10**20
c=[[] for i in range(N)]
for u,v in AB:
    c[u-1].append(v-1)
    c[v-1].append(u-1)
from heapq import heappop,heappush
def dij(c,N,s):
    d=[inf]*N
    d[s]=0
    prev=[-1]*N
    q=[]
    heappush(q,(0,s))
    while q:
        u=heappop(q)[1]
        for v in c[u]:
            temp=d[u]+1
            if d[v]>temp:
                d[v]=temp
                prev[v]=u
                heappush(q,(d[v],v))
    return d
d1=dij(c,N,U-1)
d2=dij(c,N,V-1)
r=0
for i in range(N):
    if d1[i]<d2[i]:
        r=max(r,d2[i]-1)
print(0 if len(c[U-1])==1 and c[U-1][0]==V-1 else r)

Solution (Python):


def solve(N, t, a, g) -> int:
    import sys

    sys.setrecursionlimit(10 ** 7)

    def calc_dist(init):
        dist = [-1] * N
        dist[init] = 0

        def _calc_dist(curr):
            for next_ in g[curr]:
                if dist[next_] != -1:
                    continue
                dist[next_] = dist[curr] + 1
                _calc_dist(next_)

        _calc_dist(init)
        return dist

    dist_a = calc_dist(a)
    dist_t = calc_dist(t)

    return max(dist_a[v] for v in range(N) if dist_t[v] < dist_a[v]) - 1


if __name__ == '__main__':
    N, t, a = map(int, input().split())
    t -= 1
    a -= 1

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    print(solve(N, t, a, g))

Solution (Python):
def dfs(g,root,ds):
    q = [root]
    ds[root] = 0
    while q:
        v = q.pop()
        for c in g[v]:
            if ds[c] == -1:
                ds[c] = ds[v] + 1
                q.append(c)
        





import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 

n,u,v = [int(i) for i in readline().split()]
u -= 1
v -= 1
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
ds = [-1]*n
dg = [-1]*n

dfs(g,u,ds)
dfs(g,v,dg)



ans = 0
for i,j in zip(ds,dg):
    if i < j: ans = max(j-1,ans)
    
print(ans)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


import collections
import itertools
edge = collections.namedtuple("edge", ["src", "to", "cost"])









class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append(root)
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v]:
                if u.to != self.parent(v):
                    self.par[0][u.to] = v
                    self.depth[u.to] = self.depth[v] + 1
                    que.append(u.to)

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i, j in itertools.product(range(self._l - 1), range(self.size)):
            if(self.par[i][j] == -1):
                self.par[i + 1][j] = -1
            else:
                self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    ans = -1
    
    
    
    
    
    g.build(v)
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()