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 -= 1
v -= 1
ab = [list(map(int, input().split())) for _ in range(n - 1)]

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


def dfs(s):
    d = [-1] * n
    d[s] = 0
    stack = [s]
    while stack:
        frm = stack.pop()
        for to in adj[frm]:
            if d[to] == -1:
                d[to] = d[frm] + 1
                stack.append(to)

    return d


du = dfs(u)
dv = dfs(v)

ans = 0
for eu, ev in zip(du, dv):
    if eu < ev:
        ans = max(ans, ev - 1)

print(ans)

Solution (Python):
from collections import deque


def bfs(s):
    d = [-1] * n
    p = [-1] * n
    dq = deque([s])
    d[s] = 0

    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                dq.append(v)

    return d, p


n, takahashi, aoki = map(int, input().split())
takahashi -= 1
aoki -= 1
ab = [list(map(int, input().split())) for _ in range(n - 1)]

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

depth, par = bfs(takahashi)
aoki_move = depth[aoki] // 2 + 1
root = aoki
for _ in range(aoki_move):
    child = root
    root = par[root]

adj[child].remove(root)
adj[root].remove(child)

depth2, par2 = bfs(root)

aoki_move += max(depth2) - 1
print(aoki_move)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
N,u,v=map(int,input().split())

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dfs(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dfs(v,t+1,i,d)

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

dfs(0,0,u,du)
dfs(0,0,v,dv)

c=0
for i in range(1,-~N):
  if len(T[i])==1 and i!=v:
    if du[i]<dv[i]:
      c=max(c,~-dv[i])

print(c)

Solution (Python):
from collections import deque

def bfs(s):
    que = deque([(s, 0)])
    dist = [None]*n
    while que:
        cur, cst = que.popleft()
        if dist[cur] != None:
            continue
        dist[cur] = cst
        for nxt in es[cur]:
            que.append((nxt, cst+1))
    return dist

n,u,v = map(int,input().split())
es = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
dist_u = bfs(u-1)
dist_v = bfs(v-1)
ans = 0

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

Solution (Python):
import sys
from collections import deque, defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    
    edges = [map(int, input().split()) for _ in range(N-1)]

    to = [[] for _ in range(N)]
    for a, b in edges:
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    dist  = {key:defaultdict(int) for key in [u, v]}

    def bfs(key):
        q = deque()
        q.append(key)
        while(len(q)):
            now = q.popleft()
            for nv in to[now]:
                if nv == key or dist[key][nv]:
                    continue
                else:
                    dist[key][nv] = dist[key][now] + 1
                    q.append(nv)
    
    for key in [u, v]:
        bfs(key)
    
    ans = 0
    for i in range(N):
        diff = dist[v][i] - dist[u][i]
        if diff > 0:
            ans = max(ans, dist[v][i]-1)

    print(ans)    

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque, defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N, u, v = map(int, input().split())
    u -= 1
    v -= 1
    
    edges = [map(int, input().split()) for _ in range(N-1)]

    to = [[] for _ in range(N)]
    for a, b in edges:
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    dist  = {key:defaultdict(int) for key in [u, v]}

    def bfs(key):
        q = deque()
        q.append(key)
        while(len(q)):
            now = q.popleft()
            for nv in to[now]:
                if nv == key or dist[key][nv]:
                    continue
                else:
                    dist[key][nv] = dist[key][now] + 1
                    q.append(nv)
    
    for key in [u, v]:
        bfs(key)
    
    ans = 0
    for i in range(N):
        diff = dist[v][i] - dist[u][i]
        if diff > 0:
            ans = max(ans, dist[v][i]-1)

    print(ans)    

if __name__ == "__main__":
    main()

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


def get_dist(s, d, N):
    dist = [-1]*(N+1)
    dist[s] = 0
    q = [s]
    while q:
        a = q.pop()
        for b in d[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist


def solve():
    N, u, v = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N-1):
        A, B = map(int, input().split())
        d[A].append(B)
        d[B].append(A)
    du, dv = get_dist(u, d, N), get_dist(v, d, N)
    ds = [(i, j) for i, j in zip(du, dv) if i<j]
    ds.sort(key=lambda x:-x[1])
    print(ds[0][1]-1)


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict
N, u, v = map(int, input().split())
d = defaultdict(list)
for _ in range(N-1):
    A, B = map(int, input().split())
    d[A].append(B)
    d[B].append(A)

def get_dist(s):
    dist = [-1]*(N+1)
    dist[s] = 0

    q = [s]
    while q:
        a = q.pop()
        for b in d[a]:
            if dist[b]!=-1:
                continue
            dist[b] = dist[a] + 1
            q.append(b)
    return dist

du, dv = get_dist(u), get_dist(v)
ds = [(i,j[0], j[1]) for i,j in enumerate(zip(du, dv)) if j[0]<j[1]]
ds.sort(key=lambda x:-x[2])
a, b, c = ds[0]
print(c-1)

Solution (Python):
from collections import deque

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

u -= 1; v -= 1

def bfs(s):
    dist = [-1] * N
    prev = [-1] * N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        for w in edge[v]:
            if dist[w] < 0:
                dist[w] = dist[v] + 1
                prev[w] = v
                que.append(w)
    return dist, prev

takahashi, _ = bfs(u)
aoki, prev = bfs(v)

node = 0
dist = -1
for i,(t,a) in enumerate(zip(takahashi, aoki)):
    if t < a and a > dist:
        dist = a
        node = i

print(aoki[prev[node]])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

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


def calc_dist(dlist, n, dist, nnode):
  for c in tree[n]:
    if c == nnode:
      continue
    dlist[c] = dist
    calc_dist(dlist, c, dist+1, n)
    
u_dist_list = [0] * N
calc_dist(u_dist_list, u-1, 1, -1)


v_dist_list = [0] * N
calc_dist(v_dist_list, v-1, 1, -1)


ans = 0
for i in range(N):
  if (v_dist_list[i] - u_dist_list[i]) > 0 and v_dist_list[i] > ans:
    ans = v_dist_list[i] - 1
    
print(ans)

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

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

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

def bfs(graph, root):
    depth = [None] * (n+1)
    depth[0] = (-1,None)

    d = deque()
    d.append((root,0))
    max_dep = 0
    while(d):
        child,parent = d.popleft()
        depth[child] = (depth[parent][0] + 1, parent)
        if( max_dep < depth[child][0] ):
            max_dep = depth[child][0]
        for i in graph[child]:
            if i != parent:
                d.append( (i,child) )

    return depth,max_dep

depth_v,_ = bfs(graph, v)
now = list(depth_v[u])
u_depth = now[0]
limit = (u_depth+2)//2
while(now[0] > limit):
    u = now[1]
    now = depth_v[ u ]

if(len(graph[u]) == 1):
    print( depth_v[u][0]//2 )
    exit()

graph[u].discard( now[1] )
depth_new,max_dep = bfs(graph, u)
ans = limit + max_dep - 1
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,u,v = mi()
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = mi()
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)
inf = -1
oni = [inf]*n
ko = [inf]*n

from collections import deque

def start(hazime,alis):
    d = deque()
    d.append((hazime-1,0))
    alis[hazime-1] = 0
    while d:
        ima,num = d.popleft()
        num += 1
        for i in data[ima]:
            if alis[i] != inf:
                continue
            alis[i] = num 
            d.append((i,num))
start(u,ko)
start(v,oni)

if len(data[u]) == 1 and data[u] == v:
    print(0) 
    exit()
ans = -1
for i in range(n):
    if ko[i] <= oni[i]:
        ans = max(ans,oni[i]-1)
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

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


def dfs(v):
    dist = [-1] * (n + 1)
    stack = deque([v])
    dist[v] = 0
    while stack:
        v = stack.popleft()
        memo = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = memo
            stack.append(w)
    return dist


U, V = dfs(u), dfs(v)
ans = 0
for x, y in zip(U[1:], V[1:]):
    if x < y:
        ans = max(ans, y - 1)
print(ans)

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque

NN = 202020
MOD = 10**9+7
INF = float("inf")

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


def bfs(start, player):
    que = deque([(start, -1, 0)])
    while que:
        node, par, dst = que.popleft()
        
        if len(graph[node]) == 1:
            
            dst_dict[player][node] = dst

        for nxt in graph[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))


