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 = map(int,input().split())
u -= 1
v -= 1

du = [float('inf')]*N
dv = [float('inf')]*N
G = [[]]*N

def calcDist(s, dist):
    q = []
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Solution (Python):
import heapq

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



du = [float('inf')]*N
dv = [float('inf')]*N


q = []

G = [[]]*N

'''
def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != []:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)
'''
def calcDist(s, dist):
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Solution (Python):

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


graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)


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):
def p_f():
    from sys import stdin
    input = stdin.readline
    N, u, v = map(int, input().split())
    edges = [list(map(int, input().split())) for i in range(N - 1)]
    if u == v:
        print(0)
        exit()

    def BFS(K, edges, N):
        roots = [[] for i in range(N)]
        for a, b in edges:
            roots[a - 1] += [(b - 1, 1)]
            roots[b - 1] += [(a - 1, 1)]
        dist = [-1] * N
        stack = []
        stack.append(K)
        dist[K] = 0
        while stack:
            label = stack.pop(-1)
            for i, c in roots[label]:
                if dist[i] == -1:
                    dist[i] = dist[label] + c
                    stack += [i]
        return dist

    dist_v = BFS(v - 1, edges, N)
    dist_u = BFS(u - 1, edges, N)
    ans = 0
    for du, dv in zip(dist_u, dist_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


if __name__ == '__main__':
    p_f()

Solution (Python):
from collections import deque

def BFS(t):
    tree=[[] for i in range(n)]
    for i in list:
      tree[i[0]-1].append(i[1]-1)
      tree[i[1]-1].append(i[0]-1)

    dist=[-1 for i in range(n)]
    dist[t-1]=0

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

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

u_dist=BFS(u)
v_dist=BFS(v)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)

Solution (Python):
from collections import deque

INF = 1000000
N,T,A=map(int,input().split())
T -= 1
A -= 1
G = [ [] for i in range(N) ]
DT = [ INF for _ in range(N) ]
DA = [ INF for _ in range(N) ]
for i in range(N-1):
    h1,h2=map(int,input().split())
    h1 -= 1
    h2 -= 1
    G[h1].append(h2);
    G[h2].append(h1);

DT[T] = 0
DA[A] = 0

q = deque()


q.append(T)
while len(q) > 0:
    v = q.popleft()
    for nv in G[v]:
        if DT[nv] == INF:
            DT[nv] = DT[v] + 1
            q.append(nv)

q.clear()
q.append(A)
while len(q) > 0:
    v = q.popleft()
    for nv in G[v]:
        if DA[nv] == INF:
            DA[nv] = DA[v] + 1
            q.append(nv)

max_da = 0
for i in range(N):
    
    if DA[i] - DT[i] >= 1 :
        max_da = max(DA[i], max_da)
print(max_da-1)

Solution (Python):
import sys, heapq
from collections import defaultdict
from itertools import product, permutations, combinations

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

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



def dijkstra_heap(s,edge):

    d = [10**20] * N
    used = [True] * N 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

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

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))

Solution (Python):

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


graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)


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

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

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

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

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

Leaf = []  
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  
UD[u - 1] = -1  
M = L[u - 1]  
d = 1  
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0




d = -1
index = u-1

for i in range(N):
    if Leaf[i]:
        if UD[i] < VD[i]:
            if d < VD[i]:
                d = VD[i]

print(d-1)

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

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

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

def minDist(start):
    minDist = [10**10] * N
    que = deque([(start, 0, -1)])
    while que:
        now, d, pr = que.popleft()

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

        for to in edges[now]:
            if to == pr:
                continue
            if minDist[to] > d + 1:
                que.append((to, d + 1, now))

    return minDist

minDistU = minDist(u)
minDistV = minDist(v)

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

print(ans)

Solution (Python):
from collections import deque
N,u,v=map(int,input().split())
u-=1;v-=1
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)
if len(G[u])==1 and G[u][0]==v:
    print(0)
    exit()
distu=[-1 for i in range(N)]
q=deque([])
q.append(u)
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if distu[p]!=-1:
            continue
        distu[p]=distu[r]+1
        q.append(p)
distv=[-1 for i in range(N)]
q=deque([])
q.append(v)
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if distv[p]!=-1:
            continue
        distv[p]=distv[r]+1
        q.append(p)
dist=[distv[i] if distu[i]<=distv[i] else 0 for i in range(N)]
print(max(dist))

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 + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)

INF = 10 ** 15
dist_U = [INF] * (N + 1)
dist_V = [INF] * (N + 1)

def dfs(start, dist):
  stack = [start]
  dist[start] = 0
  
  while stack:
    s = stack.pop()
    for g in graph[s]:
      if dist[g] > dist[s] + 1:
        dist[g] = dist[s] + 1
        stack.append(g)

