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

Solution (Python):
from collections import deque
n,u,v = map(int,input().split())
branch = [list(map(int,input().split())) for _ in range(n-1)]
link = [[] for _ in range(n)]
for i in branch:
    link[i[0]-1].append(i[1]-1)
    link[i[1]-1].append(i[0]-1)

q_a = deque([u-1])
q_b = deque([v-1])
dist_a = [-1 for _ in range(n)]
dist_b = [-1 for _ in range(n)]
dist_a[u-1] = 0
dist_b[v-1] = 0
while q_a:
    check = q_a.popleft()
    for j in link[check]:
        if dist_a[j] == -1:
            dist_a[j] = dist_a[check]+1
            q_a.append(j)
while q_b:
    check = q_b.popleft()
    for m in link[check]:
        if dist_b[m] == -1:
            dist_b[m] = dist_b[check]+1
            q_b.append(m)

ans = 0
for k in range(n):
    compare = 0
    if dist_b[k]>dist_a[k]:
        compare = dist_b[k]-1

    if compare > ans:
        ans = compare

print(ans)

Solution (Python):
class LCA(object):
    def __init__(self, n, root, edges, decrement=True):
        """
        :param n: 頂点数
        :param root: 木の根
        :param edges: 辺のリスト
        :param decrement:

        :param self.depth: rootを根とした時の各頂点の深さ
        """
        self.n = n
        self.decrement = decrement
        self.root = root - self.decrement
        self.edges = [set() for _ in range(self.n)]
        for x, y in edges:
            self.add_edge(x,y)
        self.k_max = (self.n - 1).bit_length()
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.parent = [-1]*self.n
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

    def add_edge(self, x, y):
        """
        後から追加した場合は update() をする
        """
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        self.edges[y].add(x)

    def update(self):
        self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
        self.doubling = [[-1] * self.n for _ in range(self.k_max)]
        self.dfs()
        for i in range(1, self.k_max):
            for k in range(self.n):
                if self.doubling[i - 1][k] != -1:
                    self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]


    def dfs(self):
        next_set = [self.root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] == -1:
                    self.depth[q] = self.depth[p] + 1
                    self.doubling[0][q] = p
                    next_set += [q]

    def get(self, u, v):
        """
        :return: u と v の最近共通祖先の頂点番号を返す
        """
        if self.decrement:
            u -= 1
            v -= 1
        if self.depth[v] < self.depth[u]:
            u, v = v, u

        for i in range(self.k_max):
            """ v を u の位置まで遡らせる """
            if (self.depth[v] - self.depth[u]) >> i & 1:
                v = self.doubling[i][v]
        if v == u:
            """ v の祖先が u だった場合"""
            return u + self.decrement

        for i in range(self.k_max-1, -1, -1):
            """ k = 2**(k_max-1), ..., 2**0 について、 
            「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返す"""
            parent_u, parent_v = self.doubling[i][u], self.doubling[i][v]
            if parent_u != parent_v:
                u, v = parent_u, parent_v
        return self.doubling[0][u] + self.decrement

    def distance(self, u, v):
        """
        :return: u と v の最短距離を求める
        備考: 経路復元をしようとすると O(E)かかるので、経路復元が必要な場合は dfs を用いるとよい
        """
        lca_at = self.get(u,v)
        if self.decrement:
            u -= 1
            v -= 1
            lca_at -= 1
        return self.depth[u] + self.depth[v] - 2*self.depth[lca_at]

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == xx-1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        if not save:
            self.parent = [-1] * self.n
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res


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

N, u, v = map(int, input().split())
edges = []
for _ in range(N-1):
    x, y = map(int, input().split())
    edges.append((x,y))
xx = -3
lca = LCA(N, 1, edges, decrement=True)
p = lca.get(u,v)
lu, lv = lca.depth[u-1] - lca.depth[p-1], lca.depth[v-1] - lca.depth[p-1]
if lu <= lv:
    q, _ = lca.most_distant_point(v)
    print(lca.distance(q,v)-1)
    exit()
