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

import sys
sys.setrecursionlimit(10**8)
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    g = Graph(N)
    for a, b in zip(A, B):
        g.add_edge(a-1, b-1)

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    u = int(next(tokens))  
    v = int(next(tokens))  
    A = [int()] * (N - 1)  
    B = [int()] * (N - 1)  
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, u, v, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque

N, u, v = map(int, input().split())
u -= 1
v -= 1
adj = defaultdict(list)
for i in range(N - 1):
    Ai, Bi = map(lambda x: int(x) - 1, input().split())
    adj[Ai].append(Bi)
    adj[Bi].append(Ai)

A = [0] * N
stack = deque()
stack.append(v)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == v or A[a] != 0:
            continue
        A[a] = A[e] + 1
        stack.append(a)

T = [0] * N
stack = deque()
stack.append(u)
while len(stack) > 0:
    e = stack.popleft()
    for a in adj[e]:
        if a == u or T[a] != 0 or A[a] < T[e] + 1:
            continue
        T[a] = T[e] + 1
        stack.append(a)

print(max([A[i] for i in range(N) if T[i] != 0 or i == u]) - 1)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a] += 1
        f[b] += 1
    l = []
    for i in range(n):
        if f[i] == 1:
            l.append(i)
    depth = [-1]*n
    depth[t] = 0
    q = deque([t])
    while q:
        x = q.popleft()
        for y in v[x]:
            if depth[y] < 0:
                depth[y] = depth[x]+1
                q.append(y)
    d = [-1]*n
    d[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            if d[y] < 0:
                d[y] = d[x]+1
                q.append(y)
    l.sort(key = lambda x:-depth[x])
    for i in l:
        if d[i] < depth[i]:
            break
    print(depth[i]-1)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,u,v = II()
A,B = Line(N-1,2)

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def bfs(pt,v):
    n = len(pt)
    d = [-1]*n
    d[v] = 0
    q = [v]
    c = 1
    while q:
        q1 = []
        for i in q:
            for j in pt[i]:
                if d[j]==-1:
                    d[j] = c
                    q1.append(j)
        q = q1
        c += 1
    return d

pt = edges_to_pt(A,B,N)
du = bfs(pt,u-1)
dv = bfs(pt,v-1)

ans = 0
for i in range(N):
    if du[i]>=dv[i]:
        continue
    elif len(pt[i])>=2:
        continue
    else:
        ans = max(ans,dv[i]-1)

print(ans)

Solution (Python):
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N, u, v ) = list(map(int,input().split()))
A=[]
B=[]
D=[] 
INF = 10 ** 10

for i in range(0,N-1):
    (a, b) =  list(map(int,input().split()))
    A.append(a)
    B.append(b)
    
C=[[] for _ in range(N)]


for i in range(0,N-1):
    
    C[A[i]-1].append(B[i])
    C[B[i]-1].append(A[i])

def initD():
    global D
    D=[INF for _ in range(N)]
    
def dist(n):
    global D
    initD()
    D[n-1] = 0 
    for x in C[n-1]:
        
        if D[x-1] == INF:
            distR(x,1)
    
def distR(n,d):
    global D
    D[n-1] = d
    for x in C[n-1]:
        if D[x-1] == INF:
            
            distR(x,d+1)



dist(u)
U = D 
dist(v)
V = D


max = 0

for i in range(0,N):
    if U[i] < V[i]:
        if (V[i] - U[i]) % 2 ==0:
            x = V[i] - 1
        else:
            x = V[i] - 1
    
        if x > max:
            max = x
 
print(max)

Solution (Python):


