Timofey 的花园里长着一棵苹果树;它是一棵由 $$$n$$$ 个顶点组成的有根树,根位于顶点 $$$1$$$(顶点编号从 $$$1$$$ 到 $$$n$$$)。树是一个没有循环和多条边的连通图。
这棵树非常不寻常——它的根部向上生长。不过,对于程序员的树来说,这是很正常的。
苹果树还很年轻,所以上面只会长两个苹果。苹果会在某些顶点生长(这些顶点可能是相同的)。苹果长大后,蒂莫菲开始摇晃苹果树,直到苹果掉落。每次蒂莫菲摇动苹果树时,每个苹果都会发生以下情况:
让苹果现在位于顶点$$$u$$$。
- 如果顶点 $$$u$$$ 有一个子顶点,则苹果会移动到该顶点(如果有多个这样的顶点,则苹果可以移动到其中任何一个)。
- 否则,苹果会从树上掉下来。
可以证明,在有限的时间后,两个苹果都会从树上掉下来。
Timofey 有 $$$q$$$ 假设,其中苹果的顶点可以生长。他假设苹果可以在顶点 $$$x$$$ 和 $$$y$$$ 中生长,并且想知道苹果可以从树上掉下来的顶点对 ($$$a$$$, $$$b$$$) 的数量,其中 $$$a$$$ - 顶点 $$$x$$$ 中的苹果将从中掉落的顶点,$$$b$$$ - 从顶点中掉落苹果的顶点顶点$$$y$$$将会掉落。帮助他做到这一点。
输入
第一行包含整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含整数 $$$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$$$) — 树中的边。
下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — Timofey 假设的数量。
接下来的 $$$q$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) - 对于假设 $$$i$$$,苹果将在其上生长的假定顶点。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。同样,保证$$$q$$$之和不超过$$$2 \cdot 10^5$$$。
输出
对于每个 Timofey 的假设,如果假设在单独的行上为真,则输出苹果可以从树上掉落的有序顶点对的数量。
示例
输入 #1
2 5 1 2 3 4 5 3 3 2 4 3 4 5 1 4 4 1 3 3 1 2 1 3 3 1 1 2 3 3 1
输出 #1
2 2 1 4 4 1 2
输入 #2
2 5 5 1 1 2 2 3 4 3 2 5 5 5 1 5 3 2 5 3 2 1 4 2 3 4 3 2 1 4 2
输出 #2
1 2 1 4 2
注意
在第一个示例中:
- 对于第一个假设,苹果可以从树上掉下来的两个可能的顶点对:$$$(4, 4), (5, 4)$$$。
- 对于第二个假设,也有两对:$$$(5, 4), (5, 5)$$$。
- 对于第三个假设,只有一对:$$$(4, 4)$$$。
- 对于第四个假设,有 $$$4$$$ 对:$$$(4, 4), (4, 5), (5, 4), (5, 5)$$$。
第一个示例中的树。
对于第二个示例,苹果可以从 $$$4$$$ 可能的顶点对掉落:$$$(2, 3), (2, 2), (3, 2), (3, 3)$$$。对于第二个假设,只有一对可能的:$$$(2, 3)$$$。对于第三个假设,有两对:$$$(3, 2), (3, 3)$$$。