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
path = [] 
for _ in range(N):
    path.append([])
for _ in range(N - 1):
    A, B = map(int,input().split())
    A, B = A - 1, B - 1
    path[A].append(B)
    path[B].append(A)
dep = [0] * N
dep[v] = 1
leaf = []
stack2 = [v]
cnt = 2
while stack2:
    stack = stack2[0:]
    stack2 = []
    while stack:
        s = stack.pop()
        for to in path[s]:
            judge = len(path[s])
            if dep[to]:
                judge -= 1
                if judge == 0:
                    leaf.append([cnt - 1, s])
                continue
            dep[to] = cnt
            stack2.append(to)
            judge += 1 
    cnt += 1
leaf.sort(reverse=True)
depmax = [0] * N
for i in range(len(leaf)):
    depth, a = leaf[i][0], leaf[i][1] 
    depmax[a] = depth
    end = False
    for j in range(depth - 1, 0, -1):
        if end:
            break
        for b in path[a]:
            if dep[b] == j:
                if depmax[b] < depmax[a]:
                    depmax[b] = depmax[a]
                    a = b
                    break
                else:
                    end = True
                    break
dis = dep[u] - 2
leng = depmax[u]
a = u
for depth in range(dep[u] - 1, dep[u] - 1 - (dis // 2), -1):
    for to in path[a]:
        if depth == dep[to]:
            leng = depmax[to]
            a = to
print(leng - 2)

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, w = n, n - 1 

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

for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = -1

for i, j in zip(takahashi, aoki):
    if j - i > 0:
        ans = max(ans, j - 1)

print(ans)

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

n, u, v = [int(x) for x in input().split()]

import heapq
def dijkstra_heap(s):
    
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, w = n, n - 1 

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

for i in range(w):
    x,y = map(int,input().split())
    z = 1
    edge[x - 1].append([z,y - 1])
    edge[y - 1].append([z,x - 1]) 

takahashi = dijkstra_heap(u - 1)
aoki = dijkstra_heap(v - 1)

ans = takahashi[v - 1] - 1 

idx = 0
for i, j in zip(takahashi, aoki):
    if idx == u - 1 or idx == v - 1:
        idx += 1
        continue
    if j - i > 0:
        ans = max(ans, j - 1)
    idx += 1

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

def main():
	N, u, v = MAP()

	tree = [[] for _ in range(N)]
	for _ in range(N-1):
		A, B = MAP()
		tree[A-1].append((B-1, 1))
		tree[B-1].append((A-1, 1))

	d_t = dijkstra(tree, u-1)
	d_a = dijkstra(tree, v-1)
	
	ans = -1
	for i in range(N):
		if d_t[i] <= d_a[i]:  
			ans = max(ans, d_a[i])
	print(ans-1)

if __name__ == '__main__':
	main()

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

tree=[]
for i in range(N+1):
  tree.append([])

for i in range(N-1):
  A,B=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)



dist_tak=[-1]*(N+1)
queue=[u]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_tak[q]==-1:
      dist_tak[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue


dist_aok=[-1]*(N+1)
queue=[v]
d=0
while(len(queue)>0):
  new_queue=set()  
  for q in queue:
    if dist_aok[q]==-1:
      dist_aok[q]=d
      for q2 in tree[q]:
        new_queue.add(q2)
  d+=1
  queue=new_queue


answer=0
for i in range(1,N+1):
  if dist_tak[i]<dist_aok[i]:
    answer=max(answer,dist_aok[i]-1)
    
print(answer)

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


def input():
    return sys.stdin.readline()


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

uu = [0] * n
vv = [0] * n


def dfs(ve, r=u, d=0, rr=-1):
    ve[r] = d
    for i in e[r]:
        if i == rr:
            continue
        dfs(ve, i, d + 1, r)


dfs(uu, u)
dfs(vv, v)


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

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

def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)

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

Solution (Python):
import sys
n,u,v=map(int,input().split())
sys.setrecursionlimit(10**9)
tree=[[] for i 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)
a=[None]*n
t=[None]*n
t[u-1]=0
a[v-1]=0
def dfsA(x,c):
  for i in tree[x]:
    if a[i]==None:
      a[i]=c
      dfsA(i,c+1)
dfsA(v-1,1)
k=a[u-1]
def dfsT(x,c):
  global k
  for i in tree[x]:
    if t[i]==None and c<a[i]:
      t[i]=c
      if k<a[i]:
        k=a[i]
      dfsT(i,c+1)
dfsT(u-1,1)
print(k-1)

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

class Node:
    def __init__(self, num):
        self.link = []
        self.costs = [num, num]
        self.check = False

def clear_nodes(nodes):
    for node in nodes:
        node.check = False

def main():
    N, u, v = map(int, input().split())

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

    for i in range(N-1):
        a, b = map(int, input().split())
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    
    starts = [u, v]
    for i in range(2):
        clear_nodes(nodes)
        q = deque()
        q.append((nodes[starts[i]], 0))
        while len(q) > 0:
            node, cost = q.popleft()
            node.costs[i] = cost
            for next_node in node.link:
                if not next_node.check:
                    q.append((next_node, cost + 1))
                    next_node.check = True

    if nodes[u].costs[1] == 1:
        print(0)
        return

    clear_nodes(nodes)
    q = deque()
    ans = 0
    q.append(nodes[u])
    while len(q) > 0:
        node = q.popleft()
        ans = max(ans, node.costs[1])
        for next_node in node.link:
            if (not next_node.check) and next_node.costs[0] < next_node.costs[1]:
                q.append(next_node)
                next_node.check = True
    print(ans - 1)

    


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge,n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = [[] for i in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        edge[A].append([1,B])
        edge[B].append([1,A])
    
    d1 = dijkstra_heap(u,edge, N)
    d2 = dijkstra_heap(v,edge, N)
    ans = 0
    for i in range(N):
        if d1[i] < d2[i]:
            ans = max(ans, d2[i]-1)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


def main():
    N, u, v = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    move = [-1] * N
    q = deque([(v-1, 0)])
    while len(q):
        cur, c = q.popleft()
        move[cur] = c
        for nxt in adj[cur]:
            if move[nxt] == -1:
                q.append((nxt, c+1))
    reachable = [False] * N
    q = deque([(u-1, 0)])
    while len(q):
        cur, c = q.popleft()
        reachable[cur] = True
        for nxt in adj[cur]:
            if c+1 <= move[nxt] and not reachable[nxt]:
                q.append((nxt, c+1))
    ans = 0
    for i in range(N):
        if reachable[i] and len(adj[i]) >= 2:
            ans = max(ans, move[i])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


N, u, v = MI()
nl = [list() for _ in range(N)]
for _ in range(N - 1):
    a, b = MI()
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)


def distance(v0):
    dist = [0] * N
    q = deque([(v0, -1, 0)])
    while len(q) > 0:
        v, p, d = q.popleft()
        dist[v] = d
        for next_v in nl[v]:
            if next_v != p:
                q.append((next_v, v, d + 1))
    return dist


t = distance(u - 1)
a = distance(v - 1)
initial_dist = t[v - 1]

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

Solution (Python):
import sys
input=sys.stdin.readline
n,u,v = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()
Q.append([v-1,0])
visited=[-1]*n
visited[v-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=cnt+1
        Q.append([nxt,cnt+1])
Q = deque()
Q.append([u-1,0])
v_taka=[-1]*n
v_taka[u-1]=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if v_taka[nxt]!=-1:
            continue
        if visited[nxt] <= cnt+1:
            continue
        v_taka[nxt]=cnt+1
        Q.append([nxt,cnt+1])
ans=-1
for i in range(n):
    if v_taka[i] == -1:
        continue
    if ans < visited[i]:
        ans=visited[i]
print(ans-1)

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

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

def dfs(s,b=-1): 
    for i in Graph[s]: 
        if i!=b: 
            depth[i]=depth[s]+1 
            dfs(i,s) 

depth=[0]*n
dfs(u-1)
dT=depth

depth=[0]*n
dfs(v-1)
dA=depth

dArrest=0
for i in range(n):
    if dA[i]>dT[i]: 
        dArrest=max(dArrest,dA[i]) 
print(dArrest-1)

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

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

def dfs(s,b=-1): 
    for i in Graph[s]: 
        if i!=b: 
            depth[i]=depth[s]+1
            dfs(i,s) 

depth=[0]*n
dfs(u-1)
dT=depth

depth=[0]*n
dfs(v-1)
dA=depth

dArrest=0
for i in range(n):
    if dA[i]>dT[i]: 
        dArrest=max(dArrest,dA[i]) 
print(dArrest-1)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth_u=[0]*n 
    depth_v=[0]*n 
    
    def dfs1(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_u[e]=depth_u[i]+1
                dfs1(e,i)
    
    def dfs2(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth_v[e]=depth_v[i]+1
                dfs2(e,i)
    
    dfs1(u)
    dfs2(v)

    ans=depth_v[u]-1
    for i in range(n):
        if len(tree[i])==1 and depth_u[i]<depth_v[i]:
                ans=max(ans,depth_v[i]-1)
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
def main():
    from functools import lru_cache
    import sys
    input=sys.stdin.readline
    sys.setrecursionlimit(100000000)

    n,u,v=map(int,input().split())
    u-=1
    v-=1
    tree=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        tree[a].append(b)
        tree[b].append(a)
    
    depth=[0]*n
    depth[v]=0
    def dfs(i,before=-1):
        for e in tree[i]:
            if e!=before:
                depth[e]=depth[i]+1
                dfs(e,i)
    dfs(v)
    
    
    max_depth=[-1]*n
    max_depth[v]=0   
    @lru_cache(maxsize=None)
    def dfs2(i,before=-1):
        t=-1
        for e in tree[i]:
            if e!=before:
                t=max(t,dfs2(e,i))
        if t!=-1:
            max_depth[i]=t
            return max_depth[i]
        else:
            max_depth[i]=depth[i]
            return max_depth[i]
            
    dfs2(v)   
    
    
    lim=depth[u]
    i,key=u,u
    while i!=v:
        if 2*depth[i]>lim and max_depth[key] < max_depth[i]:
            key=i
            
        for e in tree[i]:
            if depth[e]<depth[i]:
                i=e
                break
                
    print(max_depth[key]-1) 
if __name__=='__main__':
    main()

Solution (Python):
import queue
def dist(graph, start):
    q = queue.Queue()
    rtn = [None]*len(graph)
    q.put(start)
    rtn[start] = 0
    while not q.empty():
        target = q.get()
        for index in graph[target]:
            if rtn[index] is None:
                q.put(index)
                rtn[index] = rtn[target] + 1
    return rtn

def solve(dist_t, dist_a):
    ans = 0
    for i in range(len(dist_t)):
        if dist_t[i] < dist_a[i]:
            if ans < dist_a[i] - 1:
                ans = dist_a[i] - 1
    return ans

def main():
    n, u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    dist_t = dist(graph, u)
    dist_a = dist(graph, v)
    print(solve(dist_t, dist_a))

if __name__ == "__main__":
    main()

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

def bfs(u):
    d = [-1]*n
    stack = deque([u])
    d[u] = 0
    while len(stack)!=0:
        s = stack.popleft()
        for t in dist[s]:
            if d[t]==-1:
                d[t] = d[s]+1
                stack.append(t)
    return d

A = bfs(v)
T = bfs(u)
ans=0
for i in range(n):
    if A[i]>T[i]:
        ans = max(A[i]-1, ans)
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N,u,v=map(int,input().split())
s=[[]for i in range(N)]
for i in range(N-1):
    A,B=map(lambda x: int(x)-1,input().split())
    s[A].append(B)
    s[B].append(A)
a=[None]*N
t=[None]*N
t[u-1]=0
a[v-1]=0
def hu(n,c):
    for i in s[n]:
        if a[i]==None:
            a[i]=c
            hu(i,c+1)
hu(v-1,1)
A=0
k=a[u-1]
def hu2(n,c):
    global k
    for i in s[n]:
        if t[i]==None and c<a[i]:
            t[i]=c
            if k<a[i]:
                k=a[i]
            hu2(i,c+1)
hu2(u-1,1)
print(k-1)

Solution (Python):
from collections import *
import copy
N,v,u=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

stack=deque([[v,0]])
visited=set([v])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==u:
            K=m+1
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])


for i in range(len(data)):
    if len(data[i])>1:
        visited=set([i])
        stack=deque([i])
        End=set()
        break

if N==2:
    print(0)
    exit()
while stack:
    a=stack.popleft()
    flag=0
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append(p)
            flag=1
    if flag==0:
        End.add(a)

Uvisited=set([u])
Vvisited=set([])
if not v in End:
    Vvisited.add(v)
Ustack=deque([[u,0]])
Vstack=deque([[v,0]])
ans=[]
M=1

while Ustack:
    while Vstack:
        a,m=Vstack.popleft()
        if m==M:
            Vstack.append([a,m])
            break
        for p in data[a]:
            if not p in End:
                if p in Uvisited:
                    pass
                    
                elif not p in Vvisited:
                    Vvisited.add(p)
                    Vstack.append([p,m+1])
    while Ustack:
        a,m=Ustack.popleft()
        if m==M:

            Ustack.append([a,m])
            break
        for p in data[a]:

            if not p in Uvisited:
                if p in Vvisited:
                    ans.append(m+1)
                Uvisited.add(p)
                Ustack.append([p,m+1])
    M+=1
print(max(ans))

Solution (Python):
N,u,v = map(int, input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    s,t = map(int, input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)


def expro(u):
    D=[0]*N
    D[u]=0
    S=[]
    S.append(u)
    L=[]
    q=0
    while(q<N):
        l=S[q]
        for i in range(len(G[l])):
            m=G[l][i]
            if(len(G[l])==1 and l!=u):
                L.append(l)
            if(D[m]==0 and m!=u):
                D[m]=D[l]+1
                S.append(m)
        
        q+=1
    return L,D
L,D = expro(u-1)
M,E = expro(v-1)
k=0
ans=0



for i in M:
    if D[i]<E[i]:
        if k<E[i]:
            k=E[i]
            ans=E[i]-1
print(ans)

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

def dfs(u):
  for v in g[u]:
    if checked[v]==1:
      continue
    else:
      checked[v]=1
      depth2[u]=max(depth2[u],dfs(v)+1)
  return depth2[u]

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)
depth=[0]*(n+1)
checked=[0]*(n+1)
checked[v]=1
q=collections.deque()
q.append((v,0))
while 1:
  if len(q)==0:
    break
  tu,d=q.popleft()
  checked[tu]=1
  depth[tu]=d
  for tv in g[tu]:
    if checked[tv]!=1:
      checked[tv]=1
      q.append((tv,d+1))
moves=(depth[u]-1)//2
depth2=[0]*(n+1)
checked=[0]*(n+1)
checked[v]=1
dfs(v)
checked=[0]*(n+1)
checked[u]=1
q=collections.deque()
q.append((u,0))
cand=[]
while 1:
  if len(q)==0:
    break
  tu,d=q.popleft()
  if d==moves:
    cand.append(tu)
  checked[tu]=1
  for tv in g[tu]:
    if checked[tv]!=1:
      checked[tv]=1
      q.append((tv,d+1))
md=0
for i in cand:
  md=max(md,depth2[i])
if depth[u]%2!=0:
  ans=moves+md
else:
  ans=moves+md+1
print(ans)

Solution (Python):
from collections import deque


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())
    edge[A - 1].append(B - 1)
    edge[B - 1].append(A - 1)

INF = 10 ** 6
lenA = [INF] * N
q = deque()
q.append((v, 0))
lenA[v] = 0
while len(q) > 0:
    p, step = q.popleft()
    for np in edge[p]:
        if lenA[np] == INF:
            lenA[np] = step + 1
            q.append((np, step + 1))


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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20

def dfs(graph, root, n):
    dista = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    dista[root - 1] = 0
    visited[root - 1] = 1
    d = deque()
    for edge in graph[root - 1]:
        d.append(edge)
    while(d):
        cur, nxt = d.pop()
        if not visited[nxt]:
            dista[nxt] = dista[cur] + 1
            visited[nxt] = 1
            for edge in graph[nxt]:
                d.append(edge)

    return dista

def dfs2(graph, root, n, dista):
    distb = [INF for i in range(n)]
    visited = [0 for i in range(n)]
    visited[root - 1] = 1
    distb[root-1] = 0
    d = deque()
    ans = dista[root-1]
    dec = 0
    
    for edge in graph[root-1]:
        d.append(edge)
    while(d):
        
        
        cur, nxt = d.pop()
        if not visited[nxt]:
            if distb[cur] + 1 <= dista[nxt]:
                if distb[cur] + 1 == dista[nxt]:
                    dec = 1
                visited[nxt] = 1
                distb[nxt] = distb[cur] + 1
                for edge in graph[nxt]:
                    d.append(edge)
                if ans < dista[nxt]:
                    ans = dista[nxt]

            

    return ans

def main():
    n, u, v = getList()
    graph = [[] for i in range(n)]
    dista = [INF for i in range(n)]
    distb = [INF for i in range(n)]
    for i in range(n-1):
        a,b = getList()
        graph[a-1].append((a-1, b-1))
        graph[b - 1].append((b-1, a - 1))
    
    if n == 3:
        print(1)
        return
    dista = dfs(graph, v, n)
    
    print(dfs2(graph, u, n, dista) - 1)
if __name__ == "__main__":
    main()

Solution (Python):
n, r0, g0 = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n-1)]