else:
    L = (lu+lv)//2
    cnt = 0
    lca.distance_list()
    if lca.depth[u-1] >= lca.depth[v-1]:
        a = u-1
        while cnt < L:
            a = lca.parent[a]
            cnt += 1
        xx, s = lca.parent[a]+1, a+1
    else:
        a = v-1
        while cnt < L+1:
            a = lca.parent[a]
            cnt += 1
        xx, s = a+1, lca.parent[a]+1
    q, _ = lca.most_distant_point(s)
    print(lca.distance(q,v)-1)
    exit()

Solution (Python):
from collections import deque
N, u, v = map(int, input().split())

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


def bfs(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    d = deque([s])
    while len(d) > 0:
        v = d.popleft()
        for w in G[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                d.append(w)
    return dist


tkhs = bfs(u)
aok = bfs(v)
ans = 0
for i in range(1, N + 1):
    if tkhs[i] < aok[i]:
        ans = max(ans, aok[i] - 1)
print(ans)

Solution (Python):
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=0
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if len(e[now])==1:ans=max(d[to],ans)
print(ans)

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

mt=[-1 for i in range(n)]
de=[-1 for i in range(n)]
dpl=[]
s=[v]
t=0
while s:
  dpl.append([])
  ns=[]
  for i in s:
    de[i]=t
    dpl[-1].append(i)
    for j in e[i]:
      if de[j]!=-1:
        continue
      ns.append(j)
      mt[j]=i
  s=ns
  t+=1

maxd=[de[i] for i in range(n)]
for i in dpl[:0:-1]:
  for j in i:
    maxd[mt[j]]=max(maxd[mt[j]],maxd[j])

t=de[u]//2+1
while de[u]!=t:
  u=mt[u]
print(maxd[u]-1)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
N, u, v= map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]

g = [[] for _ in range(N+1)]
for a, b in AB:
    g[a].append(b)
    g[b].append(a)

parent = [-1] * (N + 1)
children = [[] for _ in range(N+1)]
degree = [0] * (N + 1)
q = deque([v])
while len(q) > 0:
    node = q.popleft()
    node_d = degree[node]
    for i in g[node]:
        if i == parent[node]:
            continue
        parent[i] = node
        degree[i] = node_d + 1
        children[node].append(i)
        q.append(i)

ans = 0

tmp = (degree[u] - 1) // 2
for _ in range(tmp):
    u = parent[u]
max_deg = 0
q = deque([u])
while len(q) > 0:
    node = q.popleft()
    max_deg = max(max_deg, degree[node])
    for i in children[node]:
        q.append(i)
print(max_deg-1)

Solution (Python):
import sys
sys.setrecursionlimit(1<<30)
def dfs(x, dis):
    for y in Tree[x]:
        if parent[y] != x:
            parent[x] = y
            dis[y] = dis[x] + 1
            dfs(y, dis)
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)
disT = [-1]*(N+1)
disA= [-1]*(N+1)
disT[u] = 0
disA[v] = 0
parent = [-1]*(N+1)
dfs(u, disT)
parent = [-1]*(N+1)
dfs(v, disA)
Ans = 0
for i in range(len(disA)):
    if disA[i] >= disT[i]:
        Ans = max(Ans, disA[i]-1)
print(Ans)

Solution (Python):
import sys
sys.setrecursionlimit(1<<30)
def dfs(x,dis):
    for y in Tree[x]:
        if parent[x] != y:
            parent[y] = x
            dis[y] = dis[x]+1
            dfs(y,dis)

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)
disT = [-1]*(N+1)
disA = [-1]*(N+1)
disT[u] = 0
disA[v] = 0
parent = [-1]*(N+1)
dfs(u,disT)
parent = [-1]*(N+1)
dfs(v,disA)
ans = 0
for i in range(1,N+1):
    if disT[i] <= disA[i]:
        ans = max(ans,disA[i]-1)
print(ans)

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

from collections import deque
def bfs(s):
  lis = [-1]*N
  d = deque([s])
  lis[s]=0
  while len(d)>0:
    v = d.popleft()
    for w in edge[v]:
      if lis[w]<0:
        lis[w]=lis[v]+1
        d.append(w)
  return lis

