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$.
The first line contains an integer $N$ - the number of computers in the network $A$ ($1 \leq N \leq 50\, 000$).
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 50\, 000$).
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.
Write in one line the minimum transmission cost of the resulting network $C$.
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.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 2 2 3 4 1 2 1 3 1 4 |
96 |
Sample Input 2 | Sample Output 2 |
---|---|
7 1 2 2 3 2 4 4 5 5 6 5 7 5 1 2 1 3 1 4 1 5 |
551 |