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

Solution (Python):
n,u,v = map(int,input().split())
u,v = u-1,v-1
link = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  link[a].append(b)
  link[b].append(a)
tree = [[] for i in range(n)]
for i in [u,v]:
  stack = [i]
  vi = [0] * n
  tree[i].append(0)
  vi[i] = 1
  while stack:
    cur = stack.pop()
    for j in link[cur]:
      if vi[j] == 0:
        stack.append(j)
        vi[j] = 1
        tree[j].append(tree[cur][-1]+1)
m = 0
c = 0
for i,j in tree:
  if i < j:
    if m < j:
      m = j
      
print(m-1)

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    u -= 1
    v -= 1
    conns = [[] for _ in range(N)]
    for j in range(N - 1):
        conns[A[j] - 1].append(B[j] - 1)
        conns[B[j] - 1].append(A[j] - 1)

    def dfs(idx, cur, dis):
        dis[idx] = cur
        for conn in conns[idx]:
            if dis[conn] < 0:
                dis = dfs(conn, cur + 1, dis)
        return dis

    dis_u = [-1] * N
    dis_u = dfs(u, 0, dis_u)
    dis_v = [-1] * N
    dis_v = dfs(v, 0, dis_v)
    ret = 0
    for i in range(N):
        if dis_u[i] < dis_v[i]:
            ret = max(ret, dis_u[i] + (dis_v[i] - dis_u[i] - 1))
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(N: int, u: int, v: int, A: "List[int]", B: "List[int]"):
    u -= 1
    v -= 1
    conns = [[] for _ in range(N)]
    for j in range(N - 1):
        conns[A[j] - 1].append(B[j] - 1)
        conns[B[j] - 1].append(A[j] - 1)

    can = [True] * N
    def find_v(idx, dis, visited):
        visited[idx] = True
        if idx == v:
            can[idx] = False
            return (dis, -1)
        ret = 0
        target = -1
        for conn in conns[idx]:
            if not visited[conn]:
                ret, target = find_v(conn, dis + 1, visited)
                if ret > 0:
                    if dis >= ret / 2:
                        can[idx] = False
                    if dis < ret / 2 and target == -1:
                        target = idx
                    break
        return ret, target
    visited = [False] * N
    uv, node = find_v(u, 0, visited)
    
    
    
    
    def dfs(idx, dis, visited):
        visited[idx] = True
        ret = dis
        for conn in conns[idx]:
            if not visited[conn] and can[conn]:
                tmp = dfs(conn, dis + 1, visited)
                ret = max(ret, tmp)
        return ret
    visited = [False] * N
    ret = dfs(node, 0, visited)
    
    ret += uv // 2
    print(ret)
    return

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys,heapq
input = sys.stdin.readline
def main():
    n,u,v = map(int,input().split())
    u,v = u-1,v-1

    edge = [[] for _ in range(n)]

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

    
    cost = [0]*n
    new = [v]
    c = 1
    while len(new):
        tank = []
        for e in new:
            for go in edge[e]:
                if go != v and cost[go] == 0:
                    cost[go] = c
                    tank.append(go)
        c += 1
        new = tank

    if cost[u]%2 == 1:
        res = cost[u]//2
        now = u
        for _ in [0]*res:
            for e in edge[now]:
                if cost[now] > cost[e]:
                    now = e
        
        new = [now]
        while len(new):
            tank = []
            for e in new:
                for go in edge[e]:
                    if cost[go] > cost[e]:
                        tank.append(go)
            res += 1
            new = tank
        
        print(res-1)

    else:
        res = cost[u]//2-1
        now = u
        for _ in [0]*res:
            for e in edge[now]:
                if cost[now] > cost[e]:
                    now = e
        
        new = [now]
        while len(new):
            tank = []
            for e in new:
                for go in edge[e]:
                    if cost[go] > cost[e]:
                        tank.append(go)
            res += 1
            new = tank
        
        print(res)



if __name__ == '__main__':
    main()

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

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())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

def bfs(start):
    q = deque()
    q.append([start,0])
    visited = set()
    lis = [0]*N
    while q:
        now,dis = q.popleft()
        if now in visited:
            continue
        lis[now] = dis
        visited.add(now)
        for node in tree[now]:
            q.append([node,dis+1])    
    return lis
ut = bfs(u)
vt = bfs(v)

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

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

import queue

dist_t = [0] * n
dist_a = [0] * n

elb_t = [0] * n
elb_a = [0] * n

ab = [[] for j 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)

u -= 1
v -= 1

q = queue.Queue()

q.put(u)
elb_t[u] = 1
dist_t[u] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_t[idx] != 1:
            if dist_t[idx] != 0:
                dist_t[idx] = min(dist_t[idx], dist_t[tmp] + 1)
            else:
                dist_t[idx] = dist_t[tmp] + 1
            elb_t[idx] = 1
            q.put(idx)

q = queue.Queue()

q.put(v)
elb_a[v] = 1
dist_a[v] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_a[idx] != 1:
            dist_a[idx] = dist_a[tmp] + 1
            elb_a[idx] = 1
            q.put(idx)

ans = 0

for i in range(n):
    if dist_a[i] > dist_t[i]:
        ans = max(ans,dist_a[i]-1)

print(ans)

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

import queue

dist_t = [0] * n
dist_a = [0] * n

elb_t = [0] * n
elb_a = [0] * n

ab = [[] for j 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)

u -= 1
v -= 1

q = queue.Queue()

q.put(u)
elb_t[u] = 1
dist_t[u] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_t[idx] != 1:
            if dist_t[idx] != 0:
                dist_t[idx] = min(dist_t[idx], dist_t[tmp] + 1)
            else:
                dist_t[idx] = dist_t[tmp] + 1
            elb_t[idx] = 1
            q.put(idx)

q = queue.Queue()

q.put(v)
elb_a[v] = 1
dist_a[v] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_a[idx] != 1:
            dist_a[idx] = dist_a[tmp] + 1
            elb_a[idx] = 1
            q.put(idx)

ans = 0

for i in range(n):
    if dist_a[i] > dist_t[i]:
        ans = max(ans,dist_a[i]-1)

print(ans)

Solution (Python):
def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    N, u, v = map(int, f_i.readline().split())
    u -= 1
    v -= 1
    adj = [[] for i in range(N)]
    for i in range(N - 1):
        A, B = map(int, f_i.readline().split())
        A -= 1
        B -= 1
        adj[A].append(B)
        adj[B].append(A)
    
    INF = 10 ** 5
    tak_dist = [INF] * N
    tak_dist[u] = 0
    aoki_dist = [INF] * N
    aoki_dist[v] = 0
    
    
    q = deque([(u, 0)])
    while q:
        pos, dist = q.popleft()
        dist += 1
        for next_pos in adj[pos]:
            if tak_dist[next_pos] > dist:
                tak_dist[next_pos] = dist
                q.append((next_pos, dist))
    
    
    q = deque([(v, 0)])
    while q:
        pos, dist = q.popleft()
        dist += 1
        for next_pos in adj[pos]:
            if aoki_dist[next_pos] > dist:
                aoki_dist[next_pos] = dist
                q.append((next_pos, dist))
    
    d = (d2 for d1, d2 in zip(tak_dist, aoki_dist) if d1 < d2)
    print(max(d) - 1)

solve()

Solution (Python):
n = input()    
m = n.split()
p = [int(i) for i in m]
from collections import deque
list = []
for i in range(p[0]-1): 
    n = input()    
    m = n.split()
    q = [int(i) for i in m] 
    list.append(q)
l = [[] for i in range(p[0]+1)]
for pi in list:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
sousa = deque([[p[2],0,0]]) 
node = [[] for i in range(p[0])] 
while len(sousa) != 0:
    a = sousa.popleft()
    b = l[a[0]]
    if a[1]!=0:
        b.remove(a[1])
    if len(b) == 0:
        pass
    else:
        for i in b:
            sousa.append([i,a[0],a[2]+1])
    node[a[0]-1] = [a[1]] + [a[2]] + b
