No submission language available for this problem.

Background

Special for beginners, ^_^

Description

蒂莫菲的花园里种着一棵苹果树，是一棵有 $n$ 个顶点的有根树，根位于顶点 $1$ （顶点的编号从 $1$ 到 $n$ ）。树是一个连通的图形，没有循环和多条边。

这棵树很不寻常——它的根向上生长。不过，对于程序员的树来说，这很正常。

这棵苹果树还很年轻，所以上面只能长出两个苹果。苹果会生长在某些顶点上（这些顶点可能是相同的）。苹果长出来后，蒂莫菲开始摇晃苹果树，直到苹果掉下来。每次蒂莫菲摇动苹果树时，每个苹果都会发生以下情况：

假设苹果现在位于顶点 $u$ 。

• 如果顶点 $u$ 有一个子顶点，苹果就会移动到该顶点（如果有多个这样的顶点，苹果可以移动到其中任何一个顶点）。
• 否则，苹果就会从树上掉下来。

可以证明，经过有限的时间后，两个苹果都会从树上掉下来。

提莫菲有 $q$ 种假设苹果可以在哪些顶点生长的情况。他假设苹果可以在顶点 $x$ 和 $y$ 上生长，并想知道苹果可以从树上掉落的顶点对数（ $a$ , $b$ ）

其中 $a$ 是苹果从顶点 $x$ 掉落的顶点，$b$ 是苹果从顶点 $y$ 掉落的顶点。请帮助他完成这项工作。

Format

Input

第一行包含整数 $n$ ( $2 \leq n \leq 2 \cdot 10^5$ ) - 树中顶点的数量。

然后有 $n - 1$ 行描述树。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ （ $1 \leq u_i, v_i \leq n$ 、 $u_i \ne v_i$ ）。( $1 \leq u_i, v_i \leq n$ , $u_i \ne v_i$ )——树中的边。

下一行包含一个整数 $q$ （ $1 \leq q \leq 2 \cdot 10^5$ ）--提莫菲的假设数。

接下来的每行 $q$ 包含两个整数 $x_i$ 和 $y_i$ ( $1 \leq x_i, y_i \leq n$ ) - 假设 $i$ 中苹果生长的顶点。

Output

对于蒂莫菲的每一个假设，如果假设成立，请在另一行输出苹果可以从树上掉落的有序顶点对的数量。

Samples

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

2
2
1
4

3
1 2
1 3
3
1 1
2 3
3 1

4
1
2

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

1
2

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

1
4
2

Limitation

样例1：

若在 (3,4), 掉下来组合为 (4,4), (4,5) 共 2 种

若在 (5,1), 掉下来组合为 (4,5), (5,5) 共 2 种

若在 (4,4), 掉下来组合为 (4,4) 共 1 种

若在 (1,3), 掉下来组合为 (4,4), (4,5), (5,4), (5,5) 共 4 种

1s, 1024KiB for each test case.