Farmer John mua trang trại mới! Muốn đường để từ bất kỳ đến bất kỳ khác qua dãy đường; vài nơi đã nối.

$N$ $(1 \le N \le 1,000)$ trại số $1..N$ ở ($X_i$, $Y_i$), $(0 \le X_i \le 1,000,000; 0 \le Y_i \le 1,000,000)$. Cho $M$ đường sẵn $(1 \le M \le 1,000)$ bằng cặp trại. Tìm tổng dài bổ sung nhỏ nhất nối hết.

Dữ liệu vào

Đọc đầu vào chuẩn.

• Dòng $1$: số nguyên $N$, $M$ cách bởi dấu cách.

• Dòng $2..N+1$: số nguyên $X_i$, $Y_i$ cách bởi dấu cách.

• Dòng $N+2..N+M+2$: số nguyên $i$, $j$ cách bởi dấu cách, trại $i$, $j$ đã nối đường.

Dữ liệu ra

Ghi đầu ra chuẩn.

• Dòng $1$: dài bổ sung nhỏ nhất, hai chữ số thập phân không làm tròn. Tính khoảng cách bằng dấu phẩy động $64$ bit.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4.00

Ghi chú

Bốn trại ở $(1,1)$, $(3,1)$, $(2,3)$, $(4,3)$; $1$, $4$ đã nối.

Nối $1$, $2$ dài $2.00$, rồi $3$, $4$ dài $2.00$, tối ưu tổng $4.00$.

Tác giả bài toán: Richard Ho, 2007