题目描述

艺术家小 $A$ 在一个大型的艺术展中参观。整个展览场地被分成 $N$ 个展区，每个展区有着不同的艺术品。

展区和展区之间有美丽的连廊相连，通过这些连廊，人们可以在不同的展区之间穿行。每个展区都被编号为 $1$ 到 $N$，共有 $N-1$ 条连廊将这 $N$ 个展区连接在一起。

小 $A$ 发现每个展区都有一个不同的主题，人们在每个展区停留时间会有差异。经过长期调研发现，人们在每个展区停留时间和与该展区连接的连廊的数量呈正相关。

我们可以理解为，如果编号为 $i$ 的展区与其连接的连廊的数量有 $C_i$ 个，那么人们会在这个展区停留 $C_i$ 个单位时间才会去下一个展区。

请你编程计算出，如果一个人想要从编号为 $U_i$ 的展区开始参观，到编号为 $V_i$ 的展区结束参观，那么他需要多少个单位的时间完成参观计划（$U_i, V_i$ 两个展区也在参观计划中）？

请注意，本题有 $M$ 组数据需要计算。

输入格式

第 $1$ 行读入 $2$ 个正整数 $N$ 和 $M$ 表示展区的数量和需要计算的数据组数。

接下来的 $N-1$ 行，每行两个正整数 $x, y$ 表示编号为 $x$ 和 $y$ 的两个展区用连廊直接相连。

接下来的 $M$ 行，每行两个正整数 $U_i, V_i$ 表示需要计算的第 $i$ 组数据的起止展区的编号。

输出格式

输出 $M$ 行，第 $i$ 行输出对于第 $i$ 组数据计算的结果。

样例

输入

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

输出

5
6
1

数据范围

对于 $30\%$ 的数据，保证 $n, m \le 1000$；

对于 $100\%$ 的数据，保证 $n, m \le 10^5$。