Description

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.

Input

* 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.

Output

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

Sample Input

4 1
1 1
3 1
2 3
4 3
1 4

Sample Output

4.00

题意：n个村庄，m条已经修好的道路，接下来n行表示n个村庄的坐标（xi，yi），m行表示两个村庄（a，b）已经修好道路。求n个村庄互相连通需要修建的最短道路。

思路：最小生成树

Prim算法：

#include
  
   
#include
   
     #include
    
      #include
     
       #define INF 999999 #define M 1005 using namespace std; double map[M][M],len[M]; // 注意类型 int vis[M]; int x[M],y[M]; double dis(int i,int j) // 任意两个村庄的距离 { double k1,k2,k; k1=x[i]-x[j]; k2=y[i]-y[j]; k=sqrt(k1*k1+k2*k2); return k; } int main () { int n,m,a,b; int i,j; int temp; double sum; while(cin>>n>>m) { memset(map,0,sizeof(map)); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) cin>>x[i]>>y[i]; for(i=1;i<=n;i++) for(j=1;j
      
       >a>>b; map[a][b]=map[b][a]=0; // 巧妙处理。若已经修好道路，则长度赋值为0. } for(i=1;i<=n;i++) len[i]=map[1][i]; vis[1]=1; sum=0.0; for(i=1;i
       
        map[temp][j]) len[j]=map[temp][j]; } } printf("%.2lf\n",sum); } return 0; }