Building Roads

题目描述

给定 \(n\) 个点的坐标，第 \(i\) 个点位于 \((x_i, y_i)\)，点编号为 \(1 \dots n\)。又给定 \(m\) 条已存在的无向边，第 \(i\) 条边连接点 \(u_i\) 与 \(v_i\)。 现在允许你再新建若干条边，使得图变为连通图（任意两点可达）。请计算：为达成连通所需新建边的总长度最小值。

边长（边权）定义： 任意两点 \(a=(x_a,y_a)\), \(b=(x_b,y_b)\) 之间的新建边的长度为它们的欧几里得距离： \( \mathrm{dist}(a,b)=\sqrt{(x_a-x_b)^2+(y_a-y_b)^2}. \) 已给定的 \(m\) 条边视为"已建成且免费"，不计入新建成本（等价于这些点对已连通，费用为 0）。

输入格式

• 第一行：两个整数 \(n, m\) —— 点数与已存在边数。
• 接下来 \(n\) 行：第 \(i\) 行给出两个整数 \(x_i, y_i\),表示点的坐标。
• 接下来 \(m\) 行：每行两个整数 \(u_i, v_i\)，表示一条已存在的无向边。

输出格式

输出一个实数，表示为使整张图连通所需新建边的最小总长度；保留两位小数输出。为避免精度误差，请使用 64 位浮点类型进行计算。

样例

输入

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

输出

4.00

说明/提示

• 数据范围：\(1 \le n,m \le 1000\), \(1 \le x_i,y_i \le 10^6\), \(1 \le u_i,v_i \le n\)。