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 heapq;

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

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[l] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]
aoki_dist[taka] = -1

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c >= aoki_dist[l]:
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        q.append((c, l))
    index += 1

print(max_dist - 1)

Solution (Python):
import heapq;

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

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    print(0)
    exit()

def bfs(begin):
    q = [(0, begin)]
    dist = [-1] * n
    dist[begin] = 0

    index = 0
    while index < len(q):
        c0, i = q[index]
        c = c0 + 1
        for l in vert[i]:
            if dist[l] >= 0:
                continue
            dist[l] = c
            q.append((c, l))
        index += 1
    return dist

aoki_dist = bfs(aoki)
taka_dist = bfs(taka)

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

print(ans)

Solution (Python):
import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

N, U, V = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(N - 1)]

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)

Solution (Python):
from queue import Queue

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

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

inf = 1<<30
du = [inf]*N
dv = [inf]*N
du[u-1] = 0
dv[v-1] = 0

visited = [False]*N
visited[u-1] = True

que = Queue()
que.put(u-1)
while not(que.empty()):
    nxt = que.get()    
    for nv in edge[nxt]:
        if not visited[nv]:
            que.put(nv)
            du[nv] = du[nxt]+1
            visited[nv] = True
visited = [False]*N
visited[v-1] = True
del que
que = Queue()
que.put(v-1)
while not(que.empty()):
    nxt = que.get()    
    for nv in edge[nxt]:
        if not visited[nv]:
            que.put(nv)
            dv[nv] = dv[nxt]+1
            visited[nv] = True

idx=0
maxd = 0
for i in range(N):
    if du[i]<dv[i]:
        if maxd<dv[i]:
            maxd=dv[i]
            idx = i

ans = dv[idx]-1
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

def dfs(x):
    dist  = [INF] * N
    stack = [(x, 0, -1)]
    while stack:
        u, cost, prev = stack.pop()
        if dist[u] != INF:
            continue
        dist[u] = cost
        for v in nodes[u]:
            if v == prev:
                continue
            stack.append((v, cost+1, u))
    return dist

res1 = dfs(x)
res2 = dfs(y)

mx = -INF
for i in range(N):
    if res1[i] <= res2[i]:
        mx = max(mx, res2[i])
print(mx - 1)

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





roots=[ [] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    roots[a-1]+=[b-1]
    roots[b-1]+=[a-1]
dist=[-1]*n
stack=[]
stack.append(u)
dist[u]=0
while stack:
    label=stack.pop(-1)
    for i in roots[label]:
        if dist[i]==-1:
            dist[i]=dist[label]+1
            stack+=[i]
dist1=dist
dist=[-1]*n
stack=[]
stack.append(v)
dist[v]=0
while stack:
    label=stack.pop(-1)
    for i in roots[label]:
        if dist[i]==-1:
            dist[i]=dist[label]+1
            stack+=[i]
dist2=dist
goal = -1
d = 0
for i in range(n):
    if dist1[i]<dist2[i] and d < dist2[i]:
        d = dist2[i]
        goal = i
else:
    print(dist2[goal]-1)

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


def dfs(v):
    dist = [-1 for _ in range(N+1)]
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dist_x = dist[v] + 1
        for child in graph[v]:
            if 0 <= dist[child]:
                continue
            dist[child] = dist_x
            stack.append(child)
    return dist


def solve():
    dist_u, dist_v = dfs(u), dfs(v)
    
    ans = 0
    for a, b in zip(dist_u[1:], dist_v[1:]):
        if a < b:
            ans = max(ans, b-1)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N, V, U = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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



children_depths = [0] * N
parents = [None] * N

stack = [(U, None)]
vs = []
while stack:
    v, parent = stack.pop()
    parents[v] = parent
    vs.append(v)
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
vs.reverse()
for v in vs:
    if parents[v] is not None:
        children_depths[parents[v]] = max(children_depths[parents[v]], children_depths[v] + 1)

v = V
dist = 1
while parents[v] != U:
    v = parents[v]
    dist += 1


p_cnt = 0
v = V
ans = 0
while dist > 0:
    ans = max(ans, dist - 1 + children_depths[v] + p_cnt)
    v = parents[v]
    p_cnt += 1
    dist -= 2
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, x, y = MAP()
x -= 1; y -= 1
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

memo  = [INF] * N
stack = [(y, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo[u] != INF:
        continue
    memo[u] = cost
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))
memo2  = [INF] * N
stack = [(x, 0, -1)]
while stack:
    u, cost, prev = stack.pop()
    if memo2[u] != INF:
        continue
    memo2[u] = cost
    if u == y:
        continue
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, cost+1, u))

