Problem1530--建设道路

1530: 建设道路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 104  Solved: 25
[Submit] [Status] [Web Board] [Creator:]

Description

       有个城市编号为{1,2,...,n}。现在要给这个城市之间建设一些道路,使得这些城市能够通过建设的这些道路相互到达。

在城市i和城市j之间建设道路的花费为

计算最少需要多少费用才能使这些城市能相互到达。



Input

第一行输入一个整数{n(1\le n\le 10^5)}
接下来行每行两个整数{x_{i},y_{i}(1\le x_i,y_i\le 10^5)}

Output

输出一个整数表示最小的费用。

Sample Input

3
1 4
2 8
3 6

Sample Output

252

Source/Category

简单