dis = node[p[1]-1][1]
takahashi = p[1]
max = dis
hate = p[1]
for i in range((dis+1)//2):
    tansaku = deque([[takahashi,dis]])
    if i >= 1:
        kitatoko = takahashi
        takahashi = node[takahashi-1][0]
        a = tansaku.popleft()
        b = node[takahashi-1][2:]
        b.remove(kitatoko)
        if len(b) == 0:
            continue
        else:
            for j in b:
                tansaku.append([j,dis+1-i])

    while len(tansaku) != 0:
        a = tansaku.popleft()
        b = node[a[0]-1][2:]
        print()
        if len(b) == 0:
            pass
        else:
            for j in b:
                tansaku.append([j,a[1]+1])

    if max < a[1]:
        max = a[1]
        hate = a[0]
print(node[hate-1][1]-1)

Solution (Python):
'''input
3 5
1 2 1
2 3 0
'''

from sys import stdin, setrecursionlimit
from bisect import bisect_left
import sys, threading
from collections import defaultdict
sys.setrecursionlimit(10 ** 5 + 1)

def dfs(node, distance, graph, visited, cur):
    visited[node] = True
    distance[node] = cur
    for i in graph[node]:
        if i not in visited:
            dfs(i, distance, graph, visited, cur + 1)



n, T, A = list(map(int, stdin.readline().split()))
graph = defaultdict(list)
for _ in range(n - 1):
    u, v = list(map(int, stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)

T_traverse = [0] * (n + 1)
A_traverse = [0] * (n + 1)
visited = dict()
dfs(T, T_traverse, graph, visited, 0)
visited = dict()
dfs(A, A_traverse, graph, visited, 0)


ans = 0
for i in range(1, n + 1):
    if T_traverse[i] <= A_traverse[i]:
        diff = A_traverse[i] - T_traverse[i]
        if diff % 2 == 0:
            for adj in graph[i]:
                if A_traverse[adj] > A_traverse[i] - 1:
                    ans = max(ans, A_traverse[i])
                    break
            else:
                ans = max(ans, A_traverse[i] - 2)
        else:
            ans = max(ans, A_traverse[i] - 1)
print(ans)

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

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

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)


mx = 0
for du,dv in zip(DU,DV):
  if du < dv:
    mx = max(dv,mx)
print(mx-1)

Solution (Python):
N,U,V=map(int,input().split())
if U==V:
    print(0)
    exit()

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


from collections import deque
def calc(s):
    que=deque()
    que.append(s-1)
    visited=[-1]*N
    visited[s-1]=0
    while que:
        v=que.pop()
        for u in G[v]:
            if visited[u]==-1:
                que.appendleft(u)
                visited[u]=visited[v]+1
    return visited
taka=calc(U)
aoki=calc(V)


ans=0
for i in range(N):
    if taka[i]<=aoki[i]:
        ans=max(ans,aoki[i])

print(ans-1)

Solution (Python):
N,U,V=map(int,input().split())
if U==V:
    print(0)
    exit()

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


from collections import deque
def calc(s):
    que=deque()
    que.append(s-1)
    visited=[-1]*N
    visited[s-1]=0
    while que:
        v=que.pop()
        for u in G[v]:
            if visited[u]==-1:
                que.appendleft(u)
                visited[u]=visited[v]+1
    return visited
taka=calc(U)
aoki=calc(V)


ans=0
for i in range(N):
    if taka[i]<=aoki[i]:
        ans=max(ans,aoki[i])

print(ans-1)

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

def calc(s, tree):
    S = deque([s])
    Dist = [-1]*n
    Dist[s] = 0
    while S:
        u = S.pop()
        for v in tree[u]:
            if Dist[v] < 0:
                Dist[v] = Dist[u] + 1
                S.append(v)
    return Dist

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

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

Solution (Python):
from collections import deque

def read():
    N, u, v = list(map(int, input().strip().split()))
    G = [list() for i in range(N+1)]
    for i in range(N-1):
        a, b = list(map(int, input().strip().split()))
        G[a].append(b)
        G[b].append(a)
    return N, u, v, G

def bfs(N, G, start):
    depth = [-1 for i in range(N+1)]
    depth[start] = 0
    q = deque()
    q.append(start)
    while(len(q) > 0):
        s = q.popleft()
        for t in G[s]:
            if depth[t] == -1:
                depth[t] = depth[s] + 1
                q.append(t)
    return depth

def solve(N, u, v, G):
    depth_u = bfs(N, G, u)
    depth_v = bfs(N, G, v)
    most_deepest_node = u
    for i in range(1, N+1):
        if depth_u[i] < depth_v[i]:
            if depth_v[i] > depth_v[most_deepest_node]:
                most_deepest_node = i
    neighbor_node = G[most_deepest_node][0]
    step_u = depth_u[neighbor_node]
    step_v = depth_v[neighbor_node]
    return step_v

if __name__ == '__main__':
    inputs = read()
    print('%d' % solve(*inputs))

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n, runner, chaser = map(int, input().split())
runner -= 1
chaser -= 1
if runner == chaser:
    print(0)
    exit()

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)