connects = [[] for i in range(n+1)]
for e in edges:
    connects[e[0]].append(e[1])
    connects[e[1]].append(e[0])    

rL, gL = [-1]*(n+1), [-1]*(n+1)
rL[r0], gL[g0] = 0, 0

from collections import deque
rQ, gQ = deque([r0]), deque([g0])

for L, Q in [(rL, rQ), (gL, gQ)]:
    while Q:
        node = Q.popleft()
        for ni in connects[node]:
            if L[ni] == -1:
                L[ni] = L[node] + 1
                
                Q.append(ni)

print(max(gL[i] for i in range(1, n+1) if rL[i] < gL[i]) - 1)

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

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

for i in range(N-1):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    data[A].append(B)
    data[B].append(A)



stack = [[u,u]]
taka_dis = [0] * N
while stack:
    x = stack.pop()
    
    for y in data[x[1]]:
        if y == x[0]:
            continue
        else:
            stack.append([x[1],y])
            taka_dis[y] = taka_dis[x[1]] + 1
    

stack = [[v,v]]
aoki_dis = [0] * N
while stack:
    x = stack.pop()
    for y in data[x[1]]:
        if y == x[0]:
            continue
        else:
            stack.append([x[1],y])
            aoki_dis[y] = aoki_dis[x[1]] + 1
    
