Spanning Tree + DSU

Unification Day

Byteland has n cities, but no one road. The king of the country, Waldemar de Bear, decided to remedy this situation, he wants to connect some cities with roads so that along these roads it will be possible to reach any city from any other city. When construction will be completed, the king plans to celebrate the Unification Day.

Unfortunately, the treasury in Byteland is almost empty, so the king needs to save money and minimize the total length of constructed roads.


The first line contains the number n (1n5000) of cities in Byteland. Each of the next n lines contains two integers xi, yi - the coordinates of i-th city (-10000xi, yi10000). No two cities are located in one point.


Print the least total roads length. Print the answer with the accuracy no less than 10-3.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 1
7 1
2 2
6 2
1 3
7 3
Output example #1