import copy
N,u,v=map(int,input().split())
l=[set()for i in range(N)]
info=[[-1,-1,-1,-1]for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    l[a-1].add(b-1)
    l[b-1].add(a-1)
terminal=set()

s={u-1}
info[u-1][0]=0
info[u-1][1]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if info[t2][0]==-1:
                info[t2][0]=t
                info[t2][1]=k
                new_s.add(t2)
    s=new_s
    k+=1

s={v-1}
info[v-1][2]=0
info[v-1][3]=0
k=1
while len(s)>0:
    new_s=set()
    for t in s:
        for t2 in l[t]:
            if  info[t2][2]==-1:
                info[t2][2]=t
                info[t2][3]=k
                new_s.add(t2)
    s=new_s
    k+=1
ans=-1
d=0
for i in range(N):
    if not len(l[i])==1:continue
    if info[i][1]<info[i][3]:
        if d<info[i][3]:
            d=info[i][3]
print(d-1)

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


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

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

    
    def dfs(list, now, prev=-1, depth=0):
        list[now] = depth
        kids = connect[now]
        for kid in kids:
            if kid == prev:
                continue
            dfs(list, kid, now, depth+1)

    list_v, list_u = [None]*n, [None]*n

    dfs(list_v, v)
    dfs(list_u, u)

    tmp_list = [(depth, index) for index, depth in enumerate(list_v)]
    sorted_v = sorted(tmp_list, reverse=True)
    ans = -1

    for depth, index in sorted_v:
        if list_u[index] < depth:
            ans = depth-1
            break

    print(ans)


if __name__ == '__main__':
    main()

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

class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    s.S = {}
    s.P = {}
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i

      s.D += 1
      F = Ft
  def getDeep(s, x):
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n):
    if n == 0:
      return x
    return s.getParent(s.P[x], n - 1)
    

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

T = Tree(N)
for a, b in AB:
  T.setC(a - 1, b - 1)

T.makeRank(v - 1)
t = (T.R[u - 1] // 2) - 1
f = T.R[u - 1] % 2
k = T.getDeep(T.getParent(u - 1, t))
print(t + k + f)

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

N,U,V = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)

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

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

DU,DV = dfs(U),dfs(V)

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

print(answer)

Solution (Python):
from collections import deque

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

