Problem C
Rooted Subtrees

A tree is a connected, acyclic, undirected graph with $n$ nodes and $n - 1$ edges. There is exactly one path between any pair of nodes. A rooted tree is a tree with a particular node selected as the root.

Let $T$ be a tree and $T_ r$ be that tree rooted at node $r$. The subtree of $u$ in $T_ r$ is the set of all nodes $v$ where the path from $r$ to $v$ contains $u$ (including $u$ itself). In this problem, we denote the set of nodes in the subtree of $u$ in the tree rooted at $r$ as $T_ r(u)$.

You are given $q$ queries. Each query consists of two (not necessarily different) nodes, $r$ and $p$. A set of nodes $S$ is “obtainable” if and only if it can be expressed as the intersection of a subtree in the tree rooted at $r$ and a subtree in the tree rooted at $p$. Formally, a set $S$ is “obtainable” if and only if there exist nodes $u$ and $v$ where $S = T_{r}(u) \cap T_{p}(v)$.

For a given pair of roots, count the number of different non-empty obtainable sets. Two sets are different if and only if there is an element that appears in one, but not the other.

Input

The first line contains two space-separated integers $n$ and $q$ $(1 \le n, q \le 2 \cdot 10^5)$, where $n$ is the number of nodes in the tree and $q$ is the number of queries to be answered. The nodes are numbered from $1$ to $n$.

Each of the next $n - 1$ lines contains two space-separated integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), indicating an undirected edge between nodes $u$ and $v$. It is guaranteed that this set of edges forms a valid tree.

Each of the next $q$ lines contains two space-separated integers $r$ and $p$ ($1 \le r,p \le n$), which are the nodes of the roots for the given query.

Output

For each query output a single integer, which is the number of distinct obtainable sets of nodes that can be generated by the above procedure.

Sample Explanation

The possible rootings of the first tree are

Considering the rootings at $1$ and $3$, the $8$ obtainable sets are:

1. $\{ 1\} $ by choosing $u = 1$, $v = 1$,

2. $\{ 1, 2, 4, 5\} $ by choosing $u = 1$, $v = 2$,

3. $\{ 1, 2, 3, 4, 5\} $ by choosing $u = 1$, $v = 3$,

4. $\{ 2, 3, 4, 5\} $ by choosing $u = 2$, $v = 3$,

5. $\{ 2, 4, 5\} $ by choosing $u = 2$, $v = 2$,

6. $\{ 3\} $ by choosing $u = 3$, $v = 3$,

7. $\{ 4, 5\} $ by choosing $u = 2$, $v = 4$,

8. and $\{ 5\} $ by choosing $u = 5$, $v = 5$.

If the rootings are instead at $4$ and $5$, there are only $6$ obtainable sets:

1. $\{ 1\} $ by choosing $u = 1$, $v = 1$,

2. $\{ 1, 2, 3\} $ by choosing $u = 2$, $v = 4$,

3. $\{ 1, 2, 3, 4\} $ by choosing $u = 4$, $v = 4$,

4. $\{ 1, 2, 3, 4, 5\} $ by choosing $u = 4$, $v = 5$,

5. $\{ 3\} $ by choosing $u = 3$, $v = 2$,

6. and $\{ 5\} $ by choosing $u = 5$, $v = 5$.

For some of these, there are other ways to choose $u$ and $v$ to arrive at the same set.

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

8
6