ფერმერმა ჯონმა შეიძინა ახალი ფერმები. მას უნდა დააკავშიროს ფერმები ერთმანეთთან გზებით ისე რომ ნებისმიერი ფერმიდან უნდა შეეძლოს გადაადგილდეს ნებისმიერ ფერმაში გზების რაღაც მიმდევრობის გავლით; მოცემული მომენტისათვის ზოგიერთ ფერმას უკვე აკავშირებს ერთმანეთთან გზა.

თითოეული N (1 <= N <= 1,000) ფერმიდან (ფერმები გადანომრილია 1..N), წარმოდგენილია გეგმაზე კოორდინატებით (X_i, Y_i) (0 <= X_i <=1,000,000; 0 <= Y_i <= 1,000,000). მოცემულია უკვე არსებული M გზა(1 <= M <= 1,000) როგორც წყვილები იმ ფერმებისა, რომლებსაც ეს გზა აერთებს. დაეხმარეთ ფერმერ ჯონს იპოვოს უმცირესი სიგრძე გზისა, რომელიც მან უნდა გააკეთოს, რათა ყველა თავის ფერმა დაკავშირებული იყოს ერთმანეთთან.

შეტანის ფორმატი:

* ხაზი 1: ორი ჰარით გაყოფილი მთელი: N და M

* ხაზები 2..N+1: ორი ჰარით გაყოფილი მთელი: X_i და Y_i

* ხაზები N+2..N+M+2: ორი ჰარით გაყოფილი მთელი: i და j, უჩვენებს, რომ უკვე არსებობს გზა, რომელიც აერთებს i და j ფერმას.

გამოტანის ფორმატი:

* ხაზი 1: უმცირესი სიგრძე, რომელიც საჭიროა რომ ყველა ფერმა იყოს ერთმანეთთან დაკავშირებული. პასუხი გამოიტანეთ მძიმის შემდგომი ორი ციფრის დამრგვალების გარეშე. დარწმუდით რომ გამოთვლას აწარმოებთ 64-ბიტიან მცურავ ნიშნულიან რიცხვებზე.

მაგალითები

შესატანი მონაცემები
4 1
1 1
3 1
2 3
4 3
1 4
                  დაკოპირება

გამოსატანი მონაცემები
4.00
                  დაკოპირება

შენიშვნა

შეტანის დეტალები:

მოცემულია ოთხი ფერმა (1,1), (3,1), (2,3) და (4,3). ფერმა 1-სა და 4-სა ორის უკვე არსებობს გზა.

გამოტანის დეტალები:

შევაერთოთ ფერმა 1 და 2. ამ გზის სიგრძე იქნება 2.00 ერთეული, შემდეგ შევაერთოთ ფერმა 3 და 4. ამ გზის სიგრძეც გამოვა 2.00 ერთეული. ეს არის საუკეთესო ვარიანტი რაც ჩვენ შეგვიძლია გავაკეთოთ. გზის საერთო სიგრძე გამოდის 4.00 ერთეული.