რამდენიმე კერძო კომპანიამ გადაწყვიტა გააერთიანოს მათ განკარგულებაში არსებული ქსელები, მაგრამ ეს არც ისე იოლი აღმოჩნდა. შექმნილი ქსელების პარამეტრები იმდენად განსხვავებულია ერთმანეთისაგან, რომ ყოველი ორი მათგანის გაერთიანება გარკვეულ დანახარჯს მოითხოვს და ეს დანახარჯი პირდაპირაა დამოკიდებული ამ ორი ქსელიდან თითოეულში შემავალი კომპიუტერების რაოდენობათა ჯამზე. ასე მაგალითად, თუ ერთ ქსელში გაერთიანებულია k1 კომპიუტერი, ხოლო მეორეში – k2 კომპიუტერი, დანახარჯი ამ ორი ქსელის გაერთიანებაზე წარმოადგენს k1+k2. ამასთან ცნობილია, რომ ყოველი კომპიუტერი ერთ სხვა კომპიუტერთან მაინც არის მიერთებული, ქსელების საერთო რაოდენობა არ აღემატება 50000-ს და ერთდროულად შეუძლებელია ორზე მეტი ქსელის გაერთიანება.

სპეციალურმა ჯგუფმა გადანომრა ქვეყანაში არსებული კომპიუტერები 1-დან N-მდე (5≤N≤200000) და დაადგინა თუ რომელი კომპიუტერი რომელთანაა შეერთებული. ახლა მას სურს დაადგინოს რა მინიმალური დანახაჯითაა შესაძლებელი არსებული ქსელების ერთ ქსელად გაერთიანება. დაეხმარეთ მათ ამ ამოცანის გადაწყვეტაში.

შემომავალი მონაცემები:

პირველ სტრიქონში წერია ორი მთელი რიცხვი N და M (5≤M≤1000000) – შესაბამისად, კომპიუტერების საერთო რაოდენობა და ერთმანეთთან შეერთებულ კომპიუტერთა წყვილების საერთო რაოდენობა. მომდევნო M სტრიქონიდან თითოეულში მოცემულია ჰარით გაყოფილი ორი რიცხვი – ერთმანეთთან შეერთებული კომპიუტერების ნომრები.

გამომავალი მონაცემები:

ერთადერთ სტრიქონში გამოიტანეთ ერთადერთი მთელი რიცხვი, რომელიც წარმოადგენს არსებული ქსელების გასაერთიანებლად საჭირო მთლიანი დანახარჯის მინიმუმს.

მაგალითები

შესატანი მონაცემები
9 5
7 3
1 4
2 9
8 5
5 6
                  დაკოპირება

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

შენიშვნა

გამომავალი მონაცემების განმარტება:

არსებობს 4 ქსელი, რომლებშიც კომპიუტერების რაოდენობაა 2, 2, 2 და 3. თუ ჩვენ ჯერ გავაერთიანებთ მე-4 და მე-3-ს, შემდეგ ამ ქსელს მივუერთებთ მე-2-ს და და ბოლოს შევაერთებთ პირველთან, დანახარჯი იქნება 5+7+9=21. ხოლო თუ გავაერთიანებთ 1-ს და მე-2-ს, შემდეგ მე-3-ს და მე-4-ს, ბოლოს კი – მიღებულ ორ ქსელს, დანახარჯი იქნება 4+5+9=18.