mx = -INF
for i in range(N):
    if memo[i] >= memo2[i]:
        mx = max(mx, memo[i])
print(mx - 1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    catch = self_depths[u] // 2
    while self_depths[parents[u]] > catch:
        u = parents[u]
    return self_depths[u] + subtree_depths[u] - 1


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)
print(solve(u))

Solution (Python):
n,x,y=map(int,input().split())
s=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
p=[float("INF")for i in range(n+1)]
q=[float("INF")for i in range(n+1)]
p[x]=0
q[y]=0
c=set([x])
while c:
    d=set()
    for i in c:
        for j in s[i]:
            if p[j]>p[i]+1:
                p[j]=p[i]+1
                d.add(j)
    c=d
c=set([y])
while c:
    d=set()
    for i in c:
        for j in s[i]:
            if q[j]>q[i]+1:
                q[j]=q[i]+1
                d.add(j)
    c=d
a=0
for i in range(1,n+1):
    if p[i]<q[i]:
        a=max(a,q[i]-1)
print(a)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n,u,v=map(int,input().split())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
depth=[-1]*(n+1)
dis=[-1]*(n+1)
def dsf_1(p,d):
    depth[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_1(c,d+1)
dsf_1(v,0)
def dsf_2(p,d):
    dis[p]=d
    for c in E[p]:
        if dis[c]==-1:
            dsf_2(c,d+1)
dsf_2(u,0)
ans=0
for i in range(1,n+1):
    if len(E[i])==1 and i!=v:
        if dis[i]<depth[i]:
           ans=max(ans,depth[i]-1)
print(ans)

Solution (Python):
import sys


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

que = []
seen = {}
dic2 = {}
way = {}
ans_l = []
for i in range(1,n+1):
    seen[i] = 0
    dic2[i] = 0
    way[i] = 0

que.append(v)
seen[v] = 1
while len(que) != 0:
    tem_v = que.pop()
    d = dic2[tem_v]
    if len(dic[tem_v]) == 1 and seen[dic[tem_v][0]] == 1:
        ans_l.append((tem_v, d))
        
    for node in dic[tem_v]:
        if seen[node] == 0:
            que.append(node)
            seen[node] = 1
            dic2[node] = d + 1


ans_l = sorted(ans_l, reverse=True, key=lambda x: x[1])

d_taka = dic2[u]

que.append(u)
way[u] = 1
while len(que) != 0:
    tem_u = que.pop()
    d = dic2[tem_u]
    for node in dic[tem_u]:
        if dic2[node] < d:
            que.append(node)
            way[node] = 1

for i in range(len(ans_l)):
    node, tem_d = ans_l[i]
    que.append(node)
    while len(que) != 0:
        tem_u = que.pop()
        d = dic2[tem_u]
        if way[tem_u] == 1:
            ans = tem_u
        else:
            for node2 in dic[tem_u]:
                if way[node2] == 1:
                    ans = node2
                if dic2[node2] < d and way[node2] == 0:
                    que.append(node2)
    
    if dic2[ans] * 2 > d_taka:
        print(tem_d - 1)
        sys.exit()

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())
data = list(zip(m,m))

graph = [[] for _ in range(n+1)]
for a,b in data:
    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
res = 0
du, dv = dfs(u), dfs(v)
for i in range(1, n+1):
    dvi = dv[i]
    if du[i] <= dvi:
        if dvi > res:
            res = dvi
