Spanning Tree + DSU
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 (1 ≤ n ≤ 5000) of cities in Byteland. Each of the next n lines contains two integers
yi - the coordinates of i-th city (-10000 ≤
yi ≤ 10000). No two cities are located in one point.
Print the least total roads length. Print the answer with the accuracy no less than
6 1 1 7 1 2 2 6 2 1 3 7 3