def dfs(dists, start, d=0, p=-1):  
    dists[start] = d
    for neighbor in tree[start]:
        if neighbor == p:
            continue
        dfs(dists, neighbor, d+1, start)

def dist(start):
    dists = [0 for _ in range(n)]
    dfs(dists, start)
    return dists

furthest = 0
run_dist = dist(runner)
chs_dist = dist(chaser)
for i in range(n):
    if run_dist[i] < chs_dist[i]:
        furthest = max(furthest, chs_dist[i])

ans = furthest-1

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, u, v = LI()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


def bfs(root):
    dq = deque([root])
    dist = [-1] * n
    dist[root] = 0
    while dq:
        u = dq.popleft()
        for v in G[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                dq += [v]
    return dist


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


print(ans)

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

dist1 = [100005]*(n+1)

q = []
q.append(v)
dist1[v] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist1[next] == 100005:
            q.append(next)
            dist1[next] = dist1[now] + 1


dist2 = [100005]*(n+1)

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1

for i in range(1, n+1):
    if dist1[i] <= dist2[i]:
        dist2[i] = -1

for i in range(1, n+1):
    if dist2[i] != -1:
        dist2[i] = 100005

q = []
q.append(u)
dist2[u] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if dist2[next] == 100005:
            q.append(next)
            dist2[next] = dist2[now] + 1



ans = 0
for i in range(1, n+1):
    if dist2[i] != -1:
        ans = max(ans, dist1[i])

print(ans-1)

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

G = [[] for a in range(N)]

for ab in AB:
  G[ab[0]-1].append(ab[1]-1)
  G[ab[1]-1].append(ab[0]-1)

qA = deque([v])
qT = deque([u])
costsA = [0 for a in range(N)]
doneA = [0 for a in range(N)]
costsT = [0 for a in range(N)]
doneT = [0 for a in range(N)]

doneA[v] = 1
doneT[u] = 1

def bfs(q, costs, done):
  while q:
    start = q.popleft()
    for i in G[start]:
      if done[i] == 0:
        q.append(i)
        costs[i] = costs[start] + 1
        done[i] = 1

bfs(qA, costsA, doneA)
bfs(qT, costsT, doneT)

distances = [0]
for i in range(N):
  if costsA[i] > costsT[i]:
    distances.append(costsA[i])

print(max(distances)-1)

Solution (Python):
from collections import defaultdict


def dfs(N, tree, v):
    s = []
    done = [False for _ in range(N)]
    dist = [0 for _ in range(N)]

    done[v] = True
    dist[v] = 0
    s.append(v)

    while 0 < len(s):
        v = s.pop()

        
        

        for i in tree[v]:
            if not done[i]:
                done[i] = True
                dist[i] = dist[v] + 1
                s.append(i)

    return dist


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

    tree = defaultdict(list)

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

        tree[A].append(B)
        tree[B].append(A)

    u_dist = dfs(N, tree, u)
    v_dist = dfs(N, tree, v)
    
    

    ans = 0
    for u1, v1 in zip(u_dist, v_dist):
        if u1 < v1:
            ans = max(ans, v1 - 1)

    print(ans)


main()

Solution (Python):
N, u, v = map(int, input().split())
tree = [[] for i in range(N + 1)]
for _ in range(N - 1):
	a, b = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
    
def dfs(v: int, tree: int, N: int) -> int:
    dist = [-1] * (N + 1)
    dist[v] = 0
    stack = [v]
    
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        
        for ne in tree[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
            
    return dist

T = dfs(u, tree, N)
A = dfs(v, tree, N)

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

Solution (Python):

import sys

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

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

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


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


answer = 0
du, dv = dfs(u), dfs(v)
for u, v in zip(du[1:], dv[1:]):
    if v - u > 0:
        x = v - 1
        if answer < x:
            answer = x
print(answer)

Solution (Python):



from collections import defaultdict
import json
from copy import deepcopy
import sys
sys.setrecursionlimit(10**4)

def dfs(graph, s):
  dist = [-1 for _ in range(len(graph))]
  dist[s] = 0
  stack = [s]
  while len(stack) != 0:
    s = stack.pop()
    for t in graph[s]:
      dist[t] = dist[s]+1
      if s in graph[t]:
        graph[t].remove(s)
      stack.append(t)
  return dist

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai-1].append(bi-1)
    graph[bi-1].append(ai-1)
  du = dfs(deepcopy(graph), u-1)
  dv = dfs(deepcopy(graph), v-1)
  costv = [0]
  for duv, dvv in zip(du, dv):
    if duv < dvv:
      costv.append(dvv)
  print(max(costv) - 1)

Solution (Python):
from collections import defaultdict










def find_distances(edge_dict, node, V):
    distances = [-1] * V
    stack = [(0, node)]

    while stack:
        dist, node = stack.pop()
        if distances[node] >= 0:
            continue

        distances[node] = dist
        for end in edge_dict[node]:
            stack.append((dist + 1, end))

    return distances

if __name__ == "__main__":
    V, T, A = map(int, input().split())
    T -= 1
    A -= 1
    edge_dict = defaultdict(list)

    for _ in range(V - 1):
        start, end = map(int, input().split())
        edge_dict[start - 1].append(end - 1)
        edge_dict[end - 1].append(start - 1)
    
    dist_T = [-1] * V
    dist_T[T] = 0
    dist_T = find_distances(edge_dict, T, V)

    dist_A = [-1] * V
    dist_A[A] = 0
    dist_A = find_distances(edge_dict, A, V)

    max_dist = 0
    for i in range(V):
        if dist_T[i] <= dist_A[i]:
            max_dist = max(max_dist, dist_A[i])
    
    print(max_dist - 1)

Solution (Python):


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


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


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


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

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

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

Solution (Python):
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())
tree = [[] for i in range(N + 1)]
for _ in range(N - 1):
	a, b = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)

