Hide

Problem J
Joining Networks

A network of size N contains N computers connected by N1 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 (1N50000).

  • In the next N1 lines, each line contains two distinct integers u and v, representing a cable connecting computers u and v in network A (1u,vN).

  • The next line contains an integer M - the number of computers in the network B (1M50000).

  • In the next M1 lines, each line contains two distinct integers u and v, representing a cable connecting computers u and v in network B (1u,vM).

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.

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
Hide

Please log in to submit a solution to this problem

Log in