print(res - 1)

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

u -= 1
v -= 1

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

def calcDepth(root):
  depth = [-1] * N
  stack = [(root, 0)]

  while stack:
    cur, curD = stack.pop()
    depth[cur] = curD
    for c in edge[cur]:
      if depth[c] != -1: continue
      stack.append((c, curD+1))
  
  return depth

Adepth = calcDepth(v)
Ddepth = calcDepth(u)

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

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

n, u, v = map(int, readline().split())
m = map(int,read().split())
data = list(zip(m,m))

graph = [[] for _ in range(n+1)]

for a,b in data:
    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
res = 0
du, dv = dfs(u), dfs(v)
for i in range(1, n+1):
    dvi = dv[i]
    if du[i] <= dvi:
        if dvi > res:
            res = dvi
print(res - 1)

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

input = sys.stdin.readline
sys.setrecursionlimit(20000000)

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

path_u = [0] * n
path_v = [0] * n


checked = [False] * n
checked[u] = True
q = queue.Queue()
q.put((u, 0))
while not q.empty():
    cur, count = q.get()
    path_u[cur] = count
    for i in ab[cur]:
        if not checked[i]:
            q.put((i, count+1))
            checked[i] = True


checked = [False] * n
checked[v] = True
q = queue.Queue()
q.put((v, 0))
while not q.empty():
    cur, count = q.get()
    path_v[cur] = count
    for i in ab[cur]:
        if not checked[i]:
            q.put((i, count+1))
            checked[i] = True

ans = 0
for u_, v_ in zip(path_u, path_v):
    if u_ < v_:
        ans = max(ans, v_ - 1)

print(ans)

Solution (Python):
import sys

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






from collections import deque



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

	q = deque()
	a = [None] * (n + 1)
	b=[None] * (n + 1)
	q=[(u,0)]
	while q:
		now,cnt= q.pop()
		a[now]=cnt
		b[cnt]=now
		if now==v:
			za=b[(cnt-1)//2]
			ccnt=cnt
		for r in A[now]:
			if a[r] == None:
				q.append((r,cnt+1))
			else:
				continue
	
	q = deque()
	c = [None] * (n + 1)
	q=[(za,0)]
	while q:
		now,cnt= q.pop()
		c[now]=cnt
		for r in A[now]:
			if c[r] == None:
				q.append((r,cnt+1))
			else:
				continue
	
	
	zza=za
	q = deque()
	q = [v]
	while q:
		now=q.pop()
		if now==za:
			A[za]=[]
		c[now]=0
		for i in A[now]:
			if c[i]!=0:
				q.append(i)
			else:
				continue
				
	syoki=a[zza]
	
	ans=syoki+max(c[1:])
	if ccnt%2==0:
		ans+=1
	print(ans)
	
	



	
if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
N,U,V = map(int, input().split())
d = [set() for _ in range(N+1)]
dps = [0 for _ in range(N+1)]
dpss = [0 for _ in range(N+1)]
oks = set()

def it(v):
    stack = [v]
    vs = set()
    path = []
    while True:
        if not len(stack):
            break
        v = stack.pop()
        if v > 0:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u in vs:
                    continue
                if u == V:
                    r = path[:]
                    continue
                dps[u] = dps[v] + 1
                oks.add(u)
                stack.append(-v)
                stack.append(u)
        else:
            path.pop()
    return r

def it2(v, path):
    stack = [v]
    vs = set()
    while True:
        if not len(stack):
            break
        v = stack.pop()
        vs.add(v)
        for u in d[v]:
            if u in vs:
                continue
            if u not in oks:
                continue
            if dps[v] >= dpss[v] and u not in path:
                continue
            dpss[u] = dpss[v] + 1
            stack.append(u)

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

oks.add(U)
path = set(it(U))
it2(V, path)
print(max(dpss)-1)

Solution (Python):
class Tree:
    def __init__(self, N):
        self.N = N 
        self.D = (self.N-1).bit_length() 
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def dfs(self, root):
        
        
        
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)