du = [0] * N
pu = [-1] * N
q = [(u - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      du[nex] = du[cur] + 1
      pu[nex] = cur
      q.append((nex, cur))

dv = [0] * N
pv = [-1] * N
q = [(v - 1, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex != pre :
      dv[nex] = dv[cur] + 1
      pv[nex] = cur
      q.append((nex, cur))




ret = 0
for i, (u, v) in enumerate(zip(du, dv)) :
  if u < v or (u == v and pu[i] != pv[i]) :
    if u == v :
      ret = max(ret, u)
    else :
      ret = max(ret, v - 1)
print(ret)

Solution (Python):
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n+1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = [v]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_u = dfs(u)
    dist_v = dfs(v)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(200000)

N, ko, oni = map(int, input().split())


class Node:
    def __init__(self):
        self.parent = -1
        self.child = []
        self.depth = -1

    def add_child(self, num):
        self.child.append(num)

    def set_parent(self, num):
        self.parent = num

    def set_depth(self, num):
        self.depth = num

    def children(self):
        for i in self.child:
            if i != self.parent:
                yield i


node_list = [Node() for _ in range(N + 1)]


def get_most_deep(parent_node):
    ret = -1

    if len(node_list[parent_node].child) == 1:
        return node_list[parent_node].depth

    for child_node in node_list[parent_node].children():
        ret = max(ret, get_most_deep(child_node))

    return ret


for _ in range(N - 1):
    A, B = map(int, input().split())
    node_list[A].add_child(B)
    node_list[B].add_child(A)

q = deque()
q.append([oni, 0])

while len(q) > 0:
    val = q.pop()
    parent = val[0]
    gen = val[1]
    node_list[parent].set_depth(gen)
    for child in node_list[parent].children():
        q.append([child, gen + 1])
        node_list[child].set_parent(parent)

ko_gen = node_list[ko].depth
up_count = (ko_gen - 1) // 2

point = ko

for _ in range(up_count):
    point = node_list[point].parent

ans = 0
ans += get_most_deep(point) - ko_gen
ans += ko_gen - 1

print(ans)

Solution (Python):
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [None] * (n + 1)
    dist[v] = 0
    stack = [v]
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist[y] is None:
                dist[y] = dist[x] + 1
                stack.append(y)
    return dist

def main():
    dist_u = dfs(u)
    dist_v = dfs(v)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

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


def dfs4t(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4t[child] = cost4t[a] + 1
            dfs4t(child, a)
    return

def dfs4a(a, par):
    for child in edge[a]:
        if child == par:
            continue
        else:
            cost4a[child] = cost4a[a] + 1
            dfs4a(child, a)
    return


N, u, v = map(int, input().split())
edge = [[] for _ in range(N)]
cost4t = [10**5 for i in range(N)]
cost4a = [10**5 for i in range(N)]

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

u -= 1
v -= 1
cost4t[u] = 0
cost4a[v] = 0
dfs4t(u, 10**5)
dfs4a(v, 10**5)

ans = 0
for t, a, in zip(cost4t, cost4a):
    if a  >= t:
        ans = max(ans, t + a - (t + 1))
print(ans)

Solution (Python):
from collections import deque

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

vds = [-1]*n

qp = deque([])

qp.append(v-1)

vds[v-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if vds[nxt] == -1:
            qp.appendleft(nxt)
            vds[nxt] = vds[now] + 1

uds = [-1]*n
ucost = [-1]*n

qp.append(u-1)

uds[u-1] = 1
ucost[u-1] = 0

while qp:
    now = qp.pop()
    for nxt in neighbors[now]:
        if uds[nxt] == -1 and nxt != v-1:
            qp.appendleft(nxt)
            uds[nxt] = 1
            ucost[nxt] = ucost[now] + 1

ans = 0

for i in range(n):
    if uds[i] != -1 and ucost[i] <= vds[i] and ans < vds[i]:
        ans = vds[i]

            
print(ans-1)

Solution (Python):
import sys
from collections import defaultdict
import heapq

g = defaultdict(list)
input = sys.stdin.buffer.readline
N,u,v= map(int,input().split())
for i in [0]*(N-1):
    A,B = map(int,input().split())
    g[A].append(B)
    g[B].append(A)

def dijkstra(start):
    inf = 10**10
    d = [inf]*(N+1)
    d[start] = 0
    que = []
    heapq.heappush(que,(start,0))
    while que:
        s, dist = heapq.heappop(que)
        if d[s] < dist:
            continue
        for t in g[s]:
            if d[t] > d[s] + 1:
                d[t] = d[s] + 1
                heapq.heappush(que,(t,d[t]))
    return d

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, u, v, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)


    def f(start):
        s = [(start, 0)]
        d = {}
        d[start] = 0
        while s:
            c, l = s.pop()
            for n in g[c]:
                if n not in d:
                    s.append((n, l+1))
                    d[n] = l+1
        return d

    vd = f(v)
    t = u
    a = v
    s = [(t, 0)]
    d = {}
    d[t] = 0
    while s:
        u, l = s.pop()
        for v in g[u]:
            if v not in d and l + 1 < vd[v]:
                s.append((v, l+1))
                tmp = vd[v] - (l+1)
                tmp = (tmp//2) * 2
                d[v] = tmp + (l+1)

    d[t] = (vd[t] // 2) * 2
    dest = (0, -1)
    for k, v in d.items():
        dest = max(dest, (v, k))

    ans = dest[0]
    
    
    
    if vd[dest[1]] == dest[0]:
        ans -= 1
    return ans


def main():
    N, u, v = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, u, v, AB))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy

n,u,v = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
tree = [list() for i in range(n)]
depth = [0] * n
depth2 = [0] * n
already = [1] * n
already[v-1] = 0
q = deque([v-1])
for a,b in ab:
  a,b = a-1,b-1
  tree[a].append(b)
  tree[b].append(a)
d = 0
last = [0] * n
for key,i in enumerate(tree):
  if len(i) == 1:
    last[key] = 1
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    depth[now] = d
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break

q = deque([u-1])
d = 0
ans = 0
already = [1] * n
already[v-1] = 0
while True:
  q2 = deque()
  while q:
    now = q.popleft()
    if depth[now] == d:
      ans = max(ans,d)
      continue
    elif depth[now] < d:
      ans = max(ans,d-1)
      continue
    if last[now]:
      if depth[now] % 2 == d % 2:
        ans = max(ans,depth[now]-1)
      else:
        ans = max(ans,depth[now]-1)
    for i in tree[now]:
      if already[i]:
        q2.append(i)
        already[i] = 0
  if q2:
    q = copy.copy(q2)
    d += 1
  else:
    break
print(ans)

Solution (Python):
import sys

def jisin(gen,mae,huka):
    hukasa[gen]=huka
    for c in tens[gen]:
        if(c!=mae):
            jisin(c,gen,huka+1)
    return

def kyokudai(gen,mae):
    dai=0
    if(len(tens[gen])==1 and mae!=-1):
        dai=hukasa[gen]
        
    else:
        for c in tens[gen]:
            if(c!=mae):
                dai=max(dai,kyokudai(c,gen))
    saisin[gen]=dai
    
    return dai

def oikake(gen):
    miti.append(gen)
    if(hukasa[gen]==0):
        return
    for c in tens[gen]:
        if(hukasa[c]==hukasa[gen]-1):
            oikake(c)

sys.setrecursionlimit(10**6)
n,u,v=map(int,input().split())
u-=1
v-=1
tens=[[]for i in range(n)]
hukasa=[0]*n
saisin=[0]*n

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



jisin(v,-1,0)

kyokudai(v,-1)


miti=[]
oikake(u)
l=len(miti)-1



ans=saisin[miti[l//2]]
print(ans-1)

Solution (Python):
from collections import defaultdict as dd
N, u, v = map(int, input().split())
es = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    es[a-1][b-1] = es[b-1][a-1] = 1

d_ao = [None] * N
q = set([v-1])
dist = 0
dist_taka_ao = None
while q:
    nq = set()
    for node in q:
        d_ao[node] = dist
        if node == v-1:
            dist_taka_ao = dist
        for child in es[node].keys():
            if d_ao[child] is None:
                nq.add(child)
    dist += 1
    q = nq

d_taka = [None] * N
q = set([u-1])
dist = 0
ans = 0
while q:
    nq = set()
    for node in q:
        if d_ao[node] <= dist:
            continue
        d_taka[node] = dist
        ans = ans if ans > d_ao[node] else d_ao[node]
        for child in es[node].keys():
            if d_taka[child] is None:
                nq.add(child)
    dist += 1
    q = nq



print(ans-1)

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

class LCA:
    def __init__(self,v,Edges,root=0):
        self.v=v
        self.Edges=Edges
        self.maxLog=18
        self.Parent=[[-1]*v for _ in range(self.maxLog+1)]
        self.Depth=[0]*v
        self.__bfs(root)
        for i in range(self.maxLog):
            for j in range(v):
                if self.Parent[i][j]!=-1:
                    self.Parent[i+1][j]=self.Parent[i][self.Parent[i][j]]
    def __bfs(self,root):
        Visited=[False]*self.v
        Visited[root]=True
        q=deque([root])
        while q:
            fr=q.pop()
            for to in self.Edges[fr]:
                if Visited[to]:
                    continue
                self.Parent[0][to]=fr
                self.Depth[to]=self.Depth[fr]+1
                Visited[to]=True
                q.append(to)
    def lca(self,a,b):
        if self.Depth[a]>self.Depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.Depth[b]-self.Depth[a])&(1<<i):
                b=self.Parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.Parent[i][a]!=self.Parent[i][b]:
                a=self.Parent[i][a]
                b=self.Parent[i][b]
        return self.Parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.Depth[a]+self.Depth[b]-2*self.Depth[lca]

def main():
    n,u,v=map(int,input().split())
    u-=1; v-=1
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(lambda i: int(i)-1,input().split())
        Edges[x].append(y)
        Edges[y].append(x)
    L=[]
    for i in range(n):
        if len(Edges[i])==1:
            L.append(i)
    lca=LCA(n,Edges,v)
    ans=0
    for l in L:
        if lca.dist(u,l)>=lca.dist(v,l):
            continue
        ans=max(ans,lca.dist(v,l)-1)
    print(ans)
    
if __name__=='__main__':
    main()

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

from collections import deque

class LCA1():
    def __init__(self, l, start):
        self.n = len(l)
        self.dep=[0]*self.n
        self.par=[[-1]*self.n for i in range(18)]

        def bfs(start):
            is_leaf = [0]*n
            que = deque()
            que.append((start, -1, 0))
            while que:
                c,p,d = que.pop()
                self.dep[c]=d
                self.par[0][c]=p
                cnt = 0
                for to in G[c]:
                    if to != p:
                        que.append((to,c,d+1))
                        cnt += 1
                if not cnt:
                    is_leaf[c] = 1
            return is_leaf

        self.is_leaf = bfs(start)

        for i in range(17):
            for j in range(self.n):
                self.par[i+1][j]=self.par[i][self.par[i][j]]

    def lca(self,a,b):
        if self.dep[a]>self.dep[b]:
            a,b=b,a
        for i in range(18):
            if (self.dep[b]-self.dep[a]) & 1<<i:
                b=self.par[i][b]
        if a==b:
            return a
        for i in range(18)[::-1]:
            if self.par[i][a]!=self.par[i][b]:
                a=self.par[i][a]
                b=self.par[i][b]
        return self.par[0][a]

    def dist(self, a,b):
        return abs(self.dep[a]-self.dep[b])

n, u, v = map(int, input().split())
u, v = u-1, v-1
G = [[] for i 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)

LCA = LCA1(G, v)
ans = 0
for i in range(n):
    if not LCA.is_leaf[i]:
        continue
    lca = LCA.lca(u, i)
    if lca == v:
        continue
    if LCA.dist(lca, u) >= LCA.dist(lca, v):
        continue
    turn = 0
    tmp = 0
    d = LCA.dist(u, lca) + LCA.dist(lca, i)
    if d != 0:
        tmp = 2*d
        aoki = d
    else:
        aoki = 0
    tak = LCA.dep[i]
    m = tak-aoki
    if m%2==1:
        tmp += 2*m -1
    else:
        tmp += 2*(m-1)
    ans = max(ans, tmp)
print(ans//2)

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

graph = [[] for _ in range(N)]
for Ai, Bi in AB:
    graph[Ai - 1].append(Bi - 1)
    graph[Bi - 1].append(Ai - 1)

import heapq


d_tak = [10 ** 9 + 7] * N
p_tak = [None] * N
d_tak[u - 1] = 0
q = [(u - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_tak[dst] > pen + 1:
            d_tak[dst] = pen + 1
            p_tak[dst] = src
            heapq.heappush(q, (dst, pen + 1))


d_aok = [10 ** 9 + 7] * N
p_aok = [None] * N
d_aok[v - 1] = 0
q = [(v - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_aok[dst] > pen + 1:
            d_aok[dst] = pen + 1
            p_aok[dst] = src
            heapq.heappush(q, (dst, pen + 1))


i_ans = None
ans_tmp = 0
for i in range(N):
    if d_tak[i] < d_aok[i] and ans_tmp < d_aok[i]:
        ans_tmp = d_aok[i]
        i_ans = i


pos_aok = i_ans
for j in range(d_aok[i_ans] - d_tak[i_ans]):
    pos_aok = p_aok[pos_aok]


d_aok2 = [10 ** 9 + 7] * N
p_aok2 = [None] * N
d_aok2[v - 1] = 0
q = [(v - 1, 0)]
while len(q) > 0:
    src, pen = heapq.heappop(q)
    for dst in graph[src]:
        if d_aok2[dst] > pen + 1:
            d_aok2[dst] = pen + 1
            p_aok2[dst] = src
            heapq.heappush(q, (dst, pen + 1))

print(max(0, d_aok2[i_ans] - 1))

Solution (Python):
def main():
    n, u, v = map(int, raw_input().split())
    u -= 1
    v -= 1
    tree = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    dist = [None] * n
    dist[v] = 0
    stack = [[v, 0]]
    while stack:
        node, d = stack.pop()
        d += 1
        for nex in tree[node]:
            if dist[nex] is None:
                dist[nex] = d
                stack.append([nex, d])
    
    stack = [[u, 0]]
    visited = [False] * n
    visited[u] = True
    best = 0
    while stack:
        node, d = stack.pop()
        d += 1
        for nex in tree[node]:
            if dist[nex] >= d and not visited[nex]:
                if dist[nex] > d:
                    stack.append([nex, d])
                visited[nex] = True
                if dist[nex] < dist[node]:
                    best = max(best, dist[node] - 1)
                else:
                    best = max(best, dist[node])
    print best


main()

Solution (Python):
import sys

n, u, v, *ab = map(int, sys.stdin.read().split())
ab = list(zip(*[iter(ab)] * 2))
graph = [[] for _ in range(n+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)


def main():
    dist_u = [None] * (n + 1)
    dist_u[u] = 0
    stack = [u]

    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_u[y] is None:
                dist_u[y] = dist_u[x] + 1
                stack.append(y)

    dist_v = [None] * (n + 1)
    dist_v[v] = 0
    stack = [v]
    contain_v = [False] * (n + 1)
    contain_v[v] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if dist_v[y] is None:
                dist_v[y] = dist_v[x] + 1
                stack.append(y)

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
def main():
    n, u, v = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    u -= 1
    v -= 1
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    da = [-1]*n
    dt = [-1]*n
    dt[u] = 0
    da[v] = 0
    q = [u]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if dt[j] == -1:
                    dt[j] = cnt
                    qq.append(j)
        q = qq
    q = [v]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        for i in q:
            for j in g[i]:
                if da[j] == -1:
                    da[j] = cnt
                    qq.append(j)
        q = qq
    
    priority = sorted([[i, j] for i, j in enumerate(da)], key=lambda x: -x[1])
    
    
    
    
    
    
    
    
    
    for i, j in priority:
        if da[i] > dt[i]:
            
            print(da[i]-1)
            return 0


main()