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