Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.Each of the *N* (1 ≤ *N* ≤ 1,000) farms (conveniently numbered 1..*N*) is represented by a position (*X*_{i}, *Y*_{i}) on the plane (0 ≤ *X*_{i }≤ 1,000,000; 0 ≤ *Y*_{i }≤ 1,000,000). Given the preexisting *M* roads (1 ≤ *M* ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

* Line 1: Two space-separated integers: *N* and *M*
* Lines 2..*N*+1: Two space-separated integers: *X*_{i }and *Y*_{i }
* Lines *N*+2..*N*+*M*+2: Two space-separated integers: *i* and *j*, indicating that there is already a road connecting the farm *i* and farm *j*.

提交代码