Connect the Campus

Time limit1sMemory limit128 MB

Summary

Given N points in the plane and some already-built zero-cost edges, add edges connecting all points at minimum total Euclidean length.

Level: Medium6 of 10
Topics: Minimum spanning tree, Union-find, Graph, Geometry
Solved: No attempts yet

Problem

Many new buildings are under construction on the campus of the University of Polkaroo. The university wants every building to be connected to every other building — directly or indirectly — through a campus network of communication cables.

Each building is a point in the plane given by an $x$ -coordinate and a $y$ -coordinate. Each communication cable connects exactly two buildings along the straight line segment between them, and information travels along a cable in both directions. Cables may cross one another freely, but they are joined only at their endpoints (the buildings).

The campus map shows the locations of all buildings and all existing communication cables. You may not change the existing cables. Decide where to install new cables so that all buildings become connected, while minimizing the total length of new cable used.

Input

The input describes a single test case. The first line contains the number of buildings $N$ $(1 \le N \le 750)$ . The buildings are labelled from $1$ to $N$ . Each of the next $N$ lines gives the $x$ - and $y$ -coordinates of one building. These coordinates are integers whose absolute values are at most $10\,000$ , and no two buildings share the same point.

The next line contains the number of existing cables $M$ $(0 \le M \le 1000)$ , followed by $M$ lines. Each of those lines contains two integers: the numbers of the two buildings that the existing cable directly connects. At most one cable directly connects any given pair of buildings.

Output

Print, on a single line, the minimum possible total length of the new cables, rounded to two decimal places.

Examples3

Example 1

Input

Expected output

4.41

Example 2
Input
```
1
0 0
0
```
Expected output
```
0.00
```
Example 3
Input
```
2
0 0
3 4
0
```
Expected output
```
5.00
```