Recalling your youth, you remember spending long hours playing Sim City 1. In this game you had the privilege and honor of building a city to your exact specifications and desires. You could build airports, sports stadiums, schools, industrial factories, residential homes, and more. It was your job to keep the citizens of your metropolis happy and prosperous.

Unfortunately, to pay for all of these construction projects, you had to tax your people. Even in the virtual world, people hate taxes and want you to spend their hard-earned income wisely. In particular, they would demand that you build roads to connect every building, but in the most cost efficient way.

Now that you have had some training in graph algorithms, you can easily tackle the problem of connecting every building in your city to every other building using the minimum amount of road. Given the coordinates of the buildings in a city, you are to connect them such that all buildings are reachable by road, while minimizing the amount of pavement you must lay down to make the connections.

## Input¶

The input is a series of building locations specified by sets of point locations. The first line of a set denotes the number of points `N`, followed by `N` pair of points `X Y`. The end of the input is denoted when `N` = 0. N will never be larger than `100`.

### Example Input¶

```3
1.0 1.0
2.0 2.0
2.0 4.0
0
```

Note: You can assume you can connect buildings directly with a straight-line path (unlike in the video game).

## Output¶

For each set of building locations, output the minimum total amount of road that must be constructed to connect all the buildings to two decimal places.

### Example Output¶

```3.41
```

#### Algorithmic Complexity¶

For each input test case, your solution should have the following targets:

 Time Complexity `O(VlogV)`, where `V` is the number of vertices in the graph. Space Complexity `O(V+E)`, where `V` is the number of vertices and `E` is the number of edges in the graph.

Your solution may be below the targets, but it should not exceed them.

## Submission¶

```\$ cd path/to/cse-30872-fa21-assignments     # Go to assignments repository
\$ git checkout master                       # Make sure we are on master
\$ git pull --rebase                         # Pull any changes from GitHub

\$ git checkout -b challenge17               # Create and checkout challenge17 branch

\$ \$EDITOR challenge17/program.py            # Edit your code

\$ git commit -m "challenge17: done"         # Commit your changes

\$ git push -u origin challenge17            # Send changes to GitHub
```

To check your code, you can use the `.scripts/check.py` script or curl:

```\$ .scripts/check.py
Checking challenge17 program.py ...
Result Success
Time 0.02
Score 6.00 / 6.00

\$ curl -F source=@challenge17/program.py https://dredd.h4x0r.space/code/cse-30872-fa21/challenge17
{"result": "Success", "score": 6, "time": 0.01631760597229004}
```

#### Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 09 TA List.

1. I was actually more of a fan of Sim Ant