dfs(U, dist_U)
dfs(V, dist_V)



answer = []
for i in range(1, N + 1):
  if dist_U[i] < dist_V[i]:
    answer.append(dist_V[i] - 1)
print(max(answer))

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

sys.setrecursionlimit(10**6)

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

def dfs(G, cr, seen, dist):
  seen[cr] = 1
  for i in G[cr]:
    if seen[i] == 0:
      dist[i] = dist[cr] + 1
      dfs(G, i, seen, dist)
  return dist

seen_u = [0]*n
seen_v = [0]*n
dist_u = [0]*n
dist_v = [0]*n

T1 = dfs(l, u, seen_u, dist_u)
T2 = dfs(l, v, seen_v, dist_v)

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

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


sys.setrecursionlimit(10**6)


def dfs(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: 
		if seen[i] == 0: 
			dist[i] = dist[cr]+1
			dfs(G,i,seen,dist)


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

u,v = u-1,v-1

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

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


dist_u = [0]*n
dist_v = [0]*n

dfs(a,u,[0]*n,dist_u)

dfs(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: 
		dist_v[i] = -1

print(max(dist_v) - 1)

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

Leaf = []  
for i in range(N):
    c = 0
    for j in L[i]:
        c = c + 1
    if c == 1:
        Leaf.append(True)
    else:
        Leaf.append(False)

UD = [0 for i in range(N)]  
UD[u - 1] = -1  
M = L[u - 1]  
d = 1  
while True:
    new_M = []
    for i in M:
        if UD[i] == 0:  
            UD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
UD[u-1] = 0

VD = [0 for i in range(N)]
VD[v-1] = -1
M = L[v-1]
d = 1

while True:
    new_M = []
    for i in M:
        if VD[i] == 0:  
            VD[i] = d
            for j in L[i]:
                new_M.append(j)
        else:
            pass
    M = new_M
    if len(M) == 0:
        break
    d = d + 1
VD[v-1] = 0




d = -1
index = u-1

for i in range(N):
    if Leaf[i]:
        if UD[i] < VD[i]:
            if d < VD[i]:
                d = VD[i]

print(d-1)

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

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

def DFS(s, dist, to, d = 0, p = -1):
    dist[s] = d
    for v in to[s]:
        if v == p:
            continue
        DFS(v, dist, to, d + 1, s)
    
def calcDist(s, dist, to):
    DFS(s, dist, to)
    
distU = [0] * (n + 1)
distV = [0] * (n + 1)

calcDist(u, distU, to)
calcDist(v, distV, to)
ans = 0
for i in range(n + 1):
    if distU[i] < distV[i]:
        ans = max(ans, distV[i])
print(ans - 1)

Solution (Python):


from collections import deque


test = ""

"""
9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9
ans 5
"""

"""
5 4 1
1 2
2 3
3 4
3 5
ans 2
"""

"""
5 4 5
1 2
1 3
1 4
1 5
ans 1
"""

test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()

        
n, taka, aoki = map(int, input2().split())

edges = [0] * (n-1)
for i in range(n-1):
    edges[i] = tuple(map(int, input2().split()))

adjacencyL = [[] for i in range(n+1)]
for edge in edges:
    adjacencyL[edge[0]].append(edge[1])
    adjacencyL[edge[1]].append(edge[0])    











takaL = [None] * (n+1)
aokiL = [None] * (n+1)
takaL[taka] = 0
aokiL[aoki] = 0
takaQ = deque([taka])
aokiQ = deque([aoki])

for L, Q in ((takaL, takaQ), (aokiL, aokiQ)):
    while Q:
        popN = Q.popleft()
        for a in adjacencyL[popN]:
            if L[a] == None:
                Q.append(a)
                L[a] = L[popN] + 1
                
    
    
print(max(aokiL[i] for i in range(1, n+1) if takaL[i] < aokiL[i]) - 1)

Solution (Python):

import copy
import sys


sys.setrecursionlimit(10**6)

def dfs(graph, v, d):
    seen[v] = True 
    dist[v] = d 

    
    for i in graph[v]:
        if seen[i]:
            continue
        dfs(graph, i, d+1)


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

u -= 1
v -= 1


graph = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    graph[A].append(B)
    graph[B].append(A)


seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, v, 0)
aoki_dist = copy.deepcopy(dist)


seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, u, 0)
takahashi_dist = copy.deepcopy(dist)

ans = 0
for i in range(N):
    if aoki_dist[i] > takahashi_dist[i]:
        if aoki_dist[i] - 1 > ans:
            ans = aoki_dist[i] - 1      

print(ans)

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
n, u, v = I[:3]
A, B = I[3::2], I[4::2]
S = [set() for _ in range(n+1)]
for a, b in zip(A, B):
    S[a].add(b)
    S[b].add(a)