N, u, v = map(int, input().split())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(v-1)
dist_v = tr.dist
tr.dfs(u-1)
dist_u = tr.dist
ans = 0
for du, dv in zip(dist_u, dist_v):
    if du < dv:
        ans = max(ans, dv - 1)
print(ans)

Solution (Python):
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, u, v = list(map(int, readline().split()))
    tmd = collections.defaultdict(list)
    for i in range(n-1):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]
        tmd[tmb-1] += [tma-1]

    qlt = [[0, u-1]]
    qlt = collections.deque(qlt)
    fqt = collections.defaultdict(int)
    fqt[u-1]
    while True:
        if len(qlt) != 0:
            cost, tmp = qlt.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fqt:
                    qlt.append([cost + 1, tmv])
                    fqt[tmv] = cost + 1
        else:
            break

    qla = [[0, v-1]]
    qla = collections.deque(qla)
    fqa = collections.defaultdict(int)
    fqa[v-1]
    while True:
        if len(qla) != 0:
            cost, tmp = qla.popleft()
            for tmv in tmd[tmp]:
                if tmv not in fqa:
                    qla.append([cost + 1, tmv])
                    fqa[tmv] = cost + 1
        else:
            break
    mt = 0
    for kt, vt in sorted(fqt.items(), key=lambda x: x[1], reverse=True):
        if vt < fqa[kt]:
            mt = max(mt, fqa[kt])
    print(mt - 1)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i: [] for i in range(n)}
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j: i for i, j in enumerate(path)}
already = set()
ls = []
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    ls.append(cur_dis - minus)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(ls)

if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)

Solution (Python):
from collections import deque
def main():
    N, u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    graph = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = [int(i) for i in input().split()]
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
    atree, aparents, adistances = maketree(v, graph, N)
    ttree, tparents, tdistances = maketree(u, graph, N)
    res = 0
    
    
    for i in range(N):
        a = adistances[i]
        t = tdistances[i]
        if(a > t):
            res = max(res, a - 1)
    print(res)

def maketree(v, graph, N):
    tree = [[] for _ in range(N)]
    parents = [-1] * N
    distances = [0]*N
    
    stack = deque([(v, -1, 0)])
    while len(stack) > 0:
        current, parent, distance = stack.pop()
        distances[current] = distance
        parents[current] = parent
        for n in graph[current]:
            if parent == n:
                continue
            stack.append((n, current, distance+1))
            tree[current].append(n)
    return tree, parents, distances
    
main()

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

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)

def cur2(p):
    if spar[p]==-1:
        spar[p]=cur2(par[p])
    return spar[p]




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

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

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

cur(u)

spar=[-1 for i in range(n)]
i=v
while i!=u:
    spar[i]=i
    i=par[i]
spar[u]=u


for p in range(n):
    cur2(p)

ans=rank[v]-1
for i in range(n):
    z=rank[v]-rank[spar[i]]*2
    if z>0:
        ans=max(ans,rank[i]+z-1)
print(ans)

Solution (Python):
from collections import deque
INF = 10 ** 9 + 7

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

edges = [[] for _ in range(N)]
for x, y in X:
    edges[x - 1].append(y - 1)
    edges[y - 1].append(x - 1)
    
def bfs(s):
    d = [INF] * N
    d[s] = 0

    visited = [False] * N
    visited[s] = True
    
    q = deque()
    q.append(s)
    
    while q:
        u = q.popleft()
        for v in edges[u]:
            if visited[v]:
                continue
            
            visited[v] = True
            d[v] = d[u] + 1
            q.append(v)
            
    return d

ans = 0
for x, y in zip(bfs(u - 1), bfs(v - 1)):
    if x <= y:
        ans = max(ans, y - 1)
        
print(ans)

Solution (Python):
N,u,v = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
import numpy as np
x = [[] for _ in range(N)]
for ab in AB:
  a = ab[0]
  b = ab[1]
  x[a-1].append(b-1)
  x[b-1].append(a-1)
  