lis1 = bfs(target)
lis2 = bfs(v)
ans = 0
for i in range(N):
  if lis1[i]<lis2[i]:
    ans = max(ans, lis2[i]-1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N,T,A = map(int,input().split()); INF = float("inf")
T-=1;A-=1 
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 
  G[a].append(b);G[b].append(a)

disT = [INF for _ in range(N)]; disT[T] = 0
disA = [INF for _ in range(N)]; disA[A] = 0

def dfs(v, L):
  for u in G[v]:
    if L[u] != INF:
      continue
    L[u] = L[v]+1
    dfs(u,L)
dfs(T,disT)
dfs(A,disA)


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

Solution (Python):
from collections import deque

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

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


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


def bfs(x):
  dist=[-1]*n
  dist[x]=0
  Q=deque()
  Q.append((x))

  while Q:
    q=Q.popleft()
    for i in a[q]:
      if dist[i]==-1:
        dist[i]=dist[q]+1
        Q.append((i))

  return dist

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

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

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

def search(p):
    stack=deque([p])
    check = [-1]*N
    check[p] = 0

    while len(stack)>0:
        v = stack.popleft()
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                stack.append(i)
    return check

taka = search(u-1)
aoki = search(v-1)
ans = 0
for i in range(N):
    if taka[i] < aoki[i]:
        ans = max(ans, aoki[i]-1)
print(ans)

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

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



from collections import deque

q=deque([])
q.append((v-1,0))
done1=[-1]*N

while q:
    now, dist = q.popleft()
    done1[now]=dist
    for i in G[now]:
        if done1[i]!=-1:
            continue
        q.append((i,dist+1))

q=deque([])
q.append((u-1,0))
done2=[-1]*N

while q:
    now, dist = q.popleft()
    done2[now]=dist
    for i in G[now]:
        if done2[i]!=-1:
            continue
        q.append((i,dist+1))

goal=0
for i in range(N):
    if done1[i]>done2[i]:
        goal=max(goal, done1[i])

ans=goal-1


print(ans)

Solution (Python):
nii=lambda:map(int,input().split())
from collections import deque

n,u,v=nii()
u-=1
v-=1

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

def BFS(s):
  dist=[-1 for i in range(n)]
  dist[s]=0

  que=deque()
  que.append(s)

  while que:
    x=que.popleft()
    for i in tree[x]:
      if dist[i]==-1:
        que.append(i)
        dist[i]=dist[x]+1
  return dist

dist_t=BFS(u)
dist_a=BFS(v)

ans=0
for i in range(n):
  if dist_a[i]>dist_t[i]:
    ans=max(ans,dist_a[i]-1)

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n,u,v=nii()
u-=1
v-=1

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

def BFS(s):
  dist=[-1 for i in range(n)]
  dist[s]=0

  que=deque()
  que.append(s)

  while que:
    x=que.popleft()
    for i in tree[x]:
      if dist[i]==-1:
        que.append(i)
        dist[i]=dist[x]+1
  return dist

dist_t=BFS(u)
dist_a=BFS(v)

ans=0
for i in range(n):
  if dist_a[i]>dist_t[i]:
    ans=max(ans,dist_a[i]-1)

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

n,u,v=nii()
u-=1
v-=1

tree=[[] for i in range(n)]
for i in range(n-1):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

dist_a=[-1 for i in range(n)]
dist_a[v]=0

dist_t=[-1 for i in range(n)]
dist_t[u]=0


def BFS(dist,s):
  que=deque()
  que.append(s)

  while que:
    x=que.popleft()
    for i in tree[x]:
      if dist[i]==-1:
        que.append(i)
        dist[i]=dist[x]+1
  return dist

dist_a=BFS(dist_a,v)
dist_t=BFS(dist_t,u)

ans=0
for i in range(n):
  if dist_a[i]>dist_t[i]:
    ans=max(ans,dist_a[i]-1)

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from collections import deque
def dfs(start):
    Q = deque([start])
    dist = [10**18]*N
    dist[start] = 0
    while Q:
        now = Q.pop()
        for nx in query[now]:
            if dist[nx]>=10**18:
                dist[nx] = dist[now] + 1
                Q.append(nx)
    return dist

taka = dfs(u-1)
aoki = dfs(v-1)
ans = 0

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

Solution (Python):

from collections import deque

def main():
    N, u, v = map(int, input().split())
    s = u-1
    t = v-1
    adj = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)
    
    
    queue = deque([t])
    visit = [-1] * N
    visit[t] = 0
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
                

    
    queue = deque([s])
    visit2 = [-1] * N
    
    visit2[s] = 0
    
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit2[u] < 0:
                queue.append(u)
                visit2[u] = visit2[now] + 1

    ans = [-1,-1]
    
    for i in range(N):
        if visit[i] >= visit2[i] and visit[i] > ans[0]:
            ans = [visit[i], i]
    
    print(visit[ans[1]]-1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,u,v = MI()
Graph = [[] for _ in range(N+1)]

for i in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

dist_T = [-1]*(N+1)  
dist_A = [-1]*(N+1)  
dist_T[u] = 0
dist_A[v] = 0

from collections import deque
q1 = deque([u])
q2 = deque([v])
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if dist_T[d] == -1:
            dist_T[d] = dist_T[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if dist_A[d] == -1:
            dist_A[d] = dist_A[n] + 1
            q2.appendleft(d)

ans = 0
for i in range(1,N+1):
    if dist_T[i] < dist_A[i]:
        ans = max(ans,dist_A[i]-1)

print(ans)

Solution (Python):
n,u,v=map(int,input().split())
u-=1;v-=1
edge=[[]*n 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)
  
  




dist=[-1]*n

from collections import deque
q=deque()
q.append(v)
dist[v]=0
while q:
  p=q.popleft()
  d=dist[p]
  for i in edge[p]:
    if dist[i]==-1:
      dist[i]=d+1
      q.append(i)



far=[-1]*n
q=deque()
q.append(u)
far[u]=0
while q:
  p=q.popleft()
  d=far[p]
  for i in edge[p]:
    if far[i]==-1:
      if dist[i]>d+1:
        far[i]=d+1
        q.append(i)


  

far_mx=max(far)
if far_mx==-1:
  print(0)
  exit()
  
ind=[i for i,v in enumerate(far) if v!=-1]

to=max(dist[i] for i in ind)
ans=(to-1)
print(ans)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)

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

graph = defaultdict(list)

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


def dfs(u):
    dist = [-1] * (n + 1)
    stack = [u]
    dist[u] = 0
    while stack:
        u = stack.pop()
        nxt = dist[u] + 1
        for v in graph[u]:
            if dist[v] >= 0:
                continue
            dist[v] = nxt
            stack.append(v)
    return dist


dist_u = dfs(u)
dist_v = dfs(v)


ans = 0
for x, y in zip(dist_u, dist_v):
    if x < y:
        ans = max(ans, y - 1)

print(ans)

Solution (Python):
from collections import deque
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
distT = [0 for _ in range(N+1)]
heap = deque([(u,0)])
distT[u] = 0
hist = [0 for _ in range(N+1)]
hist[u] = 1
while heap:
    x,d = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            distT[y] = d+1
            heap.append((y,d+1))
            hist[y]=1
heap = deque([(v,0)])
distA = [0 for _ in range(N+1)]
heap = deque([(v,0)])
distA[v] = 0
hist = [0 for _ in range(N+1)]
hist[v] = 1
while heap:
    x,d = heap.popleft()
    for y in G[x]:
        if hist[y]==0:
            distA[y]=d+1
            heap.append((y,d+1))
            hist[y] = 1
cmax = 0
for i in range(1,N+1):
    if distT[i]<=distA[i] and distA[i]>cmax:
        cmax = distA[i]
print(cmax-1)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

N,u,v = MI()
Graph = [[] for _ in range(N+1)]

for i in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)

