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

Solution (Python):
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)

    path = [-1] * N

    def find_path_on_tree(to_node, node, parent=None, d=0):
        if node == to_node:
            path[d] = node
            return True
        for child in adj[node]:
            if child == parent:
                continue
            if not find_path_on_tree(to_node, child, node, d + 1):
                continue
            path[d] = node
            return True
        return False

    find_path_on_tree(U, V)  
    path = [node for node in path if node != -1]
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()

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

aolevel = [-1] * n
aolevel[v - 1] = 0
q = [v - 1]
while len(q) > 0:
    i = q.pop(0)
    for j in edges[i]:
        if aolevel[j] < 0:
            aolevel[j] = aolevel[i] + 1
            q.append(j)

ret = 0
takalevel = [-1] * n
takalevel[u - 1] = 0
q = [u - 1]
while len(q) > 0:
    i = q.pop(0)
    ret = max(ret, aolevel[i] - 1)
    if takalevel[i] < aolevel[i]:
        for j in edges[i]:
            if takalevel[j] < 0:
                takalevel[j] = takalevel[i] + 1
                q.append(j)

print(ret)

Solution (Python):
from collections import deque,defaultdict
import copy

def main():
    from collections import defaultdict
    import copy 
    n,u,v = map(int,input().split())
    u -= 1
    v -= 1
    graph = defaultdict(deque)
    for _ in range(n-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    depth = dfs(graph,u,n)
    
    depth2 = dfs(graph,v,n)
    
    ans = 0
    ans2 = 10**6
    for i,j in zip(depth,depth2):
        if i < j:
            ans = max(j,ans)
        
        

    print(ans-1)

def dfs(G,s,n):
    stack = deque([s])
    graph = copy.deepcopy(G)
    depth = [None] * n
    depth[s] = 0
    while stack:
        u = stack[-1]
        if graph[u]:
            v = graph[u].popleft()
            if depth[v] == None:
                depth[v] = depth[u] + 1
                stack.append(v)

        else:
            stack.pop()

    return depth
    

main()

Solution (Python):
import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,u,v = map(int,readline().split())
AB = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = map(int,readline().split())
    AB[a].append(b)
    AB[b].append(a)
    
tdist = [0]*(N+1)
adist = [0]*(N+1)

def tdfs(x,pre):
    for to in AB[x]: 
        if to == pre:
            continue
        tdist[to] = tdist[x]+1
        tdfs(to,x)

def adfs(x,pre):
    for to in AB[x]: 
        if to == pre:
            continue
        adist[to] = adist[x]+1
        adfs(to,x)

tdfs(u,-1)
adfs(v,-1)

ans = 0
for i in range(1,N+1):
    if tdist[i] < adist[i]:
        k = adist[i] - tdist[i]
        ans = max(ans,tdist[i] + k-1)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, a, b = map(int, input().split())
D = [[0]*2 for _ in range(101010)]
E = [[] for _ in range(n)]


def dfs(cur, pre, d, id):
    D[cur][id] = d
    for nv in E[cur]:
        if nv != pre:
            dfs(nv, cur, d+1, id)


a -= 1
b -= 1
for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
dfs(a, a, 0, 0)
dfs(b, b, 0, 1)
max_d = 0
for i in range(n):
    if D[i][0] < D[i][1]:
        max_d = max(max_d, D[i][1]-1)
print(max_d)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,u,v = LI()
Graph = [[] for i in range(N+1)]

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

from collections import deque

q1 = deque([u])
distance1 = [-1]*(N+1)  
distance1[u] = 0



while q1:
    n = q1.pop()
    for d in Graph[n]:
        if distance1[d] != -1:
            continue
        else:
            distance1[d] = distance1[n]+1
            q1.appendleft(d)

q2 = deque([v])
distance2 = [-1]*(N+1)  
distance2[v] = 0



while q2:
    n = q2.pop()
    for d in Graph[n]:
        if distance2[d] != -1:
            continue
        else:
            distance2[d] = distance2[n]+1
            q2.appendleft(d)

q3 = deque([u])
distance3 = [-1]*(N+1)  
distance3[u] = 0



while q3:
    n = q3.pop()
    for d in Graph[n]:
        if distance3[d] != -1 or distance1[d] >= distance2[d]:
            continue
        else:
            distance3[d] = distance3[n]+1
            q3.appendleft(d)



ans = max(distance2[i]-1 for i in range(1,N+1) if distance3[i] >= 0)

print(ans)

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N,u,v = LI()
Graph = [[] for i in range(N+1)]

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

from collections import deque

q1 = deque([u])
distance1 = [-1]*(N+1)  
distance1[u] = 0



while q1:
    n = q1.pop()
    for d in Graph[n]:
        if distance1[d] != -1:
            continue
        else:
            distance1[d] = distance1[n]+1
            q1.appendleft(d)

q2 = deque([v])
distance2 = [-1]*(N+1)  
distance2[v] = 0



while q2:
    n = q2.pop()
    for d in Graph[n]:
        if distance2[d] != -1:
            continue
        else:
            distance2[d] = distance2[n]+1
            q2.appendleft(d)

q3 = deque([u])
distance3 = [-1]*(N+1)  
distance3[u] = 0



while q3:
    n = q3.pop()
    for d in Graph[n]:
        if distance3[d] != -1 or distance1[d] >= distance2[d]:
            continue
        else:
            distance3[d] = distance3[n]+1
            q3.appendleft(d)



ans = 0
for i in range(1,N+1):
    if distance3[i] >= 0:
        ans = max(ans,distance2[i]-1)

print(ans)

Solution (Python):
from collections import defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [-1] * self.n  
        self.depth = [-1] * self.n  
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  
        self.root = root
        self.order = [root]
        self.dist[root] = 0
        self.depth[root] = 0
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  
        u = self.dist.index(max(self.dist))  
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  
            return diameter, path
        else:
            return diameter, u, v

    

    def heavy_light_decompose(self):  
        self.subsize = [1] * self.n  
        self.head = [self.root] * self.n  
        self.tree_order = [0] * self.n

        
        
        for v in reversed(self.order):
            v_kids = self.children[v]  
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        
        
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  
        while True:  
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)