def cal(x):
  dist=[None]*(n+1)
  dist[x]=0
  st=set([x])
  while st:
    x=st.pop()
    for i in S[x]:
      if dist[i]==None:
        dist[i]=dist[x]+1
        st.add(i)
  return dist

T=cal(u)
A=cal(v)
ans=0
for t,a in zip(T[1:],A[1:]):
  if t<a:
    ans=max(ans,a-1)
print(ans)

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


U_dist = dijkstra(T, u)
V_dist = dijkstra(T, v)

ans_candidates = [dv for du, dv in zip(U_dist, V_dist) if du < dv]
print(max(ans_candidates) - 1)

Solution (Python):
n, u, v = map(int, input().split())
matrix = [[] for _ in range(n)]
import sys
sys.setrecursionlimit(10**8)
for _ in range(n-1):
    a,b = map(int, input().split())
    matrix[a-1].append(b-1)
    matrix[b-1].append(a-1)

C = [0]*n
D = [0]*n

def dfs(x, pre, cnt, c):
    c[x] = cnt
    cnt += 1
    for a in matrix[x]:
        if a == pre:
            continue
        dfs(a, x, cnt, c)

dfs(v-1, -1, 0, C)
dfs(u-1, -1, 0, D)
ans=0

for i in range(n):
    if C[i] > D[i]:
        ans = max(ans, C[i]-1)
print(ans)

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

def dfs(v, dist, d = 0, p = -1):

    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
mx = 0
for i in range(n):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Solution (Python):





from heapq import heappop, heappush
N, u, v = map(int, input().split())
edges = [[] for i in range(N+1)]

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

def dfs(u):
  colors = ["white"] * (N+1)
  d = [9999999999999999] * (N + 1)
  d[u] = 0
  stack = [u]

  while stack:
    u = stack.pop()
    colors[u] = "black"

    for e in edges[u]:
      if colors[e] != "black":
        d[e] = d[u] + 1
        stack.append(e)

  return d

u_dist = dfs(u)
v_dist = dfs(v)

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

print(ans)

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

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)
ans=0
for i in range(N):
    if C[i]>D[i]:
        ans =max(ans, C[i]-1)
print(ans)

Solution (Python):
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
import numpy as np
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)

E = np.array(C) > np.array(D)
C = np.array(C)
ans = max(C[E]) - 1
print(ans)

Solution (Python):
from collections import deque

n, s, t = map(int, input().split(' '))
s -= 1
t -= 1

v = [[] for i in range(n)]
f = [0]*n

for i in range(n-1):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
    f[a] += 1
    f[b] += 1
for i in range(n):
    if f[i] == 0:
        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)
l = depth[:]
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 = sorted(range(n), key=lambda x:-depth[x])
for i in l:
    if d[i] < depth[i]:
        break
print(depth[i] - 1)

Solution (Python):
from collections import deque

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

neighbors = [[] for i in range(N + 1)]

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


def BFS(neighbors, s):
    q = deque([s])
    dist = [-1] * len(neighbors)
    dist[s] = 0
    while q:
        t = q.popleft()
        d = dist[t]
        nodes = neighbors[t]
        for n in nodes:
            if dist[n] < 0:
                dist[n] = d + 1
                q.append(n)
    return dist

u_cost = BFS(neighbors, u)
v_cost = BFS(neighbors, v)

ans = 0
for i in range(1, N + 1):
    if u_cost[i] < v_cost[i]:
        ans = max(ans, v_cost[i])

print(ans - 1)

Solution (Python):

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

from collections import deque

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

queT = deque()
queA = deque()

checkT = [-1] * (N + 1)
checkA = [-1] * (N + 1)

checkT[u] = 0
checkA[v] = 0

