[USACO Dec07]建造路径

成绩 0 开启时间 2013年01月18日 星期五 09:40
折扣 0.8 折扣时间 2013年01月18日 星期五 09:40
允许迟交 是 关闭时间 2013年01月18日 星期五 09:40
输入文件 roads.in 输出文件 roads.out

译 by CmYkRgB123

描述

Farmer John 刚刚得到了几个新农场！他想把这几个农场用路连接起来，这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中，每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路，使他的农场连在一起。

输入

* 第 1 行: 两个整数: N , M
* 第 2..N+1 行: 两个整数 Xi , Yi
* 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。

输出

* 第 1 行: 额外的路的最少长度，保留2小数。 请使用 64 位的浮点数。

样例输入

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

样例输出

 4.00