题目描述

给定一个连通简单图（任意两个节点之间至多有一条边），该图有 $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$ 行，每行一个整数，表示询问节点之间的简单路径数量。按照输入中出现的顺序输出每个询问的答案。

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

3
3
3
3
3
4

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
4
1

提示

翻译由 DeepSeek V3.2 完成