A network of size $N$ contains $N$ computers connected by $N-1$ cables, so that there is exactly $1$ path between any pair of computers.

The transmission cost between $2$ computers is equal to the square of the number of cables on the path connecting the $2$ computers.

The transmission cost of a network is equal to the sum of the transmission cost between all unordered pair of computers.

Given network $A$ with $N$ computers and network $B$ with $M$ computers, the administrator wants to create a new network $C$, by adding exactly one cable connecting one computer in $A$ and one computer in $B$.

Your task is to minimize the transmission cost of the new network $C$.

-----Input-----
 - The first line contains an integer $N$ - the number of computers in the network $A$ ($1 \leq N \leq 50000$).
 - In the next $N-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $A$ ($1 \leq u,v \leq N$).
 - The next line contains an integer $M$ - the number of computers in the network $B$ ($1 \leq M \leq 50000$).
 - In the next $M-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $B$ ($1 \leq u,v \leq M$).

It is guaranteed that each network is a tree.

-----Output-----
Write in one line the minimum transmission cost of the resulting network $C$.

-----Sample clarification-----
In the first sample below, connecting computer $2$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

In the second sample below, connecting computer $4$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

-----Examples-----
Sample Input:
3
1 2
2 3
4
1 2
1 3
1 4
Sample Output:
96

Source: kattis | Difficulty: HARD


Solutions: