题目描述

一个艺术展有 $N$ 个展区，编号为 $1$ 到 $N$。展区之间有 $N-1$ 条双向连廊，任意两个展区之间都可以互相到达。

展区 $i$ 的停留时间等于与该展区直接相连的连廊数量。

共有 $M$ 次询问。每次给出两个展区 $U_i,V_i$，参观者从 $U_i$ 出发，沿两点之间唯一的简单路径到达 $V_i$。请计算这条路径上所有展区的停留时间之和，其中包括起点和终点。

输入格式

第一行包含两个整数 $N,M$，表示展区数量和询问数量。

接下来 $N-1$ 行，每行包含两个整数 $x,y$，表示展区 $x$ 和展区 $y$ 之间有一条双向连廊。

接下来 $M$ 行，每行包含两个整数 $U_i,V_i$，表示一次询问。

输出格式

对于每次询问输出一行，表示对应参观路径上的停留时间之和。

样例

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

5
6
1

样例解释

四个展区的停留时间依次为 $2,2,1,1$。从展区 $2$ 到展区 $3$ 的路径为 $2\to1\to3$，停留时间之和为 $2+2+1=5$。

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

2
4
2
3
6

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le N,M \le 1000$。
• 对于 $100\%$ 的数据，$1 \le N,M \le 10^5$。
• $1 \le x,y,U_i,V_i \le N$。
• 输入的连廊保证构成一棵树。