flag1 = [False]*N
flag2 = [False]*N
length1 = [0]*N
length2 = [0]*N
go = [v-1]
while go!=[]:
  a = go.pop()
  if flag1[a]:
    continue
  else:
    flag1[a]=True
    for i in x[a]:
      if flag1[i]:
        continue
      else:
        length1[i]=length1[a]+1
        go.append(i)

go = [u-1]
while go!=[]:
  a = go.pop()
  if flag2[a]:
    continue
  else:
    flag2[a]=True
    for i in x[a]:
      if flag2[i]:
        continue
      else:
        length2[i]=length2[a]+1
        go.append(i)
        
length1 = np.array(length1)
length2 = np.array(length2)
print(max(length1[length1>length2])-1)

Solution (Python):
from collections import deque
import numpy as np


def bfs(N, u, path):
    d = [-1] * N
    d[u-1] = 0
    q = deque([])
    q.append(u-1)

    while(len(q) != 0):
        p = q.popleft()

        rs = path[p]

        for r in rs:
            if d[r] == -1:
                d[r] = d[p] + 1
                q.append(r)

    return d


def bfs2(N, u, path, d):
    e = [-1] * N
    e[u-1] = 0
    q = deque([])
    q.append(u-1)
    far_p = u-1

    while(len(q) != 0):
        p = q.popleft()

        if (d[p] - e[p]) >= 1:
            rs = path[p]

            is_end = len(rs)
            for r in rs:
                if e[r] == -1:
                    e[r] = e[p] + 1
                    q.append(r)
                else:
                    is_end -= 1

            if is_end == 0:
                if d[p] >= d[far_p]:
                    far_p = p

    return e, far_p


N, u, v = map(int, input().split())
path = [[] * N for i in range(N)]

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

d = bfs(N, v, path)
e, far_p = bfs2(N, u, path, d)

print(d[far_p]-1)

Solution (Python):
from collections import deque

di_lst = []
N, U, V = map(int, input().split())
edges = {tuple(map(int, input().split())) for i in range(N - 1)}

stack = deque()


def BFS(X, edges, N):
    roots = [set() for _ in range(N + 1)]
    for a, b in edges:
        roots[a].add(b)
        roots[b].add(a)
    dist = {}
    stack = deque()
    stack.append(X)
    dist[X] = 0
    while stack:
        parent = stack.pop()
        for child in roots[parent]:
            if not child in dist:
                dist[child] = dist[parent] + 1
                stack.append(child)
    return dist


U_dist = BFS(U, edges, N)
V_dist = BFS(V, edges, N)

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

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

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

x=bfs(u-1)
y=bfs(v-1)
ans=[]
for i in range(n):
  if x[i]<y[i]:
    ans.append(y[i]-1)
print(max(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]
N,u,v = map(int,input().split(' '))
l = [None]*N
for i in range(N-1):
    l[i] = list(map(int, input().split()))

MAP = {}
for i in range(N):
    if l[i]==None:
        continue
    a,b = l[i]
    if a in MAP:
        MAP[a].append(b)
    else:
        MAP[a] = [b]
    if b in MAP:
        MAP[b].append(a)
    else:
        MAP[b] = [a]


t_MAP = [0]*(N+1)
cost = 0

def t_dfs(n,c):
    t_MAP[n] = c
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if t_MAP[j]==0 and j!=u:
                t_dfs(j,c)
t_dfs(u,cost)

a_visited = [False]*(N+1)
break_even = False
pre_tcost = 10**5
ANS = [0]
def a_dfs(n,c,pre_c):
    a_visited[n] = True
    t_cost = t_MAP[n]
    if t_cost>c:
        if t_cost>pre_c:
            return
    ANS[0] = max(c,ANS[0])
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if not a_visited[j]:
                a_dfs(j,c,t_cost)
a_visited[v] = True
a_dfs(v,cost,pre_tcost)
print(ANS[0]-1)

Solution (Python):
import sys
from collections import deque

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

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre, p):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo[cur][p] = memo[pre][p] + 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])

dfs(u - 1, - 1, 0)
dfs(v - 1, -1, 1)


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