import java.util.*;
import java.io.*;
class Main
{
static Pair[] array;
static Vector<Triple> vect;
static UF uf;
{
while(line != null)
{
array = new Pair[n];
vect = new Vector<Triple>();
uf = new UF(n);
double min = 0;
for(int i = 0; i < n; i++)
{
line = br.readLine();
int x
= Integer.
parseInt(sTok.
nextToken());
int y
= Integer.
parseInt(sTok.
nextToken());
array[i] = new Pair(x,y);
}
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++)
{
double d
= Math.
sqrt(Math.
pow(array
[i
].
x - array
[j
].
x,
2) + Math.
pow(array
[i
].
y - array
[j
].
y,
2));
vect.add(new Triple(d,i,j));
}
}
line = br.readLine();
for(int i = 0; i < m; i++)
{
line = br.readLine();
int a
= Integer.
parseInt(sTok.
nextToken());
int b
= Integer.
parseInt(sTok.
nextToken());
uf.union(a-1, b-1);
}
for(int i = 0; i < vect.size(); i++)
{
if(uf.size() == 1)
break;
Triple t = vect.get(i);
double w = t.w;
int v1 = t.v1;
int v2 = t.v2;
if(!uf.sameSet(v1, v2))
{
min += w;
uf.union(v1, v2);
}
}
str.
append(String.
format("%.2f\n", min
));
line = br.readLine();
}
out.write(str.toString());
out.flush();
}
}
class UF
{
int[] array;
int[] sizes;
int count;
UF(int n)
{
array = new int[n];
sizes = new int[n];
count = n;
for(int i = 0; i < n; i++)
{
array[i] = i;
sizes[i] = 1;
}
}
int size()
{
return count;
}
int findSet(int i)
{
if(array[i] == i)
return i;
else
return findSet(array[i]);
}
boolean sameSet(int i, int j)
{
return findSet(i) == findSet(j);
}
void union(int i, int j)
{
int a = findSet(i);
int b = findSet(j);
if(a != b)
{
if(sizes[a] > sizes[b])
{
array[b] = a;
sizes[a] += sizes[b];
}
else
{
array[a] = b;
sizes[b] += sizes[a];
}
count--;
}
}
}
class Pair
{
int x;
int y;
Pair(int a, int b)
{
x = a;
y = b;
}
}
class Triple implements Comparable<Triple>
{
double w;
int v1;
int v2;
Triple(double a, int b, int c)
{
w = a;
v1 = b;
v2 = c;
}
@Override
public int compareTo(Triple that) {
if(this.w > that.w)
return 1;
else if(this.w < that.w)
return -1;
else
return 0;
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5pby4qOwoKY2xhc3MgTWFpbgp7ICAgCiAgIHN0YXRpYyBQYWlyW10gYXJyYXk7CiAgIHN0YXRpYyBWZWN0b3I8VHJpcGxlPiB2ZWN0OwogICBzdGF0aWMgVUYgdWY7CiAgIAogICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB0aHJvd3MgSU9FeGNlcHRpb24KICAgewogICAgICBCdWZmZXJlZFJlYWRlciBiciA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CiAgICAgIAogICAgICBCdWZmZXJlZFdyaXRlciBvdXQgPSBuZXcgQnVmZmVyZWRXcml0ZXIobmV3IE91dHB1dFN0cmVhbVdyaXRlcihTeXN0ZW0ub3V0KSk7CiAgICAgIAogICAgICBTdHJpbmdCdWZmZXIgc3RyID0gbmV3IFN0cmluZ0J1ZmZlcigpOwogICAgICAKICAgICAgU3RyaW5nIGxpbmUgPSBici5yZWFkTGluZSgpOwogICAgICAKICAgICAgd2hpbGUobGluZSAhPSBudWxsKQogICAgICB7CiAgICAgICAgIGludCBuID0gSW50ZWdlci5wYXJzZUludChsaW5lKTsKICAgICAgICAgCiAgICAgICAgIGFycmF5ID0gbmV3IFBhaXJbbl07CiAgICAgICAgIAogICAgICAgICB2ZWN0ID0gbmV3IFZlY3RvcjxUcmlwbGU+KCk7CiAgICAgICAgIAogICAgICAgICB1ZiA9IG5ldyBVRihuKTsKICAgICAgICAgCiAgICAgICAgIGRvdWJsZSBtaW4gPSAwOwogICAgICAgICAKICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgewogICAgICAgICAgICBsaW5lID0gYnIucmVhZExpbmUoKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIFN0cmluZ1Rva2VuaXplciBzVG9rID0gbmV3IFN0cmluZ1Rva2VuaXplcihsaW5lKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCB4ID0gSW50ZWdlci5wYXJzZUludChzVG9rLm5leHRUb2tlbigpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCB5ID0gSW50ZWdlci5wYXJzZUludChzVG9rLm5leHRUb2tlbigpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGFycmF5W2ldID0gbmV3IFBhaXIoeCx5KTsKICAgICAgICAgfQogICAgICAgICAKICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgewogICAgICAgICAgICBmb3IoaW50IGogPSBpKzE7IGogPCBuOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgZG91YmxlIGQgPSBNYXRoLnNxcnQoTWF0aC5wb3coYXJyYXlbaV0ueCAtIGFycmF5W2pdLngsMikgKyBNYXRoLnBvdyhhcnJheVtpXS55IC0gYXJyYXlbal0ueSwyKSk7CiAgICAgICAgICAgIAogICAgICAgICAgICAgICB2ZWN0LmFkZChuZXcgVHJpcGxlKGQsaSxqKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgfQogICAgICAgICAKICAgICAgICAgQ29sbGVjdGlvbnMuc29ydCh2ZWN0KTsKICAgICAgICAgCiAgICAgICAgIGxpbmUgPSBici5yZWFkTGluZSgpOwogICAgICAgICAKICAgICAgICAgaW50IG0gPSBJbnRlZ2VyLnBhcnNlSW50KGxpbmUpOwogICAgICAgICAKICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG07IGkrKykKICAgICAgICAgewogICAgICAgICAgICBsaW5lID0gYnIucmVhZExpbmUoKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIFN0cmluZ1Rva2VuaXplciBzVG9rID0gbmV3IFN0cmluZ1Rva2VuaXplcihsaW5lKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCBhID0gSW50ZWdlci5wYXJzZUludChzVG9rLm5leHRUb2tlbigpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCBiID0gSW50ZWdlci5wYXJzZUludChzVG9rLm5leHRUb2tlbigpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIHVmLnVuaW9uKGEtMSwgYi0xKTsKICAgICAgICAgfQogICAgICAgICAKICAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IHZlY3Quc2l6ZSgpOyBpKyspCiAgICAgICAgIHsKICAgICAgICAgICAgaWYodWYuc2l6ZSgpID09IDEpCiAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAKICAgICAgICAgICAgVHJpcGxlIHQgPSB2ZWN0LmdldChpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGRvdWJsZSB3ID0gdC53OwogICAgICAgICAgICAKICAgICAgICAgICAgaW50IHYxID0gdC52MTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGludCB2MiA9IHQudjI7CiAgICAgICAgICAgIAogICAgICAgICAgICBpZighdWYuc2FtZVNldCh2MSwgdjIpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgIG1pbiArPSB3OwogICAgICAgICAgICAgICB1Zi51bmlvbih2MSwgdjIpOwogICAgICAgICAgICB9CiAgICAgICAgIH0KICAgICAgICAgCiAgICAgICAgIHN0ci5hcHBlbmQoU3RyaW5nLmZvcm1hdCgiJS4yZlxuIiwgbWluKSk7CiAgICAgICAgIAogICAgICAgICBsaW5lID0gYnIucmVhZExpbmUoKTsKICAgICAgfQogICAgICAKICAgICAgCiAgICAgIAogICAgICAKICAgICAgCiAgICAgIG91dC53cml0ZShzdHIudG9TdHJpbmcoKSk7CiAgICAgIAogICAgICBvdXQuZmx1c2goKTsKICAgfQp9CgpjbGFzcyBVRgp7CiAgIGludFtdIGFycmF5OwogICBpbnRbXSBzaXplczsKICAgaW50IGNvdW50OwogICAKICAgVUYoaW50IG4pCiAgIHsKICAgICAgYXJyYXkgPSBuZXcgaW50W25dOwogICAgICBzaXplcyA9IG5ldyBpbnRbbl07CiAgICAgIGNvdW50ID0gbjsKICAgICAgCiAgICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgIHsKICAgICAgICAgYXJyYXlbaV0gPSBpOwogICAgICAgICBzaXplc1tpXSA9IDE7CiAgICAgIH0KICAgfQogICAKICAgaW50IHNpemUoKQogICB7CiAgICAgIHJldHVybiBjb3VudDsKICAgfQogICAKICAgaW50IGZpbmRTZXQoaW50IGkpCiAgIHsKICAgICAgaWYoYXJyYXlbaV0gPT0gaSkKICAgICAgICAgcmV0dXJuIGk7CiAgICAgIGVsc2UKICAgICAgICAgcmV0dXJuIGZpbmRTZXQoYXJyYXlbaV0pOwogICB9CiAgIAogICBib29sZWFuIHNhbWVTZXQoaW50IGksIGludCBqKQogICB7CiAgICAgIHJldHVybiBmaW5kU2V0KGkpID09IGZpbmRTZXQoaik7CiAgIH0KICAgCiAgIHZvaWQgdW5pb24oaW50IGksIGludCBqKQogICB7CiAgICAgIGludCBhID0gZmluZFNldChpKTsKICAgICAgaW50IGIgPSBmaW5kU2V0KGopOwogICAgICAKICAgICAgaWYoYSAhPSBiKQogICAgICB7CiAgICAgICAgIGlmKHNpemVzW2FdID4gc2l6ZXNbYl0pCiAgICAgICAgIHsKICAgICAgICAgICAgYXJyYXlbYl0gPSBhOwogICAgICAgICAgICBzaXplc1thXSArPSBzaXplc1tiXTsKICAgICAgICAgfQogICAgICAgICBlbHNlCiAgICAgICAgIHsKICAgICAgICAgICAgYXJyYXlbYV0gPSBiOwogICAgICAgICAgICBzaXplc1tiXSArPSBzaXplc1thXTsKICAgICAgICAgfQogICAgICAgICAKICAgICAgICAgY291bnQtLTsKICAgICAgfQogICB9Cn0KCmNsYXNzIFBhaXIKewogICBpbnQgeDsKICAgaW50IHk7CiAgIAogICBQYWlyKGludCBhLCBpbnQgYikKICAgewogICAgICB4ID0gYTsKICAgICAgeSA9IGI7CiAgIH0KfQoKY2xhc3MgVHJpcGxlIGltcGxlbWVudHMgQ29tcGFyYWJsZTxUcmlwbGU+CnsKICAgZG91YmxlIHc7CiAgIGludCB2MTsKICAgaW50IHYyOwogICAKICAgVHJpcGxlKGRvdWJsZSBhLCBpbnQgYiwgaW50IGMpCiAgIHsKICAgICAgdyA9IGE7CiAgICAgIHYxID0gYjsKICAgICAgdjIgPSBjOwogICB9CgogICBAT3ZlcnJpZGUKICAgcHVibGljIGludCBjb21wYXJlVG8oVHJpcGxlIHRoYXQpIHsKICAgICAgaWYodGhpcy53ID4gdGhhdC53KQogICAgICAgICByZXR1cm4gMTsKICAgICAgZWxzZSBpZih0aGlzLncgPCB0aGF0LncpCiAgICAgICAgIHJldHVybiAtMTsKICAgICAgZWxzZQogICAgICAgICByZXR1cm4gMDsKICAgfQp9
NgowIDAKMjAwIDUwCjEwMCAyMDAKNTAgMzAwCjMwMCAyMDAKMzAwIDMwMAoyCjMgNAo1IDYKCjYKMCAwCjIwMCA1MAoxMDAgMjAwCjUwIDMwMAozMDAgMjAwCjMwMCAzMDAKNQoxIDIKMiAzCjMgNAo0IDUKNSA2
6
0 0
200 50
100 200
50 300
300 200
300 300
2
3 4
5 6
6
0 0
200 50
100 200
50 300
300 200
300 300
5
1 2
2 3
3 4
4 5
5 6