can = [0] * N

for i in range(N):
    if aoki_dis[i] - taka_dis[i] > 0:
        can[i] = aoki_dis[i]
    else:
        can[i] = 0




print(max(can) -1 )

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

def make_adlist(n):
  adlist = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    adlist[a] += [b] 
    adlist[b] += [a]
  return adlist

def dfs(adlist, s, dist, d):
  for nxt in adlist[s]:
    if dist[nxt] == -1:
      dist[nxt] = d
      dfs(adlist, nxt, dist, d+1)

def main():
  n, u, v = map(int, input().split())
  u -= 1
  v -= 1
  adlist = make_adlist(n)
  t_dist = [-1]*n
  t_dist[u] = 0
  dfs(adlist, u, t_dist, 1)
  a_dist = [-1]*n
  a_dist[v] = 0
  dfs(adlist, v, a_dist, 1)
  ans = 0 
  for i in range(n):
    if t_dist[i] < a_dist[i]:
      ans = max(ans, a_dist[i]-1)
  print(ans)

if __name__ == "__main__":
  main()

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, u, v = na()
u -= 1; v -= 1
g = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = na()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

def dfs(v):
    dist = [-1] * n
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in g[v]:
            if dist[w] == -1:
                dist[w] = dw
                stack.append(w)
    return dist

