Farmer John vient d’acheter de nouvelles fermes ! Il veut des routes reliant toute ferme à toute autre par une succession ; certaines sont déjà reliées.

$N$ $(1 \le N \le 1,000)$ fermes numérotées $1..N$ ont positions ($X_i$, $Y_i$), $(0 \le X_i \le 1,000,000; 0 \le Y_i \le 1,000,000)$. Les $M$ routes existantes $(1 \le M \le 1,000)$ sont des paires de fermes. Trouvez la longueur totale minimale à ajouter pour tout relier.

Entrée

Lisez l’entrée standard.

• Ligne $1$ : entiers $N$, $M$ séparés par un espace.

• Lignes $2..N+1$ : entiers $X_i$, $Y_i$ séparés par un espace.

• Lignes $N+2..N+M+2$ : entiers $i$, $j$ séparés par un espace, fermes $i$, $j$ déjà reliées.

Sortie

Écrivez la sortie standard.

• Ligne $1$ : longueur supplémentaire minimale avec deux décimales sans arrondi. Calculez les distances en flottants $64$ bits.

Exemples

Entrée 1

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

Sortie 1

4.00

Remarque

Quatre fermes en $(1,1)$, $(3,1)$, $(2,3)$, $(4,3)$ ; $1$, $4$ reliées.

Reliez $1$, $2$ par $2.00$, puis $3$, $4$ par $2.00$, optimal total $4.00$.

Auteur du problème : Richard Ho, 2007