Farmer John kaufte neue Farmen! Er möchte Straßen, über deren Folge jede Farm jede andere erreicht; einige sind schon verbunden.

$N$ $(1 \le N \le 1,000)$ Farmen mit Nummern $1..N$ liegen bei ($X_i$, $Y_i$), $(0 \le X_i \le 1,000,000; 0 \le Y_i \le 1,000,000)$. $M$ bestehende Straßen $(1 \le M \le 1,000)$ sind Paare. Bestimme minimale zusätzliche Gesamtlänge zur Verbindung aller.

Eingabe

Lies Standardeingabe.

• Zeile $1$: ganze Zahlen $N$, $M$ mit Leerzeichen.

• Zeilen $2..N+1$: ganze Zahlen $X_i$, $Y_i$ mit Leerzeichen.

• Zeilen $N+2..N+M+2$: ganze Zahlen $i$, $j$ mit Leerzeichen; Farmen $i$, $j$ bereits verbunden.

Ausgabe

Schreibe Standardausgabe.

• Zeile $1$: minimale zusätzliche Länge, zwei Nachkommastellen ohne Rundung. Entfernungen mit $64$-Bit-Gleitkommazahlen berechnen.

Beispiele

Eingabe 1

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

Ausgabe 1

4.00

Hinweis

Vier Farmen bei $(1,1)$, $(3,1)$, $(2,3)$, $(4,3)$; $1$, $4$ verbunden.

$1$, $2$ mit $2.00$ verbinden, dann $3$, $4$ mit $2.00$, optimal zusammen $4.00$.

Aufgabenautor: Richard Ho, 2007