【问题描述】
众所周知，小y好奇心极强。
这次，他看到了一个n个节点的树，他突然想知道有多少个三元组(u, v, w)满足其两两不同且存在一条u到w路径和一条v到w路径满足两条路径之间没有公共边。
单单知道这个小y还不满足，他决定增加一些边，每加一条边他就想知道答案。

【输入格式】
输入的第一行为n，表示节点个数
接下来n-1行，每行两个数x，y表示一条边。
接下来一行一个数为q，表示加边的次数。
接下来q行，每行两个数x，y，表示加的一条边。

【输出格式】
q+1行，表示初始答案和每次加边后的答案。

输入样例

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

输出样例

6
18
24

Limitation

2s, 256MiB for each test case.
【数据范围与约定】
20%: n <= 10, q <= 10
50%: n <= 500, q <= 500
100%: n <= 100000, q <= 100000