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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


import collections
import itertools

class edge():
    def __init__(self, src: int, to: int, cost: int):
        self.src = src
        self.to = to
        self.cost = cost
    def __str__(self):
        return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append(root)
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v]:
                if u.to != self.parent(v):
                    self.par[0][u.to] = v
                    self.depth[u.to] = self.depth[v] + 1
                    que.append(u.to)

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i, j in itertools.product(range(self._l - 1), range(self.size)):
            if(self.par[i][j] == -1):
                self.par[i + 1][j] = -1
            else:
                self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    ans = -1
    
    
    
    
    
    g.build(v)
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


import collections

class edge():
    def __init__(self, src: int, to: int, cost: int):
        self.src = src
        self.to = to
        self.cost = cost
    def __str__(self):
        return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


import collections

class edge():
    def __init__(self, src: int, to: int, cost: int):
        self.src = src
        self.to = to
        self.cost = cost
    def __str__(self):
        return "(" + str(self.src) + ", " + str(self.to) + ", " + str(self.cost) + ")"

class rootedtree():
    def __init__(self, n: int) -> None:
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]  
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src: int, to: int, cost: int = 1):
        self.graph[src].append(edge(src, to, cost))
        self.graph[to].append(edge(to, src, cost))

    def parent(self, x: int):
        return self.par[0][x]

    def bfs(self, s: int) -> list:
        INF = 10**9
        dist = [INF] * self.size
        que = collections.deque()  
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != INF:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r):
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

