There is a tree containing $N$ nodes that is connected with $N-1$ edges. This tree is rooted at node $1$. A path is defined as a sequence of at least two nodes where consecutive nodes are connected in the tree by edges, and every node occurs at most once. As such, there are exactly $\frac{N\times (N-1)}{2}$ paths in the tree. The length of a path is defined as the number of edges in that path.

The heaviness of the tree is defined as the average length of all the paths in the tree. Recall that the average in this case is ${\displaystyle \frac{\text{sum of the path lengths}}{\text{number of paths}}}$.

Evan is planning to modify the tree. He will choose two nodes, $i$ and $j$, such that $i$ and $j$ are not in each other's subtree (not ancestors of one another), and ask you:

• If the subtree rooted at node $i$ is swapped with the subtree rooted at node $j$ (that is, $i$ and all of its descendants are moved to the location of $j$, and vice versa), is the heaviness of the resultant tree lower, equal, or higher than the original tree's heaviness?

He will ask $Q$ of these questions. Note that the questions are not persistent.

Input Specification

The first line will contain two integers, $N,Q$ $(3\le N\le {10}^5,1\le Q\le {10}^5)$.

The next $N-1$ lines will each contain two integers, $u,v$ $(1\le u,v\le N)$, the edges of the tree.

The next $Q$ lines will each contain two integers, $i,j$ $(1\le i,j\le N,i\ne j)$, a question as defined above. $i$ and $j$ will not be ancestors of one another.

Output Specification

For each question, output -1 if the heaviness in the resultant tree is less than in the original tree, 0 if it is equal, and 1 if it is greater, on its own line.

Constraints

Subtask 1 [5%]

$Q,N\le 100$

Subtask 2 [35%]

$Q,N\le 1000$

Subtask 3 [60%]

No additional constraints.

Sample Input 1

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

Sample Output 1

0
0
1

Explanation For Sample 1

The original tree is shown:

The heaviness is $\frac{31}{15}\approx 2.067$.

For the third question, the tree looks like:

The new heaviness is $\frac{32}{15}\approx 2.133$, which is larger than $\frac{31}{15}$.

Sample Input 2

13 10
1 12
12 13
1 2
2 3
2 4
2 5
2 6
3 7
7 8
8 9
9 10
10 11
7 12
8 12
9 12
10 12
11 12
8 4
7 5
3 6
3 12
3 13

Sample Output 2

0
-1
-1
0
1
-1
-1
0
1
1