dist_T = [-1]*(N+1)
dist_A = [-1]*(N+1)
dist_T[u] = 0
dist_A[v] = 0

from collections import deque
q1 = deque([u])
q2 = deque([v])
while q1:
    n = q1.pop()
    for d in Graph[n]:
        if dist_T[d] == -1:
            dist_T[d] = dist_T[n] + 1
            q1.appendleft(d)
while q2:
    n = q2.pop()
    for d in Graph[n]:
        if dist_A[d] == -1:
            dist_A[d] = dist_A[n] + 1
            q2.appendleft(d)

ans = 0
for i in range(1,N+1):
    if dist_T[i] < dist_A[i]:
        ans = max(ans,dist_A[i]-1)

print(ans)

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

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

u -= 1
v -= 1

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

INF = 1 << 30
t = [INF] * n
a = [INF] * n

t[u] = 0
a[v] = 0


def dfs(v, p, d):
    for nv in g[v]:
        if nv == p:
            continue
        if d[nv] == INF:
            d[nv] = d[v] + 1
            dfs(nv, v, d)


dfs(u, -1, t)
dfs(v, -1, a)

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

Solution (Python):
from collections import deque
def bfs(start, g, visited):
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        for next_node in g[curr_node]:
            if visited[next_node] >= 0: continue
            visited[next_node] = visited[curr_node] + 1
            q.append(next_node)
    

