题目描述

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 $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.

输入格式

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 \ne 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.

输出格式

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.

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

8
6

提示

Sample Explanation

The possible rootings of the first tree are

:::align{center} :::

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.