Description

众所周知，小y好奇心极强。

这次，他看到了一个 $n$ 个节点的树，他突然想知道有多少个三元组 $(u, v, w)$ 满足其两两不同且存在一条 $u$ 到 $w$ 路径和一条 $v$ 到 $w$ 路径满足两条路径之间没有公共边。

单单知道这个小 $y$ 还不满足，他决定增加一些边，每加一条边他就想知道答案。

Input Format

输入的第一行为 $n$ ，表示节点个数

接下来 $n-1$ 行，每行两个数 $x$，$y$表示一条边。

接下来一行一个数为 $q$ ，表示加边的次数。

接下来 $q$ 行，每行两个数 $x, y$，表示加的一条边。

Output Format

$q+1$行，表示初始答案和每次加边后的答案。

Sample

样例输入1

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

样例输出1

6
18
24

Hint

对于$20\%$的数据: $n \le 10, q \le 10$

对于$50\%$的数据: $n \le 500, q \le 500$

对于$100\%$的数据: $n \le 100000, q \le 100000$