def main():
    n,u,v = map(int, input().split())
    gl = [ [] for _ in range(n+1)]
    visited_u = [-1] * (n+1)
    visited_v = [-1] * (n+1)
    for i in range(n-1):
        a, b = map(int, input().split()) 
        gl[a].append(b)
        gl[b].append(a)
    bfs(u, gl, visited_u)
    bfs(v, gl, visited_v)

    
    

    
    
    ans = 0
    for i in range(1,n+1):
        if visited_u[i] < visited_v[i] and visited_v[i]:
            
            val = visited_v[i]-1
            ans = max(ans,val)
            
                
                
    print(ans)



if __name__ == "__main__":
    main()

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

dist1 = [N] * N
dist1[V] = 0
def dfs1(v,p=-1):
    for to in es[v]:
        if to==p: continue
        dist1[to] = dist1[v] + 1
        dfs1(to,v)
dfs1(V)

D = dist1[U]

dist2 = [N] * N
dist2[U] = 0
def dfs2(v,p=-1):
    for to in es[v]:
        if to==p: continue
        if (D+1)//2 > dist1[to]: continue
        dist2[to] = dist2[v] + 1
        dfs2(to,v)
dfs2(U)

ans = 0
for a,b in zip(dist1,dist2):
    if b==N: continue
    ans = max(ans, a-1)
print(ans)

Solution (Python):
from collections import deque

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

q = deque()
q.append((u, 0))
depth = [0] * n

visited = set()
while q:
    p, d = q.popleft()
    depth[p] = d
    visited.add(p)
    for x in tree[p]:
        if not x in visited:
            q.append((x, d+1))


q.append((v, 0))
visited.clear()
max_case = max(depth[v] - 1, 0)
while q:
    p, d = q.popleft()
    visited.add(p)
    is_leaf = True
    for x in tree[p]:
        if not x in visited:
            q.append((x, d+1))
            is_leaf = False
    if is_leaf and depth[p] < d:
        max_case = max(max_case, d - 1)
print(max_case)

Solution (Python):
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

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

t = Tree(N, E)
t.setroot(u); dist1 = t.depth
t.setroot(v); dist2 = t.depth

tmp = 0
for i in range(N):
    if dist1[i] < dist2[i]:
        tmp = max(tmp, dist2[i])

print(tmp - 1)

Solution (Python):
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

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

t = Tree(N, E)
t.setroot(v)
t.heavylight_decomposition()

d = t.depth[u]
k = (d + 1) // 2 - 1

for _ in range(k):
    u = t.parent[u]

arr = [None for _ in range(N)]
for i in range(N):
    arr[t.order[i]] = t.depth[i]

st = SegmentTree(arr, max, -1)
lt, rt = t.subtree_hld(u)
maxdep = st.query(lt, rt)

print(maxdep - 1)