Pondo LCA I

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. Unlike the enter/exit tour (first and last visit only), record a vertex every time you visit it: when you first enter it, and again each time you return from a child. The lowest common ancestor of $u$ and $v$ is then the vertex of minimum depth on the tour between their first visits.

The bounds are small, so you may scan that range in $O(n)$ time per query.

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^2$
• $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