dst_dict = [{}, {}]
bfs(u, 0)
bfs(v, 1)


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

print(max_time)

Solution (Python):
from collections import deque

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 dfs(x,n): 
    stack=deque([x])
    dist=[-1]*(n+1)
    dist[x]=0
    
    while len(stack)>0:
        a=stack.pop()
        for k in G[a]:
            if dist[k]<0:
                dist[k]=dist[a]+1
                stack.append(k)
    return dist 

distt=dfs(u,n) 
dista=dfs(v,n) 

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

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def dfs(start): 
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

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

print(answer)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def dfs(start): 
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

dist_U = dfs(U)
dist_V = dfs(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def dfs(start): 
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

dist_U = dfs(U)
dist_V = dfs(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)

Solution (Python):
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist_U = dijkstra(U)
dist_V = dijkstra(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)

Solution (Python):
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

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

dp1 = dijkstra(v - 1)
dp2 = dijkstra(u - 1)
ans = 0
for i in range(n):
    if dp1[i] >= dp2[i]:
        ans = max(ans, dp1[i])

print(ans - 1)

Solution (Python):
from heapq import heappop, heappush
INF = 10 ** 18

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

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

dp1 = dijkstra(v - 1)
dp2 = dijkstra(u - 1)
ans = 0
for i in range(n):
    if dp1[i] >= dp2[i]:
        ans = max(ans, dp1[i])

print(ans - 1)

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

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

def calc(s):
    minDist = [10**18] * N
    st = [(s, 0)]
    while st:
        now, dist = st.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to in edges[now]:
            if minDist[to] > dist + 1:
                st.append((to, dist + 1))
    return minDist

distTaka = calc(u - 1)
distAoki = calc(v - 1)

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

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

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


def dfs(v, d, count):
    count[v] = d
    for v_next in graph[v]:
        if count[v_next] >= 0:
            continue
        dfs(v_next, d + 1, count)


count_tak = [-1] * n
dfs(u, 0, count_tak)
count_aok = [-1] * n
dfs(v, 0, count_aok)

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

print(ans)

Solution (Python):
N,u,v = map(int, input().split())
if u == v:
  print(0)
  exit()
  
ver= [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)
    
    
def bfs(start):
    dist_turn = [float('inf') for i in range(N)]
    dist_turn[start] = 0
    visited = set()
    visited.add(start)
    turn = 0
    prev_dists = [start]
    new_dists = []
    while len(prev_dists) != 0:
        turn += 1
        for prev_dist in prev_dists:
            for new_dist in ver[prev_dist]: 
                if new_dist not  in visited:
                    visited.add(new_dist)
                    new_dists.append(new_dist)
                    dist_turn[new_dist] = turn
        prev_dists = new_dists
        new_dists = []
    return dist_turn

u_shortest = bfs(u-1)
v_shortest = bfs(v-1)

max_dist = -1
for i in range(N):
    if u_shortest[i] < v_shortest[i]:
        max_dist = max(max_dist, v_shortest[i])
print(max_dist - 1)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9 +7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N,u,v = inputIL()
l = inputILL(N-1)

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

dic = dict([(i,[]) for i in range(1,N+1)])
 
for i in l:
  dic[i[0]].append(i[1])
  dic[i[1]].append(i[0])

du = [INF for i in range(N+1)]
du[u] = 0
q = deque([u])

while q:
  x = q.popleft()
  nd = du[x]+1
  for nx in dic[x]:
    if nd < du[nx]:
      du[nx] = nd
      q.append(nx)
      
dv = [INF for i in range(N+1)]
dv[v] = 0
q = deque([v])

while q:
  x = q.popleft()
  nd = dv[x]+1
  for nx in dic[x]:
    if nd < dv[nx]:
      dv[nx] = nd
      q.append(nx)
  
best = 0
pos = None
for i in range(1,N+1):
  if du[i] < dv[i]:
    if best < dv[i]:
      best = dv[i]

print(best-1)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

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

dic=defaultdict(list)
for i in range(n-1):
    a,b=ab[i]
    dic[a].append(b)
    dic[b].append(a)


taka=[-1]*(n+1)
aoki=[-1]*(n+1)

d=deque([[u,0]])
if len(dic[u])==1:
    taka[u]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if taka[dic[now][i]]==-1:
            taka[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        taka[now]=cnt


d=deque([[v,0]])
if len(dic[v])==1:
    aoki[v]=0
while d:
    now,cnt=d.popleft()
    flag=0
    for i in range(len(dic[now])):
        if aoki[dic[now][i]]==-1:
            aoki[dic[now][i]]=-2
            flag=1
            d.append([dic[now][i],cnt+1])
    if flag==0:
        aoki[now]=cnt


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

Solution (Python):
import sys

sys.setrecursionlimit(10**6)


def get_distance(v):              
    distance = [0] * n
    visited = [0] * n
    visited[v] = 1
    dfs(v, 0, distance, visited)
    return distance


def dfs(v, d, distance, visited):
    distance[v] = d
    for u in adj[v]:
        if not visited[u]:
            visited[u] = 1
            dfs(u, d + 1, distance, visited)


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

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

u_distance = get_distance(u - 1)
v_distance = get_distance(v - 1)

ans = 0
for u, v in zip(u_distance, v_distance):
    if u < v and v - 1 > ans:
        ans = v - 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)

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

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

du = [0] * n
dv = [0] * n

def dfs(v, dis, ng, d):
    d[v] = dis
    ng.add(v)
    for w in connect[v]:
        if w not in ng:
            dfs(w, dis+1, ng, d)

dfs(u, 0, set(), du)
dfs(v, 0, set(), dv)

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

Solution (Python):
from collections import deque
n,u,v=map(int,input().split())
G=[[] for i in range(n)]
dist_u=[-1]*n
dist_v=[-1]*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)