n, u, v = (int(x) for x in input().split())
u -= 1
v -= 1
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
tree = Tree(n, edges)
tree.set_root(0)
tree.heavy_light_decompose()
ans = 0
for i in range(n):
    if tree.get_hld_distance(i, u) <= tree.get_hld_distance(i, v):
        ans = max(ans, tree.get_hld_distance(i, v) - 1)
print(ans)

Solution (Python):
from collections import defaultdict

class Tree:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.parent = [-1] * self.n
        self.children = [[] for _ in range(self.n)]
        self.dist = [-1] * self.n  
        self.depth = [-1] * self.n  
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def set_root(self, root):  
        self.root = root
        self.order = [root]
        self.dist[root] = 0
        self.depth[root] = 0
        stack = [root]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if child == self.parent[v]:
                    continue
                else:
                    self.parent[child] = v
                    self.children[v].append(child)
                    self.dist[child] = self.dist[v] + self.weight[(v, child)]
                    self.depth[child] = self.depth[v] + 1
                    self.order.append(child)
                    stack.append(child)

    def get_root_path(self, target):
        path = [target]
        v = target
        while v != self.root:
            path.append(self.parent[v])
            v = self.parent[v]
        path.reverse()
        return path

    def get_diameter(self, restore=False):  
        u = self.dist.index(max(self.dist))  
        dist_u = [-1] * self.n
        dist_u[u] = 0
        stack = [u]
        parent_u = [None for _ in range(self.n)]
        while stack:
            v = stack.pop()
            for child in self.adj[v]:
                if dist_u[child] == -1:
                    dist_u[child] = dist_u[v] + self.weight[(v, child)]
                    parent_u[child] = v
                    stack.append(child)
        diameter = max(dist_u)
        v = dist_u.index(diameter)
        if restore:
            path = [v]
            while v != u:
                v = parent_u[v]
                path.append(v)
            path.reverse()  
            return diameter, path
        else:
            return diameter, u, v

    

    def heavy_light_decompose(self):  
        self.subsize = [1] * self.n  
        self.head = [self.root] * self.n  
        self.tree_order = [0] * self.n

        
        
        for v in reversed(self.order):
            v_kids = self.children[v]  
            for i, child in enumerate(v_kids):
                self.subsize[v] += self.subsize[child]
                if self.subsize[child] > self.subsize[v_kids[0]]:
                    v_kids[i], v_kids[0] = v_kids[0], v_kids[i]

        
        
        stack = [self.root]
        tree_label = 0
        while stack:
            v = stack.pop()
            self.tree_order[v] = tree_label
            tree_label += 1
            for child in reversed(self.children[v]):  
                if child == self.children[v][0]:
                    self.head[child] = self.head[v]
                else:
                    self.head[child] = child  
                stack.append(child)

    def get_hld_chain_paths(self, u, v):  
        ret = []
        while True:
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                ret.append((self.tree_order[u], self.tree_order[v] + 1))
                return ret
            else:
                ret.append((self.tree_order[self.head[v]], self.tree_order[v] + 1))
                v = self.parent[self.head[v]]

    def get_hld_lca(self, u, v):  
        while True:  
            if self.tree_order[u] > self.tree_order[v]:
                u, v = v, u
            if self.head[u] == self.head[v]:
                return u
            v = self.parent[self.head[v]]

    def get_hld_distance(self, u, v):
        return self.dist[u] + self.dist[v] - (2 * self.dist[self.get_hld_lca(u, v)])

    def exist_on_path_hld(self, u, v, x):  
        return self.get_hld_distance(u, x) + self.get_hld_distance(x, v) == self.get_hld_distance(u, v)



