#1328. 建设道路 Building Roads

建设道路 Building Roads

题目描述

给定 n(1n1,000)\red{n (1 ≤ n ≤ 1,000) } 个点的坐标,第 i\red{i} 个点的坐标为 (xi,yi)(0xi,yi1,000,000)\red{(x_i,y_i ) (0 ≤ x_i , y_i ≤ 1,000,000 ) },这 n\red{n} 个点编号为 1\red{1}n\red{n}。给定 m(1m1,000)\red{m (1 ≤ m ≤ 1,000) } 条边,第 i\red{i} 条边连接第 ui\red{u_i} 个点和第 vi\red{v_i} 个点。

现在要求你添加一些边,并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

第一行两个整数 n,m\red{n,m} 代表点数与边数。

接下来 n\red{n} 行每行两个整数 xi,yi\red{x_i,y_i} 代表第 i\red{i} 个点的坐标。

接下来 m\red{m} 行每行两个整数 ui,vi\red{u_i,v_i} 代表第 i\red{i} 条边连接第 ui\red{u_i} 个点和第 vi\red{v_i} 个点。

输出格式

一行一个实数代表添加的边的最小长度,要求保留两位小数,为了避免误差, 请用 64\red{64} 位实型变量进行计算。

样例

输入样例

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

输出样例

4.00