dist_v = dfs(v)
dist_u = dfs(u)
ans = 0
for rv, ru in zip(dist_v, dist_u):
    if rv > ru:
        ans = max(ans, rv-1)
print(ans)

Solution (Python):
from collections import deque
n,u,v = map(int,input().split())
l = [[]for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([l[u],u])
while len(d):
    l0,now = d.popleft()
    for i in l0:
        if i == u:
            continue
        elif rl[i] == 0:
            rl[i] = rl[now] + 1
            d.append([l[i],i])
rl2 = [0 for i in range(n+1)]
d = deque()
d.append([l[v],v])
while len(d):
    l0,now = d.popleft()
    for i in l0:
        if i == v:
            continue
        elif rl2[i] == 0:
            rl2[i] = rl2[now] + 1
            d.append([l[i],i])
dis = rl[v]
nl = []
for i in range(n+1):
    nl.append([rl2[i],i])
nl.sort(key=lambda x:x[0],reverse=True)
for i in range(n+1):
    if nl[i][0] > rl[nl[i][1]]:
        ans = nl[i][0]-1
        break
print(ans)

Solution (Python):
from collections import deque
n, u, v = list(map(int, input().split()))
a = [[] for _ in range(n+1)]
for _ in range(n-1):
  x, y = map(int, input().split())
  a[x].append(y)
  a[y].append(x)
  
def dis(a,v):
  d = [[1,0] for _ in range(n+1)]
  c = 1
  for i in a[v]:
    d[i][0] = 1
    d[i][1] = c
    c += 1
  b = deque(a[v])
  while b:
    x = b.pop()
    for i in a[x]:
      if d[i][1] == 0:
        d[i][0] = d[x][0] + 1
        d[i][1] = d[x][1]
        b.append(i)
  d[v] = [0,0]
  return d

du = dis(a,u)
dv = dis(a,v)
dis = max([dv[i][0] for i in range(n+1) if dv[i][1]==dv[u][1] and dv[i][0]>du[i][0]])
print(dis-1)

Solution (Python):
from collections import defaultdict, deque
N, u, v = map(int, input().split())
u -= 1
v -= 1
dic = defaultdict(list)
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [b-1]
  dic[b-1] += [a-1]
dist1 = [float('inf')]*N
dist2 = [float('inf')]*N
q1 = deque([u])
q2 = deque([v])
dist1[u] = 0
dist2[v] = 0
while q1:
  e = q1.popleft()
  for p in dic[e]:
    if dist1[p]>dist1[e]+1:
      dist1[p] = dist1[e]+1
      q1 += [p]

while q2:
  e = q2.popleft()
  for p in dic[e]:
    if dist2[p]>dist2[e]+1:
      dist2[p] = dist2[e]+1
      q2 += [p]

ans = -1
j = 0
for i in range(N):
  if ans<dist2[i]-1 and dist1[i]<dist2[i]:
    ans = dist2[i]-1
if u==v:
  ans = 0
print(ans)