n, u, v = (int(x) for x in input().split())
u -= 1
v -= 1
edges = [tuple(int(x) - 1 for x in input().split()) for _ in range(n - 1)]
tree = Tree(n, edges)
tree.set_root(v)
tree.heavy_light_decompose()
ans = 0
for i in range(n):
    if tree.get_hld_distance(i, u) <= tree.get_hld_distance(i, v):
        ans = max(ans, tree.get_hld_distance(i, v) - 1)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n,U,V = map(int, input().split())
U -= 1
V -= 1
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

def bfs(start, ng=None):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    dist = [None] * n
    dist[start] = 0
    seen[start] = -1
    while q:
        u = q.pop()
        d = dist[u]
        for v in ns[u]:
            if seen[v] is None and (ng is None or v!=ng):
                seen[v] = u
                dist[v] = d + 1
                q.appendleft(v)
    return seen, dist
ps, du = bfs(U)
_, dv = bfs(V)
l = []
tmp = V
while tmp!=U:
    l.append(tmp)
    tmp = ps[tmp]
d = len(l)
l = l[::-1]
dist = d//2 if d%2 else d//2-1
ng = l[dist]
start = U if dist==0 else l[dist-1]
_, D = bfs(start, ng=ng)
if max(item for item in D if item is not None)==0:
    ans = dv[start] - 1
else:
    ans = -1
    for i,num in enumerate(D):
        if num is None:
            continue
        val = num + dv[start] - 1
        ans = max(ans, val)
print(ans)

Solution (Python):
from collections import deque

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

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

