Pondo LCA II

You are given a tree with $n$ vertices, rooted at vertex $1$, and $q$ queries. Each query gives two vertices $u$ and $v$. Output the lowest common ancestor of $u$ and $v$.

The lowest common ancestor of $u$ and $v$ is the deepest vertex that lies on both the path from the root to $u$ and the path from the root to $v$. In particular, $\mathrm{lca}(u, u) = u$, and if $u$ is an ancestor of $v$ then $\mathrm{lca}(u, v) = u$.

Solve the queries with an Euler tour, the same way as in Pondo LCA I: record a vertex every time you visit it, then the lowest common ancestor of $u$ and $v$ is the vertex of minimum depth on the tour between their first visits.

The bounds are larger here, so scanning that range per query is too slow. Use the sparse table below to find the index of the minimum value in a range in $O(1)$ time after $O(n \log n)$ preprocessing. query(L, R) is inclusive.

class SparseTable:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)
        self.log = [0] * (self.n + 1)
        self._compute_logs()
        self.st = self._build_sparse_table()

    def _compute_logs(self):
        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1

    def _build_sparse_table(self):
        k = self.log[self.n] + 1
        st = [[(0, 0)] * k for _ in range(self.n)]
        for i in range(self.n):
            st[i][0] = (self.arr[i], i)
        j = 1
        while (1 << j) <= self.n:
            i = 0
            while i + (1 << j) - 1 < self.n:
                if st[i][j - 1][0] < st[i + (1 << (j - 1))][j - 1][0]:
                    st[i][j] = st[i][j - 1]
                else:
                    st[i][j] = st[i + (1 << (j - 1))][j - 1]
                i += 1
            j += 1
        return st

    def query(self, L, R):
        j = self.log[R - L + 1]
        left = self.st[L][j]
        right = self.st[R - (1 << j) + 1][j]
        if left[0] < right[0]:
            return left
        return right

Input

The first line contains two integers $n$ and $q$.

Each of the next $n - 1$ lines contains two integers $u$ and $v$, denoting an undirected edge between $u$ and $v$.

Each of the next $q$ lines contains two integers $u$ and $v$, the vertices of one query.

Vertices are numbered $1$ through $n$. The edges form a tree.

Output

Print $q$ lines. The $i$-th line should contain the lowest common ancestor of the $i$-th query.

Constraints

• $1 \le n, q \le 10^5$
• $1 \le u, v \le n$

Example 1

5 5
1 2
2 3
2 4
1 5
2 5
5 2
3 4
2 3
4 4

1
1
2
2
4

Explanation

The tree, rooted at $1$, looks like this:

      1
     / \
    2   5
   / \
  3   4

• $\mathrm{lca}(2, 5) = 1$
• $\mathrm{lca}(5, 2) = 1$
• $\mathrm{lca}(3, 4) = 2$
• $\mathrm{lca}(2, 3) = 2$
• $\mathrm{lca}(4, 4) = 4$

Example 2

10 10
4 7
7 8
2 4
6 7
8 10
5 8
2 9
3 7
1 9
2 9
6 8
8 9
2 8
8 9
3 8
4 10
5 7
5 6
3 9

9
7
9
2
9
7
4
7
7
9