اشترى Farmer John مزارع جديدة! يريد طرقًا للانتقال من أي مزرعة لأخرى بسلسلة طرق؛ بعض المزارع مرتبط بالفعل.

$N$ $(1 \le N \le 1,000)$ مزارع مرقمة $1..N$ في ($X_i$, $Y_i$)، $(0 \le X_i \le 1,000,000; 0 \le Y_i \le 1,000,000)$. تعطى $M$ طرق قائمة $(1 \le M \le 1,000)$ كأزواج. أوجد أقل مجموع أطوال إضافية لربط الجميع.

الإدخال

اقرأ الإدخال القياسي.

• السطر $1$: الصحيحان $N$ و$M$ بفراغ.

• الأسطر $2..N+1$: الصحيحان $X_i$ و$Y_i$ بفراغ.

• الأسطر $N+2..N+M+2$: الصحيحان $i$ و$j$ بفراغ؛ المزرعتان $i$ و$j$ مرتبطتان بطريق.

الإخراج

اكتب الإخراج القياسي.

• السطر $1$: أدنى طول إضافي بمنزلتين عشريتين دون تقريب. احسب المسافات بعائمة $64$ بت.

أمثلة

الإدخال 1

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

الإخراج 1

4.00

ملاحظة

أربع مزارع في $(1,1)$ و$(3,1)$ و$(2,3)$ و$(4,3)$؛ $1$ و$4$ مرتبطتان.

اربط $1$ و$2$ بطول $2.00$ ثم $3$ و$4$ بطول $2.00$، الأمثل مجموع $4.00$.

مؤلف المسألة: Richard Ho، 2007