给定一个包含 $n$ 个节点和 $n+1$ 条边的连通简单图（即一棵树外加两条边），回答一系列询问：对于两个不同的节点，它们之间有多少条简单路径？简单路径是指不重复经过节点的路径。

输入格式

第一行包含两个整数 $n$ ($4 \le n \le 5 \times 10^4$) 和 $q$ ($1 \le q \le 5 \times 10^4$)，其中 $n$ 是节点数，$q$ 是询问次数。节点编号从 $1$ 到 $n$。

接下来的 $n+1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示节点 $a$ 和 $b$ 之间有一条边。所有边均不相同。

接下来的 $q$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le n$)。这是一次关于节点 $u$ 和 $v$ 之间简单路径数量的询问。

输出格式

输出 $q$ 行。每行输出一个整数，表示询问节点之间的简单路径数量。按输入顺序输出询问的答案。

样例

样例输入 1

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

样例输出 1

3
3
3
3
3
4

样例输入 2

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

样例输出 2

2
2
4
1