u-=1
v-=1

dist_u[u]=0
q=deque([u])

while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_u[nx]==-1:
            q.append(nx)
            dist_u[nx]=dist_u[cur]+1

dist_v[v]=0
q=deque([v])

while q:
    cur=q.popleft()
    for nx in G[cur]:
        if dist_v[nx]==-1:
            q.append(nx)
            dist_v[nx]=dist_v[cur]+1
ans=0
for i in range(n):
    if dist_u[i]<dist_v[i] and dist_v[i]>=ans:
        ans=dist_v[i]
print(ans-1)

Solution (Python):
import queue

N, U, V = map(int, input().rstrip().split())
U -= 1
V -= 1

v2e = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().rstrip().split())
    v2e[a].add(b)
    v2e[b].add(a)
    
q = queue.Queue()
q.put(U)
p = [-1] * N
p[U] = U
while True:
    a = q.get()
    
    if a == V:
        break
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put(b)
            
a = V
min_p = []
while True:
    min_p.append(a)
    if a == U:
        break
    a = p[a]

p = [-1] * N
p[min_p[(len(min_p)-1)//2-len(min_p)%2]] = min_p[(len(min_p)-1)//2-len(min_p)%2]
for a in v2e[min_p[(len(min_p)-1)//2-len(min_p)%2]]:
    p[a] = a
p[min_p[-len(min_p)//2+len(min_p)%2]] = min_p[-len(min_p)//2+len(min_p)%2]

q = queue.Queue()
q.put((min_p[-len(min_p)//2+len(min_p)%2], 0))
while q.qsize() > 0:
    a, d = q.get()
    
    for b in v2e[a]:
        if p[b] == -1:
            p[b] = a
            q.put((b, d + 1))
            
print(d + (len(min_p) - 2) // 2 + len(min_p) % 2)

Solution (Python):
N, U, V = map(int, input().split())
G = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

stack = [V]
path = []
vs = set([V])
G2 = [set() for _ in range(N+1)]
depth = [0] * (N+1)
while stack:
    v = stack.pop()
    if v > 0:
        path.append(v)
        if v == U:
            tmp = len(path)//2

            ss = path[-tmp]
        for u in G[v]:
            if u in vs:
                continue
            depth[u] = depth[v] + 1
            G2[v].add(u)
            vs.add(u)
            stack += [-v, u]
    else:
        path.pop()

stack = [ss]
vs = set([ss])
while stack:
    v = stack.pop()
    for u in G2[v]:
        if u in vs:
            continue
        vs.add(u)
        stack.append(u)

x = 0
for v in vs:
    x = max(depth[v], x)
print(x-1)

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

from collections import deque
q = deque()
q.append(u)
t = [-1]*n
t[u] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if t[new_x] == -1:
            t[new_x] = t[x]+1
            q.append(new_x)

q = deque()
q.append(v)
a = [-1]*n
a[v] = 0
while q:
    x = q.popleft()
    for new_x in g[x]:
        if a[new_x] == -1:
            a[new_x] = a[x]+1
            q.append(new_x)
            
max_ = 0
for i in range(n):
    if t[i] < a[i]:
        max_ = max(max_, a[i])
print(max_-1)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)
n,U,V = map(int,input().split())
U-=1;V-=1
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
Aokidis = [0]*n
Takahashidis = [0]*n
def dfs(node,dis,TorA,pre):
  if TorA == "Takahashi":Takahashidis[node] = dis
  else:Aokidis[node] = dis
  for vi in G[node]:
    if vi == pre:continue
    dfs(vi,dis+1,TorA,node)
dfs(U,0,"Takahashi",-1)
dfs(V,0,"",-1)
for i in range(n):
  if Takahashidis[i] <= Aokidis[i]:
    ans = max(ans,Aokidis[i]-1)
print(ans)

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

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


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


taka = calc_dist(u)
aoki = calc_dist(v)
ans = 0

for x, y in zip(taka, aoki):
    if x <= y:
        ans = max(ans, y - 1)

print(ans)

Solution (Python):
n,u,v=map(int,input().split())
u-=1
v-=1
e=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  e[a].append(b)
  e[b].append(a)
cho=[u]
cho_dis=[10**7]*n
cho_dis[u]=0
cho_visited={u}
countt=1
while cho:
  CHO=[]
  for i in cho:
    for j in e[i]:
      if j in cho_visited:continue
      cho_visited.add(j)
      CHO.append(j)
      cho_dis[j]=countt
  countt+=1
  cho=CHO
aok=[v]
aok_dis=[10**7]*n
aok_dis[v]=0
aok_visited={v}
countt=1
while aok:
  AOK=[]
  for i in aok:
    for j in e[i]:
      if j in aok_visited:continue
      aok_visited.add(j)
      AOK.append(j)
      aok_dis[j]=countt
  countt+=1
  aok=AOK
ans=0
for i in range(n):
  if cho_dis[i]<aok_dis[i]:ans=max(ans,aok_dis[i]-1)
print(ans)

Solution (Python):

import queue
n, u, v = map(int, input().split())
inf = 10 ** 6
ans = 0

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)

def bfs(d,start):
    d[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
            x = que.get()
            for to in edges[x]:
                if d[to] == inf:
                    que.put(to)
                    d[to] = d[x] + 1
                    
du, dv = [inf]*n, [inf]*n
bfs(du,u-1)
bfs(dv,v-1)
for i in range(n):
    if dv[i] > du[i]:
        ans = max(ans, dv[i] - 1)
    
print(ans)