This is an arranged version of No.386 Greedy Lord.

Problem Statement

There are $N$ villages in a certain country.
The villages are connected to one another by $N-1$ roads, and one can travel freely between them.

To increase tax revenue, the lord of this country decided to set up a checkpoint in each village and impose tariffs on the peddlers passing through.
Each time a peddler passes through a village, they must pay $$ 関税が施行されてから今までにその村を通った行商人の数 + 1 $$ units of money, that is, the number of peddlers who have passed through that village since the tariffs took effect, plus 1.
Higher demand means a higher price; that's just how the economy works, isn't it?

It is known that, since the tariffs took effect, $Q$ peddlers have each traveled from village $A_i$ to village $B_i$ along the roads by the shortest path.
Output the total amount of tariffs the country will receive.

Note that a peddler must pay tariffs not only at the checkpoints of the villages along the way, but also at the checkpoints of village $A_i$ and village $B_i$.

Input

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$Q$
$A_1$ $B_1$
$\vdots$
$A_Q$ $B_Q$

All input values are integers.
Line $1$ contains the number of villages $N$, and the following $N-1$ lines give the villages connected by each road.
The $i$-th road connects village $u_i$ and village $v_i$.
Line $N+1$ contains the number of peddlers $Q$.
Each of the following $Q$ lines gives the starting village $A_i$ and the final destination village $B_i$ of the $i$-th peddler.

The input also satisfies the following constraints.
$2 \leq N \leq 10^5$
$1 \leq u_i, v_i \leq N$
$u_i \neq v_i$
$1 \leq Q \leq 10^5$
$1 \leq A_i, B_i \leq N$
$A_i \neq B_i$

Output

Output the total amount of tariffs on one line. Note that the answer may not fit in a 32-bit integer.

Sample

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

15

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

75