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

Input

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

Output

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

Input

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

Output

9
7
9
2
9
7
4
7
7
9