一家航空公司提供连接 $n$ 个不同机场的定期航班。每条航线直接连接两个机场（即中间不停靠其他机场），且允许双向通行。这些航线的安排使得对于任意选择的起点机场 $s$ 和终点机场 $t$，在不重复经过任何机场的前提下，两个机场之间存在唯一的一条航线序列。这条序列中的航线数量被称为 $s$ 和 $t$ 之间的距离。

如果航空公司增加一条航线，例如在机场 $x$ 和 $y$ 之间增加航线，那么对于某些机场对 $(s, t)$，可能会形成另一条更短的航线序列。受影响的机场对越多，在 $x$ 和 $y$ 之间建立的新连接就被认为越有价值。航空公司请求你帮助他们根据这一标准评估若干可能的航线增加方案 $(x, y)$。

输入格式

第一行包含两个整数 $n$（机场数量）和 $q$（待评估的可能增加的航线数量）。

接下来的 $n-1$ 行描述了增加航线前的原始航线。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示机场 $u_i$ 和 $v_i$ 之间存在直接航线连接。

剩余的 $q$ 行描述了正在考虑的可能增加的航线。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示在第 $i$ 种方案中，原始的 $n-1$ 条航线将由机场 $x_i$ 和 $y_i$ 之间的一条新直接航线补充。

数据范围

• $2 \le n \le 10^6$
• $1 \le q \le 10^5$
• $1 \le u_i \le n; 1 \le v_i \le n; u_i \neq v_i$
• $1 \le x_i \le n; 1 \le y_i \le n; x_i \neq y_i$
• $\sum_{i=1}^q d_i \le 10^7$，其中 $d_i$ 是原始航线网络中 $x_i$ 和 $y_i$ 之间的距离。

输出格式

输出 $q$ 行；第 $i$ 行输出满足 $1 \le s < t \le n$ 且在原始 $n-1$ 条航线网络中补充机场 $x_i$ 和 $y_i$ 之间的直接航线后，机场 $s$ 和 $t$ 之间的距离会减小的机场对 $(s, t)$ 的数量。

样例

输入 1

8 2
1 5
5 2
7 3
3 8
6 4
4 5
6 3
5 7
2 6

输出 1

10
4