Highways

The island nation of Flatopia is perfectly flat, but its network of public highways is poor. The government has already built a number of highways connecting some of the towns, yet some towns still cannot be reached by highway. More highways must be built so that it is possible to drive between every pair of towns using only the highway system.

The towns are numbered from $1$ to $N$, and town $i$ is at Cartesian coordinates $(x_i, y_i)$. Each highway connects exactly two towns, runs in a straight line, and can be driven in both directions; its length equals the Euclidean distance between the two towns. Highways may cross one another, but a driver can only switch between two highways at a town that is an endpoint of both.

The government wants every town to be reachable from every other town while spending as little as possible. Because the terrain is flat, the cost of a highway is proportional to its length, so the cheapest system is the one that minimizes the total length of the newly built highways.

The first line contains a single integer $N$ ($1 \le N \le 750$), the number of towns.

Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10000$), the coordinates of town $i$ (for $i$ from $1$ to $N$). Every town has a unique location.

The next line contains a single integer $M$ ($0 \le M \le 1000$), the number of highways that have already been built. Each of the next $M$ lines contains two distinct town numbers that are already directly connected by a highway. Each pair of towns is joined by at most one existing highway.

Build new highways so that every town becomes reachable from every other town, using the existing and the new highways together, with the minimum possible total length of the new highways.

Because that minimum total length is a sum of Euclidean distances (a sum of square roots), report it as an integer: output a single integer equal to the sum of the squared lengths of the new highways, i.e. the sum of $(x_i - x_j)^2 + (y_i - y_j)^2$ over every new highway between towns $i$ and $j$ in the minimum-total-length system.

This value is uniquely determined even when several different systems achieve the minimum total length. If all towns are already connected and no new highway is needed, output $0$.