from queue import Queue as queue
class rootedtree():
    def __init__(self, n):
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def bfs(self, s: int) -> list:
        dist = [10**9] * self.size
        que = queue()
        que.put(s)
        dist[s] = 0
        while not que.empty():
            v = que.get()
            for e in self.graph[v]:
                if dist[e.to] != 10**9:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.put(e.to)
        return dist

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = queue()
        que.put((0, root))
        while not que.empty():
            v = que.get()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.put((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

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


def treeDist(u, E):
    D = [-1]*len(E)
    q = [(u, 0)]
    while q:
        i, d = q.pop()
        if D[i] != -1:
            continue
        D[i] = d
        for j in E[i]:
            q.append((j, d+1))
    return D


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

    D1 = treeDist(u-1, E)
    D2 = treeDist(v-1, E)
    ans = 0
    for d1, d2 in zip(D1, D2):
        if d1 < d2:
            ans = max(ans, d2)
    print(ans-1)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

import collections
class rootedtree():
    def __init__(self, n):
        _l = 0
        while pow(2, _l) < n:
            _l += 1
        self._l = _l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(_l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def bfs(self, s: int) -> list:
        dist = [10**9] * self.size
        que = collections.deque()
        que.append(s)
        dist[s] = 0
        while len(que):
            v = que.popleft()
            for e in self.graph[v]:
                if dist[e.to] != 10**9:
                    continue
                dist[e.to] = dist[e.src] + 1
                que.append(e.to)
        return dist

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    du = g.bfs(u)
    dv = g.bfs(v)
    ans = -1
    for i in range(n):
        if du[i] < dv[i]:
            ans = max(ans, dv[i])
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()


import collections
class edge():
    def __init__(self, src, to):
        self.src = src
        self.to = to
    def __str__(self):
        return "(" + str(self._from) + ", " + str(self._to) + ")"

class rootedtree():
    def __init__(self, n):
        l = 0
        while pow(2, l) < n:
            l += 1
        self._l = l
        self.size = n
        self.par = [[-1 for i in range(n + 1)] for i in range(l)]
        self.graph = [[] for i in range(n)]
        self.depth = [-1 for i in range(n)]
        self.root = -1

    def add_edge(self, src, to):
        self.graph[src].append(edge(src, to))
        self.graph[to].append(edge(to, src))

    def parent(self, i):
        return self.par[0][i]

    def __dfs1(self, r) -> None:
        root = r
        self.depth[r] = 0
        que = collections.deque()
        que.append((0, root))
        while len(que) != 0:
            v = que.pop()
            for u in self.graph[v[1]]:
                if u.to != self.parent(v[1]):
                    self.par[0][u.to] = v[1]
                    self.depth[u.to] = v[0] + 1
                    que.append((v[0] + 1, u.to))

    def build(self, _root=0) -> None:
        assert(self.root == -1)
        self.root = _root
        self.__dfs1(self.root)
        for i in range(self._l - 1):
            for j in range(self.size):
                if(self.par[i][j] == -1):
                    self.par[i + 1][j] = -1
                else:
                    self.par[i + 1][j] = self.par[i][self.par[i][j]]

    def lca(self, x: int, y: int) -> int:
        assert(self.root != -1)
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        dif = self.depth[y] - self.depth[x]
        for i in range(self._l - 1, -1, -1):
            if dif & (1 << i):
                y = self.par[i][y]
        if x == y:
            return x
        for i in range(self._l - 1, -1, -1):
            nx = self.par[i][x]
            ny = self.par[i][y]
            if nx != ny:
                x = nx; y = ny
        return self.par[0][x]

    def depth_dif(self, x: int, y: int) -> int:
        assert(self.root != -1)
        z = self.lca(x, y)
        return self.depth[x] + self.depth[y] - 2 * self.depth[z]

def main():
    n, u, v = mi()
    u -= 1; v -= 1
    g = rootedtree(n)
    for _ in range(n - 1):
        a, b = mi()
        g.add_edge(a - 1, b - 1)
    g.build(v)
    ans = -1
    for i in range(n):
        x = g.lca(u, i)
        if g.depth_dif(u, x) < g.depth_dif(v, x):
            ans = max(ans, g.depth_dif(v, i))
    print(ans - 1)
    return


if __name__ == '__main__':
    main()

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


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


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


if __name__ == '__main__':
    solve()

Solution (Python):
import 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
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)
        E[v].append(u)

    
    dx=[None]*n
    dx[x]=0
    Q=[(x,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            dx[nv]=dx[v]+1
            Q.append((nv,v))

    dy=[None]*n
    dy[y]=0
    Q=[(y,-1)]
    while(Q):
        v,p=Q.pop()
        for nv in E[v]:
            if(nv==p): continue
            dy[nv]=dy[v]+1
            Q.append((nv,v))

    
    ans=0
    for v in range(n):
        if(dx[v]<dy[v]):
            ans=max(ans,dy[v]-1)

    print(ans)
resolve()

Solution (Python):
import sys

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

(n,u,v)=na()
u -= 1
v -= 1

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

for i in range(0, n-1):
    (a, b) = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)


dep1 = [0] * n
dep2 = [0] * n
def dfs(now, pre, d, dep):
    dep[now] = d
    for nex in g[now]:
        if pre == nex:
            continue
        dfs(nex,now,d+1,dep)


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

ret = 0
for i in range(n):
    if dep1[i] < dep2[i]:
        ret = max(ret, dep2[i]-1)
print(ret)

Solution (Python):
from collections import deque

def main():
    N, u, v, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        E[a].append(b)
        E[b].append(a)

    def game(s):
        D = [-1] * (N + 1)
        D[s] = 0

        Q = deque([s])
        while Q:
            a = Q.popleft()
            for b in E[a]:
                if D[b] != -1:
                    continue
                D[b] = D[a] + 1
                Q.append(b)

        return D[1:]

    taka = game(u)
    aoki = game(v)

    print(-1 + max(a for t, a in zip(taka, aoki) if t < a))

main()

Solution (Python):
def f(s):
  d=[-1]*-~n
  d[s]=0
  q=[s]
  while q:
    v=q.pop()
    c=d[v]+1
    for w in e[v]:
      if d[w]<0:
        d[w]=c
        q+=w,
  return d
n,u,v,*t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for a,b in zip(*[iter(t)]*2):
  e[a]+=b,
  e[b]+=a,
m=0
for a,b in zip(*map(f,(u,v))):
  if a<b:m=max(m,b-1)
print(m)

Solution (Python):
def f(s):
  d=[-1]*-~n
  d[s]=0
  q=[s]
  while q:
    v=q.pop()
    c=d[v]+1
    for w in e[v]:
      if d[w]<0:
        d[w]=c
        q+=w,
  return d
n,u,v,*t=map(int,open(0).read().split())
e=[[]for _ in range(n+1)]
for a,b in zip(*[iter(t)]*2):
  e[a]+=b,
  e[b]+=a,
m=0
for a,b in zip(*map(f,(u,v))):
  if a<b:m=max(m,b-1)
print(m)

Solution (Python):
N,U,V = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
U,V = U-1,V-1

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

if len(es[U]) == 1 and es[U][0] == V:
    print(0)
    exit()

dv = [N] * N
dv[V] = 0
stack = [V]
while stack:
    v = stack.pop()
    for to in es[v]:
        if dv[to] != N: continue
        dv[to] = dv[v]+1
        stack.append(to)

ok = dv[U] - (dv[U]-1) // 2

visited = [0] * N
visited[U] = 1
stack = [U]
while stack:
    v = stack.pop()
    for to in es[v]:
        if visited[to]: continue
        if dv[to] < ok: continue
        visited[to] = 1
        stack.append(to)

mx = -1
for i in range(N):
    if not visited[i]: continue
    mx = max(mx, dv[i])
print(mx - 1)

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

def bfs(s):
    dist = [-1]*N
    q = deque([s])
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N, u, v = map(int, input().split())
adj_list = [[] for _ in range(N)]
degree = [0]*N

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)
    degree[Ai-1] += 1
    degree[Bi-1] += 1
    
d1 = bfs(u-1)
d2 = bfs(v-1)
ans = 0

for i in range(N):
    if degree[i]==1 and d1[i]<d2[i]:
        ans = max(ans, d2[i]-1)
        
    
        
    
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(500*500) 

class neighborList():
    def __init__(self,N):
        self.to=[[] for j in range(N)] 

def calcDist(v_,p=-1,dist=0): 
    distList[v_]=dist
    lst=neighborList.to[v_] 
    for child in lst:
        if child==p:
            continue
        calcDist(child,v_,dist+1)
    return distList


N, u, v = map(int, input().strip().split()) 
u-=1
v-=1
neighborList = neighborList(N)
for i in range(N-1):
    A, B = map(int, input().strip().split())
    A-=1 
    B-=1
    neighborList.to[A].append(B)
    neighborList.to[B].append(A)

distList=[0]*N
distT = calcDist(u)
distList=[0]*N
distA = calcDist(v)

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

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

def bfs(s):
    dist = [-1]*N
    q = deque([s])
    dist[s] = 0
    
    while q:
        v = q.popleft()
        
        for nv in adj_list[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N, u, v = map(int, input().split())
adj_list = [[] for _ in range(N)]
degree = [0]*N

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)
    degree[Ai-1] += 1
    degree[Bi-1] += 1
    
d1 = bfs(u-1)
d2 = bfs(v-1)
ans = 0

for i in range(N):
    if degree[i]==1 and d1[i]<d2[i]:
        ans = max(ans, d2[i]-1)
        
    if d1[i]==d2[i] and d1[i]+d2[i]==d1[v-1]:
        ans = max(ans, d1[i])
    
print(ans)

Solution (Python):
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

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

d = deque([[v,0]])
while d:
  n,cnt = d.popleft()
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      d.append([x, cnt+1])

dd = deque([[u,0]])
while dd:
  n,cnt = dd.popleft()
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
  for x in edge[n]:
    if choku_visited[x] == False:
      dd.append([x, cnt+1])




ans = 0
for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(200000)
n,u,v = map(int,input().split())
edge = [[] for i in range(n+1)]
distt = [0 for i in range(n+1)]
dista = [0 for i in range(n+1)]

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

def tdfs(x, last = -1):
    for to in edge[x]:
        if(to == last):continue
        distt[to] = distt[x] + 1
        tdfs(to, x)

def adfs(x, last = -1):
    for to in edge[x]:
        if(to == last):continue
        dista[to] = dista[x] + 1
        adfs(to, x)

tdfs(u)
adfs(v)
ans = 0

for i in range(1, n+1):
    if distt[i] >= dista[i]:continue
    l = distt[i]
    k = dista[i] - distt[i]
    ans = max(ans, k - 1 + l)

print(ans)