def find_dist(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        for v in tree[u]:
            if dist[v] >= 0:
                continue
                
            dist[v] = dist[u] + 1
            q.append(v)
            
    return dist


dist_u = find_dist(U)
dist_v = find_dist(V)

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

Solution (Python):
from collections import deque
N,U,V = map(int, input().split())
U,V = U-1, V-1
E = [[] for _ in range(N)]

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

def BFS(root):
  D = [ 0 for _ in range(N) ]
  visited = [False for _ in range(N)]
  willSearch = [ False for _ in range(N)]
  Q = deque()
  Q.append(root)
  willSearch[root] = True
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True
    for nx in E[now]:
      if visited[nx] or willSearch[nx]:
        continue
      willSearch[nx] = True
      D[nx] = D[now] + 1
      Q.append(nx)
  return D

UD = BFS(U)
VD = BFS(V)





if E[U] == [V]:
  print(0)
  exit(0)
  
ans=0
 
for i in range(N):
    if UD[i]<=VD[i]:
        ans=max(ans,VD[i]-1)

print(ans)

Solution (Python):
from collections import deque
N,U,V = map(int, input().split())
U,V = U-1, V-1
E = [[] for _ in range(N)]

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

def BFS(root):
  D = [ 0 for _ in range(N) ]
  visited = [False for _ in range(N)]
  willSearch = [ False for _ in range(N)]
  Q = deque()
  Q.append(root)
  willSearch[root] = True
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True
    for nx in E[now]:
      if visited[nx] or willSearch[nx]:
        continue
      willSearch[nx] = True
      D[nx] = D[now] + 1
      Q.append(nx)
  return D

UD = BFS(U)
VD = BFS(V)





if E[U] == [V]:
  print(0)
  exit(0)
  
ans=0
 
for i in range(N):
    if UD[i]<=VD[i]:
        ans=max(ans,VD[i]-1)

print(ans)

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

def dist(x):
    dist=[-1]*(N+1)
    dist[x]=0
    stack=[x]
    while len(stack)>0:
        current=stack.pop()

        for s in g[current]:
            if dist[s]>-1:
                continue

            dist[s]=dist[current]+1
            stack.append(s)

    return dist

for _ in range(N-1):
    a,b=list(map(int,input().split()))

    g[a].append(b)
    g[b].append(a)

du=dist(u)
dv=dist(v)

ans=0

for i in range(1,N+1):
    if du[i]<=dv[i]:
        ans=max(ans,dv[i]-1)

print(ans)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, p, q, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    p -= 1
    q -= 1

    if len(G[p]) == 1 and G[p][0] == q:
        print(0)
        return

    dist1 = [-1] * N
    dist1[p] = 0
    queue1 = deque([p])
    while queue1:
        v = queue1.popleft()
        for nv in G[v]:
            if dist1[nv] == -1:
                dist1[nv] = dist1[v] + 1
                queue1.append(nv)

    dist2 = [-1] * N
    dist2[q] = 0
    queue2 = deque([q])
    while queue2:
        v = queue2.popleft()
        for nv in G[v]:
            if dist2[nv] == -1:
                dist2[nv] = dist2[v] + 1
                queue2.append(nv)

    max_dist = -1
    for d1, d2 in zip(dist1, dist2):
        if d1 < d2 and max_dist < d2:
            max_dist = d2

    print(max_dist - 1)
    return


if __name__ == '__main__':
    main()

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

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

dist=[[-1, -1] for _ in range(n)]
dist[v][0]=0
dist[u][1]=0
 
def dfs(graph,v,k):
    ver=graph[v]
    for vers in ver:
        if dist[vers][k]==-1:
            dist[vers][k]=dist[v][k]+1
            dfs(graph,vers,k)
 
 
dfs(graph,v,0)
dfs(graph,u,1)
dist.sort(reverse=True)
 
for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Solution (Python):
from collections import deque

def bfs(s):
    stack=deque([s])
    check = [-1]*n
    check[s] = 0
    while len(stack)>0:
        v = stack.popleft()
        for i in root[v]:
            if check[i] == -1:
                check[i]=check[v]+1
                stack.append(i)
    return check

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

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

takahashi_root = bfs(u-1)
aoki_root = bfs(v-1)

ans = 0

for i in range(n):
    if takahashi_root[i] < aoki_root[i]:
        ans = max(ans,aoki_root[i]-1)
print(ans)

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
























N,u,v = map(int,readline().split())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)

