题目描述

某航空公司在 $n$ 座城市之间开通了 $n-1$ 条双向航线，现有航线构成一棵树。每条航线的长度均为 $1$。两座城市之间的距离，定义为从一座城市到达另一座城市所需经过的最少航线数。

公司提出了 $q$ 个增补计划。每个计划指定两座不同的城市 $x,y$，拟在它们之间增加一条长度为 $1$ 的双向航线。

请对每个计划求出：新增这条航线后，有多少对不同城市之间的距离会严格减小？同一对城市只统计一次，即只统计 $1\le s<t\le n$ 的城市对 $(s,t)$。

各个计划相互独立，均以原有的 $n-1$ 条航线为基础，不会保留其他计划新增的航线。即使 $x,y$ 之间已有航线，该计划仍然合法。

输入格式

第一行包含两个整数 $n,q$，分别表示城市数和增补计划数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示城市 $u,v$ 之间有一条原有的双向航线。

接下来 $q$ 行，每行包含两个整数 $x,y$，表示一个增补计划。

输出格式

按输入顺序输出 $q$ 行，每行包含一个整数，表示对应计划使距离严格减小的城市对数。

样例输入 1

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

样例输出 1

1
2

样例 1 解释

增加航线 $(1,4)$ 后，只有城市对 $(1,4)$ 的距离减小，由 $3$ 变为 $1$。增加航线 $(1,3)$ 后，城市对 $(1,3)$ 和 $(1,4)$ 的距离分别由 $2,3$ 变为 $1,2$。

样例输入 2

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

样例输出 2

1
0

样例 2 解释

第一个计划使城市 $2,3$ 之间的距离由 $2$ 变为 $1$，其他城市对的距离不变。第二个计划新增的航线连接城市 $1,2$，这两座城市之间已有航线，因此所有城市对的距离均不变。

数据范围与子任务

对于所有测试数据，保证$2\le n\le10^6$，$1\le q\le10^5$，城市编号在 $1$ 到 $n$ 之间，$x\ne y$。保证原航线构成树，且所有询问中 $x$ 到 $y$ 的原树距离之和不超过 $10^7$。

每个子任务内的正式测试全部通过，才获得该子任务的分数。