Manthan, Codefest 17 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

graphs

trees

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Harry Vs Voldemort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter destroying all of Voldemort's Horcruxes, Harry and Voldemort are up for the final battle. They each cast spells from their wands and the spells collide.

The battle scene is Hogwarts, which can be represented in the form of a tree. There are, in total, *n* places in Hogwarts joined using *n* - 1 undirected roads.

Ron, who was viewing this battle between Harry and Voldemort, wondered how many triplets of places (*u*, *v*, *w*) are there such that if Harry is standing at place *u* and Voldemort is standing at place *v*, their spells collide at a place *w*. This is possible for a triplet only when *u*, *v* and *w* are distinct, and there exist paths from *u* to *w* and from *v* to *w* which do not pass through the same roads.

Now, due to the battle havoc, new paths are being added all the time. You have to tell Ron the answer after each addition.

Formally, you are given a tree with *n* vertices and *n* - 1 edges. *q* new edges are being added between the nodes of the tree. After each addition you need to tell the number of triplets (*u*, *v*, *w*) such that *u*, *v* and *w* are distinct and there exist two paths, one between *u* and *w*, another between *v* and *w* such that these paths do not have an edge in common.

Input

First line contains an integer *n* (1 ≤ *n* ≤ 10^{5}), the number of places in Hogwarts.

Each of the next *n* - 1 lines contains two space separated integers *u* and *v* (1 ≤ *u*, *v* ≤ *n*) indicating a road between places *u* and *v*. It is guaranteed that the given roads form a connected tree.

Next line contains a single integer *q* (1 ≤ *q* ≤ 10^{5}), the number of new edges being added.

Each of the next *q* lines contains two space separated integers *u* and *v* (1 ≤ *u*, *v* ≤ *n*) representing the new road being added.

Note that it is possible that a newly added road connects places that were connected by a road before. Also, a newly added road may connect a place to itself.

Output

In the first line print the value for the number of triplets before any changes occurred.

After that print *q* lines, a single integer *ans*_{i} in each line containing the value for the number of triplets after *i*-th edge addition.

Examples

Input

3

1 2

2 3

1

2 3

Output

2

4

Input

4

1 2

2 3

2 4

2

1 4

3 4

Output

6

18

24

Input

5

1 2

2 3

3 4

4 5

1

1 5

Output

20

60

Note

In the first sample case, for the initial tree, we have (1, 3, 2) and (3, 1, 2) as the only possible triplets (*u*, *v*, *w*).

After addition of edge from 2 to 3, we have (1, 3, 2), (3, 1, 2), (1, 2, 3) and (2, 1, 3) as the possible triplets.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 04:00:57 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|