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

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)

    ans = vdist[u-1] - 1
    for ud, vd in zip(udist, vdist):
        if ud < vd:
            ans = max(ans, vd - 1)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g
def tree_utils(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def graph_distance(start, g):
    dist, q = [-1] * len(g), deque([start]); dist[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if dist[j] == -1: dist[j] = dist[i] + 1; q.append(j)
    return dist

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    udist = graph_distance(u-1, g)
    vdist = graph_distance(v-1, g)

    visit = [False] * N
    ans = vdist[u-1] - 1
    q = deque([u-1])
    while q:
        i = q.popleft()
        visit[i] = True
        if udist[i] < vdist[i]:
            ans = max(ans, vdist[i]-1)
            for j in g[i]:
                if not visit[j]:
                    q.append(j)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
def parent_children(start, g):
    parent, children, depth, q = [-1]*len(g), make_list(len(g), 0), [-1]*len(g), deque([start]); depth[start] = 0
    while q:
        i = q.popleft()
        for j in g[i]:
            if depth[j] != -1: parent[i] = j
            else: depth[j] = depth[i] + 1; children[i].append(j), q.append(j)
    return parent, children, depth
def adjacency_list(N, edges):
    g = make_list(N, 0)
    for a, b in edges: g[a].append(b), g[b].append(a)
    return g

sys.setrecursionlimit(1000000)
dire, dire8 = [[1, 0], [0, 1], [-1, 0], [0, -1]], [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets, ALPHABETS = "abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD, INF = 1000000007, float("inf")

def main():
    N, u, v = LI()
    AB = LIR1(N-1)
    max_dist = [None] * N
    g = adjacency_list(N, AB)
    parent, children, depth = parent_children(v-1, g)

    def dfs(i):
        dist = max([0] + [dfs(j) for j in children[i]])
        max_dist[i] = dist
        return dist + 1
    mid = u-1
    for _ in range((depth[u-1] - 1)//2):
        mid = parent[mid]
    dfs(mid)
    print(depth[mid] + max_dist[mid] - 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, u, v = map(int, readline().split())
    edge = defaultdict(list)

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

    dist_first = defaultdict(lambda: float("INF"))
    dist_second = defaultdict(lambda: float("INF"))
    dist_first[u] = 0
    dist_second[v] = 0
    leaf = set()

    que = deque()
    que.append((v, 0))
    while que:
        cur, cost = que.popleft()
        new_cost = cost + 1
        is_leaf = True
        for nx in edge[cur]:
            if dist_second[nx] == INF:
                que.append((nx, new_cost))
                dist_second[nx] = new_cost
        if len(edge[cur]) == 1:
            leaf.add(cur)

    que.append((u, 0))
    while que:
        cur, cost = que.popleft()
        if cost < dist_second[cur]:
            new_cost = cost + 1
            for nx in edge[cur]:
                if dist_first[nx] == INF:
                    que.append((nx, new_cost))
                    dist_first[nx] = new_cost

    ans = 0
    for i in range(1, n + 1):
        if i in leaf:
            first = dist_first[i]
            second = dist_second[i]
            if first == INF:
                continue
            ans = max(ans, second - 1)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



from heapq import heappop, heappush

INF = float("inf")

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)]
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child, child_d in G[v]:
            if dist[child] > dist[v] + child_d:
                dist[child] = dist[v] + child_d
                heappush(hq, (dist[child], child))
    return dist

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

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

for a, b in edge:
    graph[a - 1].append((b - 1, 1))
    graph[b - 1].append((a - 1, 1))

from_u = dijkstra(n, graph, u - 1)
from_v = dijkstra(n, graph, v - 1)




fil = filter(lambda x : x[0] < x[1], [[fu, fv] for fu, fv in zip(from_u, from_v)])
sfil = sorted(list(fil), key=lambda x: [-x[1], -x[0]])  



print(sfil[0][1] - 1)

Solution (Python):

def resolve():
    def dfs(v):
        dist = [-1] * N
        stack = [v]
        dist[v] = 0
        while stack:
            v = stack.pop()
            for to in G[v]:
                if dist[to] != -1:
                    continue
                dist[to] = dist[v] + 1
                stack.append(to)
        return dist

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

    dist_Tk = dfs(taka)
    dist_Ao = dfs(aoki)

    ans = 0
    for i in range(N):
        if dist_Tk[i] < dist_Ao[i]:
            ans = max(ans, dist_Ao[i] - 1)

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):

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

from collections import deque
def shortest(tree,start):
    from_start=[None]*N
    q = deque([(-1,start,0)])
    while q:
        parent,x,time = q.popleft()
        if tree[x]==[parent] or (len(tree[x])==1 and parent==-1):
            from_start[x]=time
        for y in tree[x]:
            if y == parent:
                continue
            q.append((x,y,time+1))
    return from_start

from_u = shortest(tree,U)
from_v = shortest(tree,V)

print( max([vv for uu,vv in zip(from_u,from_v) 
            if isinstance(uu, int) and isinstance(vv, int) and uu<vv])-1 )

Solution (Python):
def main():
    from collections import defaultdict,deque
    from math import ceil
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    f = lambda :map(int,input().split())
    n,u,v = f() 
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(node,start):
        targets = deque([node])
        while targets:
            parent = targets.popleft()
            distance_parent = distance[parent][start]
            for child in edge[parent]:
                if distance[child][start] == -1:
                    distance[child][start] = distance_parent + 1
                    targets.append(child)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()

Solution (Python):
import copy
from collections import deque

n, st, sa = map(int,input().split())
st -= 1
sa -= 1

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

visited = [False] * n
visited[st] = True
d = deque()
d.append([st, 0])
tx = {}
if len(e[st]) == 1:
    tx[st] = 0
cnt = 0
while d:
    f, cnt = d.popleft()
    flg = True
    for t in e[f]:
        if not visited[t]:
            flg = False
            d.append([t, cnt+1])
            visited[t] = True
    if flg:
        tx[f] = cnt

visited = [False] * n
visited[sa] = True
d = deque()
d.append([sa, 0])
ax = {}
if len(e[sa]) == 1:
    ax[sa] = 0
cnt = 0
while d:
    f, cnt = d.popleft()
    flg = True
    for t in e[f]:
        if not visited[t]:
            flg = False
            d.append([t, cnt+1])
            visited[t] = True
    if flg:
        ax[f] = cnt

ax = sorted(ax.items(), key=lambda x:x[1], reverse=True)
for i in range(len(ax)):
    x, d = ax[i][0], ax[i][1]
    if d > tx[x]:
        ans = d - 1
        break

print(ans)

Solution (Python):
import os
import sys
import numpy as np

def solve(N, U, V, AB):
    G = [[0]*0 for _ in range(N+1)]
    for idx_ab in range(len(AB)):
        a, b = AB[idx_ab]
        G[a].append(b)
        G[b].append(a)
    P1 = np.zeros(N+1, dtype=np.int64)
    def dfs1(u):
        st = [u]
        while st:
            v = st.pop()
            p = P1[v]
            for u in G[v]:
                if p != u:
                    st.append(u)
                    P1[u] = v
    dfs1(U)
    path_u2v = [U]
    v = V
    while v != U:
        v = P1[v]
        path_u2v.append(v)
    path_u2v.reverse()
    l = len(path_u2v)
    half = (l-2) // 2
    c = path_u2v[half]
    ng = path_u2v[half+1]
    Depth = np.zeros(N+1, dtype=np.int64)
    def dfs2(c):
        st = [c]
        P = np.zeros(N+1, dtype=np.int64)
        while st:
            v = st.pop()
            p = P[v]
            d = Depth[v]
            for u in G[v]:
                if p != u and u != ng:
                    st.append(u)
                    P[u] = v
                    Depth[u] = d + 1
    dfs2(c)
    c_ = path_u2v[l-1-half]
    v = c_
    while v != c:
        Depth[v] = 0
        v = P1[v]
    d = l%2
    ans = max(Depth) + half + d
    return ans



numba_config = [
    [solve, "i8(i8,i8,i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



def main():
    N, u, v = map(int, input().split())
    if N==2:
        print(0)
        return
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2)
    ans = solve(N, u, v, AB)
    print(ans)

main()

Solution (Python):
import os
import sys
import numpy as np

def solve(N, U, V, AB):
    G = [[] for _ in range(N+1)]
    for ab in AB:
        a, b = ab
        G[a].append(b)
        G[b].append(a)
    P1 = np.zeros(N+1, dtype=np.int64)
    def dfs1(u):
        st = [u]
        while st:
            v = st.pop()
            p = P1[v]
            for u in G[v]:
                if p != u:
                    st.append(u)
                    P1[u] = v
    dfs1(U)
    path_u2v = [U]
    v = V
    while v != U:
        v = P1[v]
        path_u2v.append(v)
    path_u2v.reverse()
    l = len(path_u2v)
    half = (l-2) // 2
    c = path_u2v[half]
    ng = path_u2v[half+1]
    Depth = np.zeros(N+1, dtype=np.int64)
    def dfs2(c):
        st = [c]
        P = np.zeros(N+1, dtype=np.int64)
        while st:
            v = st.pop()
            p = P[v]
            d = Depth[v]
            for u in G[v]:
                if p != u and u != ng:
                    st.append(u)
                    P[u] = v
                    Depth[u] = d + 1
    dfs2(c)
    c_ = path_u2v[l-1-half]
    v = c_
    while v != c:
        Depth[v] = 0
        v = P1[v]
    d = l%2
    ans = max(Depth) + half + d
    return ans

def main():
    N, u, v = map(int, input().split())
    if N==2:
        print(0)
        return
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2)
    ans = solve(N, u, v, AB)
    print(ans)

main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    search = [-1] * N
    search[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == -1:
                q.append(nv)
                search[nv] = search[v] + 1

    return search


def bfs2(N, v0, edge, dis):

    q = deque()
    q.append(v0)

    max_dis = dis[v0]
    while q:
        v = q.popleft()
        for nv in edge[v]:
            if dis[v] < dis[nv]:
                q.append(nv)
                max_dis = max(max_dis, dis[nv])

    return max_dis


def main():

    N, taka, aoki = in_nn()
    taka, aoki = taka - 1, aoki - 1

    edge = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = in_nn()
        x, y = x - 1, y - 1
        edge[x].append(y)
        edge[y].append(x)

    dis = bfs(N, aoki, edge)

    if dis[taka] > 2:
        x = (dis[taka] + 1) // 2 - 1
        for _ in range(x):
            for v in edge[taka]:
                if dis[v] < dis[taka]:
                    taka = v
                    break

    ans = bfs2(N, taka, edge, dis) - 1
    print(ans)


if __name__ == '__main__':
    main()

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

takyori = [-1 for i in range(n)]
takyori[u] = 0
d = deque()
d.append(u)
while d:
    now = d.popleft()
    for i in route[now]:
        if takyori[i] == -1:
            takyori[i] = takyori[now] + 1
            d.append(i)

aokyori = [-1 for i in range(n)]
aokyori[v] = 0
d = deque()
d.append(v)
while d:
    now = d.popleft()
    for i in route[now]:
        if aokyori[i] == -1:
            aokyori[i] = aokyori[now] + 1
            d.append(i)
ans = 0
for i in range(n):
    if takyori[i] <= aokyori[i]:
        ans = max(ans,aokyori[i]-1)
print(ans)

Solution (Python):
from collections import deque

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


def bfs(v):
  visited = [False] * N
  q = deque([v])
  span = [-1] * N

  s = 0
  while q:
    l = len(q)
    newq = deque([])

    for _ in range(l):
      node = q.popleft()
      visited[node] = True
      span[node] = s

      for nei in adj[node]:
        if not visited[nei]:
          newq.append(nei)

    q = newq
    s += 1

  return span

t = bfs(u)
a = bfs(v)

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

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

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


def bfs(s):
    INF = 10 ** 9 + 7
    d = [INF] * (N + 1)
    d[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] + 1
                q.append(v)

    return d


to = bfs(u)
ot = bfs(v)

ans = 0
for i, (a, b) in enumerate(zip(to, ot)):
    if a < b:
        ans = max(ans, b)
print(ans - 1)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def bfs(start):
        dist = [f_inf] * n
        dist[start] = 0
        que = deque([start])
        while que:
            v = que.popleft()
            for u in edge[v]:
                if dist[u] == f_inf:
                    dist[u] = dist[v] + 1
                    que.append(u)
        return dist

    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)

    distT = bfs(u - 1)
    distA = bfs(v - 1)

    res = 0
    for i in range(n):
        if distT[i] < distA[i]:
            res = max(res, distA[i])
    print(res - 1)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def bfs(start):
        dist = [f_inf] * n
        dist[start] = 0
        que = deque([start])
        while que:
            v = que.popleft()
            for u in edge[v]:
                if dist[u] == f_inf:
                    dist[u] = dist[v] + 1
                    que.append(u)
        return dist

    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)

    distA = bfs(u - 1)
    distT = bfs(v - 1)

    res = 0
    for i in range(n):
        if distA[i] < distT[i]:
            res = max(res, distT[i])
    print(res - 1)


if __name__ == '__main__':
    resolve()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, U, V = getNM()
U -= 1
V -= 1


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

taka_d = [-1] * N
aoki_d = [-1] * N

taka_d[U] = 0
pos = deque([[U, taka_d[U]]])
while len(pos) > 0:
    u, dis = pos.popleft()
    for i in dist[u]:
        if taka_d[i] == -1:
            taka_d[i] = dis + 1
            pos.append([i, taka_d[i]])

aoki_d[V] = 0
pos = deque([[V, aoki_d[V]]])
while len(pos) > 0:
    u, dis = pos.popleft()
    for i in dist[u]:
        if aoki_d[i] == -1:
            aoki_d[i] = dis + 1
            pos.append([i, aoki_d[i]])

ans = 0
for a, b in zip(taka_d, aoki_d):
    if a < b:
        ans = max(ans, b - 1)
print(ans)

Solution (Python):
def resolve():
    N, u, v = list(map(int, input().split()))
    u, v = u-1, v-1
    adjs = [ [] for _ in range(N)]
    for _ in range(N-1):
        a, b = list(map(lambda x: int(x)-1, input().split()))
        adjs[a].append(b)
        adjs[b].append(a)
    dist_from_u = [float("inf") for _ in range(N)]
    dist_from_u[u] = 0
    import collections
    q = collections.deque([u])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_u[adj] > dist_from_u[node]+1:
                dist_from_u[adj] = dist_from_u[node]+1
                q.appendleft(adj)
    
    dist_from_v = [float("inf") for _ in range(N)]
    dist_from_v[v] = 0
    import collections
    q = collections.deque([v])
    while q:
        node = q.pop()
        for adj in adjs[node]:
            if dist_from_v[adj] > dist_from_v[node]+1:
                dist_from_v[adj] = dist_from_v[node]+1
                q.appendleft(adj)
    
    length = 0
    for i in range(N):
        if dist_from_u[i] < dist_from_v[i] and length < dist_from_v[i]:
            length = dist_from_v[i]
    print(length-1)
    
if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  
    dist = [-1 for _ in range(N)]  
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  
            if i in frag:  
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


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

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max(akdist[i] for i in node)
print(ans - 1)

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S, N):  
    dist = [-1 for _ in range(N)]  
    dist[S] = 0
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  
            if i in frag:  
                continue
            dist[i] = dist[q] + 1
            que.append(i), frag.add(i)
    return dist


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

near = nearlist(n, ab)
tkdist, akdist = bfs(near, u - 1, n), bfs(near, v - 1, n)

node = [i for i in range(n) if tkdist[i] <= akdist[i]]
ans = max((akdist[i], i) for i in node)
print(ans[0] - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, u, v = map(int, input().split())
u -= 1
v -= 1
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
d1 = [None]*n
d2 = [None]*n
def dfs(node, d, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        d[c_node] = d[node] + 1
        dfs(c_node, d, node)
d1[u] = 0
d2[v] = 0
dfs(u, d1)
dfs(v, d2)
ans = 0
for i, j in zip(d1, d2):
    if i<j:
        ans = max(ans, j-1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, u, v = map(int, input().split())
u -= 1
v -= 1
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
pre = [None]*n
def dfs(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        pre[c_node] = node
        dfs(c_node, node)
dfs(u)
path = [v]
now = v
while now!=u:
    now = pre[now]
    path.append(now)
s1 = path[len(path)//2]
p1 = path[len(path)//2-1]
def dfs2(node, depth, p_node):
    mx = depth
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        mx = max(mx, dfs2(c_node, depth+1, node))
    return mx
print(dfs2(s1, 0, p1)+len(path)//2-1)