F. LCS of DFS orders
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Consider the following pseudocode, which performs a preorder traversal of the tree: 


a = []
function preorder_traversal(u):
    append u to the back of a
    for each v that is adjacent to u and not visited:
        preorder_traversal(v)

Note that the resulting array $$$a$$$, representing the preorder traversal of the tree starting from node $$$u$$$, may vary depending on the order in which adjacent vertices are visited.

Let $$$S_u$$$ denote the set of all possible arrays $$$a$$$ that can be obtained by running the above traversal starting from vertex $$$u$$$, allowing all possible orderings of adjacent nodes during traversal.

For any two vertices $$$u$$$ and $$$v$$$, define the function $$$f(u, v)$$$ as follows: $$$$$$\min_{a_1 \in S_u, a_2 \in S_v} \text{LCS}(a_1, a_2)$$$$$$ where $$$\text{LCS}(a_1, a_2)$$$ denotes the length of the longest common subsequence between the two arrays $$$a_1$$$ and $$$a_2$$$.

For example, consider a tree with $$$5$$$ vertices and edges $$$(1,2),(1,3), (3,4), (3,5)$$$. Then we have:

  • $$$S_1 = \{[1,2,3,4,5],[1,2,3,5,4],[1,3,4,5,2],[1,3,5,4,2]\}$$$
  • $$$S_4 = \{[4,3,5,1,2], [4,3,1,2,5]\}$$$

Then we have $$$f(1,4) = 2$$$, because the smallest possible LCS length among all combinations of arrays from $$$S_1$$$ and $$$S_4$$$ is 2.

You are given $$$q$$$ queries. Each query consists of two (not necessarily distinct) vertices $$$x_i$$$ and $$$y_i$$$. For each query, compute the value of $$$f(x_i, y_i)$$$.

Input

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ — the number of vertices of the tree and the number of queries.

The $$$i$$$-th of the following $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ — the ends of the $$$i$$$-th edge.

The $$$i$$$-th of the following $$$q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the vertices in the query.

  • $$$1 \le n \le 2 \cdot 10^5$$$
  • $$$1 \le q \le 2 \cdot 10^5$$$
  • $$$1 \le u_i, v_i\le n$$$ and $$$u_i \neq v_i$$$ for $$$i = 1,2,\ldots,n$$$.
  • $$$1 \le x_i, y_i \le n$$$ for $$$i = 1,2,\ldots,q$$$.
  • It is guaranteed that the given edges form a tree.
Output

For each query, output a single integer in a new line — the value of $$$f(x_i,y_i)$$$.

Examples
Input
5 2
1 2
1 3
3 4
3 5
1 4
3 3
Output
2
3
Input
7 2
1 2
2 3
2 5
1 4
4 6
4 7
5 6
3 5
Output
2
4