Pondo Tree Distance

You are given a tree with $n$ vertices and $q$ queries. Each query gives two vertices $u$ and $v$. Output the number of edges on the unique path between $u$ and $v$.

This is a follow-up to Pondo LCA II. Root the tree at vertex $1$, then

$\mathrm{dist}(u, v) = \mathrm{depth}[u] + \mathrm{depth}[v] - 2 \cdot \mathrm{depth}[\mathrm{lca}(u, v)]$.

In particular, $\mathrm{dist}(u, u) = 0$. Use an Euler tour to compute the lowest common ancestors.

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 endpoints of one path.

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

Output

Print $q$ lines. The $i$-th line should contain the distance between the two vertices of the $i$-th query.

Constraints

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

Example 1

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

2
2
3
2
1
0

Explanation

The tree looks like this:

      1
     / \
    2   5
   / \
  3   4

Rooted at $1$, the depths of vertices $1, 2, 3, 4, 5$ are $0, 1, 2, 2, 1$. Then $\mathrm{dist}(3, 5) = 2 + 1 - 2 \cdot 0 = 3$, and $\mathrm{dist}(4, 4) = 0$.

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

1
2
4
3
4
2
3
2
3
4