queT.append(u)
queA.append(v)
flag = True
while queT or queA: 
    tmp_lst = []
    while queT:
        tmp = queT.popleft()
        d = checkT[tmp]
        for next_ in G[tmp]:
            if checkT[next_] == -1:
                if checkA[next_] != -1:
                    flag = False
                    turn = True 
                    break
                checkT[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queT.append(i)
    
    tmp_lst = []
    while queA:
        tmp = queA.popleft()
        d = checkA[tmp]
        for next_ in G[tmp]:
            if checkA[next_] == -1:
                if checkT[next_] != -1:
                    flag = False
                    turn = False 
                    break
                checkA[next_] = d + 1
                tmp_lst.append(next_)
        if not flag:
            break
    if not flag:
        break
    for i in tmp_lst:
        queA.append(i)








if turn:
    ans = 0
    check = [-1] * (N + 1)
    check[tmp] = 0
    stack = [tmp]
    while stack:
        tmp1 = stack.pop()
        tmp_d = check[tmp1]
        
        for next_ in G[tmp1]:
            if check[next_] == -1 and checkA[next_] == -1:
                check[next_] = tmp_d + 1
                stack.append(next_)
                
        
        ans = max(ans, tmp_d)

else:
    ans = 0
    check = [-1] * (N + 1)
    check[tmp] = 0
    stack = [tmp]

    tmp1 = stack.pop()
    tmp_d = check[tmp1]
    
    for next_ in G[tmp1]:
        if check[next_] == -1 and checkT[next_] != -1:
            check[next_] = tmp_d + 1
            stack.append(next_)
            
    
    ans = max(ans, tmp_d)

    while stack:
        tmp1 = stack.pop()
        tmp_d = check[tmp1]
        
        for next_ in G[tmp1]:
            if check[next_] == -1 and checkA[next_] == -1:
                check[next_] = tmp_d + 1
                stack.append(next_)
                
        
        ans = max(ans, tmp_d)    



if turn:
    print (max(d + ans, 0))
else:
    print (max(d + ans - 1, 0))

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
N, u, v = nm()
u -= 1
v -= 1
G = [[] for i in range(N)]
for i in range(N-1):
    A, B = nm()
    A -= 1
    B -= 1
    G[A].append(B)
    G[B].append(A)

dist_u = [-1]*N
dist_v = [-1]*N
dist_u[u] = 0
dist_v[v] = 0

from collections import deque

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

q = deque()
q.append(v)
while q:
    x = q.popleft()
    for nx in G[x]:
        if dist_v[nx] == -1:
            q.append(nx)
            dist_v[nx] = dist_v[x]+1

ans = 0
for i in range(N):
    if dist_u[i] < dist_v[i] and dist_v[i] >= ans:
        ans = dist_v[i]

print(ans-1)

Solution (Python):






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





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





par = [0] * N


stack = [v]
par[v] = -1

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        par[n2] = n1

        stack.append(n2)
        





par





dis = 0
n = u
while n != v:
    n = par[n]
    dis += 1





n = u
for _ in range((dis - 1) // 2):
    n = par[n]





y = (dis - 1) // 2
x = dis - y






stack = [n]
depth = [0] * N
maxd = 0

while stack:
    n1 = stack.pop()
    for n2 in eda[n1]:
        if n2 == par[n1]:
            continue
        depth[n2] = depth[n1] + 1
        maxd = max(maxd, depth[n2])
        stack.append(n2)
        





z = maxd





if dis % 2 == 0:
    print(y + z + 1)
else:
    print(y + z)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, u, v = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

tkhs = [-1 for _ in range(n)]
aoki = [-1 for _ in range(n)]
tkhs[u-1], aoki[v-1] = 0, 0

def dfs(x, player):
	for y in adj[x]:
		if player[y] < 0:
			player[y] = player[x] + 1
			dfs(y, player)
	return

dfs(u-1, tkhs)
dfs(v-1, aoki)

ans = 0
for i in range(n):
	if tkhs[i] <= aoki[i] and len(adj[i]) > 1:
		ans = max(ans, aoki[i])

print(ans)

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(10**6)
 
N,u,v = map(int, input().split())
 
es = [[] for _ in range(N+1)]
 
for i in range(N-1):
    a,b = map(int, input().split())
    es[a].append(b)
    es[b].append(a)
 
INF = float("inf")
from_u = [INF] * (N+1)
from_u[u] = -1
from_v = [INF] * (N+1)
from_v[v] = -1
 
def solve(prev, curr, distances):
    distances[curr] = distances[prev] + 1
    for next in es[curr]:
        if distances[next] == INF:
            solve(curr, next, distances)
 
solve(u,u,from_u)
solve(v,v,from_v)
 
 
 
ans = 0
for i in range(1,N+1):
    if from_u[i] < from_v[i]:
        
        ans = max(ans, from_v[i]-1)
 
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

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


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

print(ans)

Solution (Python):
from collections import deque

INF = -1

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

def bfs(start):
    dist = [INF] * n
    dist[start] = 0
    q = deque([start])
    while q:
        cur = q.pop()
        for to in g[cur]:
            if dist[to] == INF:
                dist[to] = 1 + dist[cur]
                q.appendleft(to)
    return dist

distT = bfs(t)
distA = bfs(a)
ret = 0
for v in range(n):
    if distT[v] < distA[v]:
        ret = max(ret, distA[v] - 1)
print(ret)

Solution (Python):
from collections import deque
n,u,v = map(int,input().split())
Edge = [[] for i in range(n)]

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

def bfs(s):
    dist = [-1]*n
    que = deque([s-1])
    dist[s-1] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Edge[v]:
            if dist[w] > -1:
                continue

            dist[w] = d+1
            que.append(w)
    return dist

U,V = bfs(u),bfs(v)

ans = 0

for i in range(n):
    if U[i] < V[i]:
        ans = max(ans,V[i]-1)

print(ans)