დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
ფერმერმა ჯონმა შეიძინა ახალი ფერმები. მას უნდა დააკავშიროს ფერმები ერთმანეთთან გზებით ისე რომ ნებისმიერი ფერმიდან უნდა შეეძლოს გადაადგილდეს ნებისმიერ ფერმაში გზების რაღაც მიმდევრობის გავლით; მოცემული მომენტისათვის ზოგიერთ ფერმას უკვე აკავშირებს ერთმანეთთან გზა.
თითოეული 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 ერთეული.