def dfs(node):
	sta = [node]
	dis = [-1] * (N + 1)
	dis[node] = 0
	while sta:
		no = sta.pop()
		tempD = dis[no] + 1
		for tempN in tree[no]:
			if dis[tempN] < 0:
				dis[tempN] = tempD
				sta.append(tempN)
	else:
		return dis

disU = dfs(u)
disV = dfs(v)
ans = 0

for u_, v_ in zip(disU[1:], disV[1:]):
	if u_ < v_:
			ans = max(ans, v_)
else:
	print(ans - 1)

Solution (Python):

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


graph = [[] for _ in range(n+1)]
for i, j in mapdata:
  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)
ans = 0

for u, v in zip(du[1:], dv[1:]):
  if u < v:
    x = v-1
    if ans < x:
      ans = x

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,x,y=map(int,input().split())
    x-=1; y-=1
    E1=[[] for _ in range(n)]
    E2=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E1[u].append(v)
        E1[v].append(u)
    E2=E1

    
    par=[None]*n 
    par[y]=y
    depth2=[None]*n
    depth2[y]=0
    Q=[y]
    while(Q):
        v=Q.pop()
        for nv in E2[v]:
            if(depth2[nv] is not None): continue
            depth2[nv]=depth2[v]+1
            par[nv]=v
            Q.append(nv)

    
    win=[0]*n
    for v in range(n):
        for nv in E1[v]:
            if(par[v]==nv or par[nv]==v or par[v]==par[nv] or par[par[v]]==nv or par[par[nv]]==v): continue
            win[nv]=win[v]=1

    
    
    
    ans=depth2[x]
    depth1=[None]*n
    depth1[x]=0
    Q=[x]
    while(Q):
        v=Q.pop()
        if(win[v]): 
            print(-1)
            return
        for nv in E1[v]:
            if(depth1[nv] is not None): continue
            depth1[nv]=depth1[v]+1
            ans=max(ans,depth2[nv])
            if(depth1[nv]<depth2[nv]): Q.append(nv)

    print(ans-1)
resolve()

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

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


isLeaf, dU, dV = [len(g) == 1 for g in G], [-1]*N, [-1]*N

for D, P in [(dU, u-1), (dV, v-1)]:
    S = [(P, 0)]
    while len(S) > 0:
        p, d = S.pop()
        D[p] = d 
        
        for g in G[p]:
            if D[g] == -1:
                S.append((g, d+1))

ans = 0


for i in range(N):
    if isLeaf[i] and dU[i] < dV[i]:
        ans = max(ans, dV[i]-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):
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 eto in G[pv]:
            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)