Pairs of Paths

Description:

Input:

First line contains a single integer $$$n$$$ $$$(1 \leq n \leq 3 \cdot 10^5)$$$.

Next $$$n - 1$$$ lines describe the tree. Each line contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$ describing an edge between vertices $$$u$$$ and $$$v$$$.

Next line contains a single integer $$$m$$$ $$$(1 \leq m \leq 3 \cdot 10^5)$$$.

Next $$$m$$$ lines describe paths. Each line describes a path by it's two endpoints $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$. The given path is all the vertices on the shortest path from $$$u$$$ to $$$v$$$ (including $$$u$$$ and $$$v$$$).

Output:

Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

Sample Input:

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

Sample Output:

2

Sample Input:

1
3
1 1
1 1
1 1

Sample Output:

3

Sample Input:

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

Sample Output:

7

Note:

The tree in the first example and paths look like this. Pairs $$$(1,4)$$$ and $$$(3,4)$$$ intersect at one vertex.

In the second example all three paths contain the same single vertex, so all pairs $$$(1, 2)$$$, $$$(1, 3)$$$ and $$$(2, 3)$$$ intersect at one vertex.

The third example is the same as the first example with two additional paths. Pairs $$$(1,4)$$$, $$$(1,5)$$$, $$$(2,5)$$$, $$$(3,4)$$$, $$$(3,5)$$$, $$$(3,6)$$$ and $$$(5,6)$$$ intersect at one vertex.