dist_from_u = [0 for i in range(N)] 
dist_from_v = [0 for i in range(N)] 

stack = []

stack.append([u - 1,0,-1])
while stack:
  e, dist, parent = stack.pop()
  dist_from_u[e] = dist
  for child in G[e]:
    if child == parent:
      continue
    stack.append([child, dist + 1, e])

stack = []

stack.append([v - 1,0,-1])
while stack:
  e, dist, parent = stack.pop()
  dist_from_v[e] = dist
  for child in G[e]:
    if child == parent:
      continue
    stack.append([child, dist + 1, e])
    
maxdiff_from_v = 0
for i in range(N):
  if dist_from_u[i] < dist_from_v[i]:
    if maxdiff_from_v < dist_from_v[i]:
      maxdiff_from_v = dist_from_v[i]
    
print(maxdiff_from_v - 1)

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, u, v = ns()
    edge = [[] for _ in range(n)]

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

    dist_takahashi = [-1] * n
    dist_aoki = [-1] * n

    def bfs(pos, dist):
        que = queue.Queue()
        que.put(pos)
        dist[pos] = 0

        while not que.empty():
            current = que.get()
            for e in edge[current]:
                if dist[e] == -1:
                    dist[e] = dist[current] + 1
                    que.put(e)

        return dist

    dist_takahashi = bfs(u - 1, dist_takahashi)
    dist_aoki = bfs(v - 1, dist_aoki)

    ans = 0
    for dt, da in zip(dist_takahashi, dist_aoki):
        if dt < da:
            ans = max(ans, da - 1)

    print(ans)


if __name__ == '__main__':
    main()

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


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

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






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

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

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


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

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





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

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

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

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

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

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

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][0]==-1:
            dist[vvv][0]=dist[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if dist[vvv][1]==-1:
            dist[vvv][1]=dist[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
dist.sort(reverse=True)

for i in range(10**6):
    if dist[i][0]-dist[i][1]>=1:
        print(dist[i][0]-1)
        break

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
 
N,u,v = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
E = [[] for _ in range(N+1)]
for a,b in edges:
    E[a].append(b)
    E[b].append(a)
 
depth = [[-1,-1] for _ in range(N+1)] 
depth[v][0] = 0
depth[u][1] = 0

def dfs1(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][0] == -1:
            depth[vvv][0] = depth[v][0] + 1
            dfs1(E,vvv)
 
def dfs2(E,v):
    vv = E[v]
    for vvv in vv:
        if depth[vvv][1] == -1:
            depth[vvv][1] = depth[v][1] + 1
            dfs2(E,vvv)
dfs1(E,v)
dfs2(E,u)
depth = sorted(depth, reverse=True)
idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1

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

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

distT = [-1]*n
distA = [-1]*n
distT[u] = 0
distA[v] = 0
def dfs(now,dist):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        dfs(nxt,dist)
dfs(u,distT)
dfs(v,distA)

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

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

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

def dfs1(pos, before_pos):
    for next_pos in ab[pos]:
        if next_pos == before_pos:
            continue
        if next_pos == u:
            return True, [pos]
        tf, root = dfs1(next_pos, pos)
        if tf:
            root.append(pos)
            return True, root
    return False, []
    
root = dfs1(v, -1)[1]
root = root[::-1]
root.append(u)
n = (len(root) + 1) // 2
pos = root[n]
before_pos = root[n - 1]

max_len = n

def dfs2(pos, before_pos, cnt):
    global max_len
    cnt += 1
    max_len = max(max_len, cnt)
    if cnt < n - 1:
        dfs2(root[cnt + 1], pos, cnt)
    else:
        for next_pos in ab[pos]:
            if next_pos == before_pos:
                continue
            dfs2(next_pos, pos, cnt)


dfs2(pos, before_pos, n - 1)
ans = max_len - 1
ans = max(ans, 0)
print(ans)