დინამიტი

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

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

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

წყარო: პოლონეთი, ოლიმპიადა 18, ეტაპი 3


კარსტული მღვიმე n ცალი ღრუსგან და n-1 ცალი დერეფნისგან შედგება, რომლებიც ღრუებს ერთმანეთთან აერთებს. ღრუების თითოეული წყვილისთვის არსებობს უნიკალური გზა ერთიდან მეორეში მისასვლელად, ისე რომ მღვიმე არ დავტოვოთ. მღვიმის ზოგიერთ ღრუში დინამიტია განთავსებული. ყველა დერეფანში კი ნავთია დასხმული. თითოეული ღრუსთვის მეზობელ დერეფნებში მოსხმული ნავთი ერთ წერტილში ერთიანდება და ღრუში განთავსებულ დინამიტამდე გრძელდება. ორ მეზობელ ღრუს შორის მოსხმულ ნავთზე ცეცხლის წაკიდებას ზუსტად დროის ერთეული სჭირდება, ხოლო ღრუში არსებული დინამიტი კი ცეცხლის წაკიდების შემდეგ დაუყოვნებლივ ფეთქდება.
                ჩვენ გვინდა, რომ რომელიღაც
m ღრუში ნავთს ცეცხლი წავუკიდოთ, ისე რომ ყველა დინამიტი რაც შეიძლება მალე აფეთქდეს ნავთზე ცეცხლის მოკიდების შემდეგ. დაწერეთ პროგრამა, რომელიც დაადგენს უმოკლეს დროს, რომელშიც ამას მოვახერხებთ.

შესატანი მონაცემები:

შესატანი მონაცემების პირველი ხაზი შეიცავს ერთი ჰარით(სფეისით) გამოყოფილ 2 მთელ რიცხვს n-ს და m-ს (1<=m<=n<=300,000), რომლებიც შესაბასიმად მღვიმეში არსებული ღრუების რაოდენობას და ისეთი ღრუების რაოდენობას აღნიშნავენ, რომლებშიც ნავთისთვის ცეცხლის წაკიდება შეგვიძლია. ღრუები 1-დან n-მდეა გადანომრილი. შემდეგი ხაზი შეიცავს n ცალ ჰარით(სფეისით) დაშორებულ მთელ რიცხვს: d1,d2,…,dn  (di  {0,1}). თუ di=1, მაშინ დინამიტი i-ურ ღრუშია, ხოლო თუ di=0, მაშინ i-ურ ღრუში დინამიტი არ გვაქვს. შემდეგი n-1 ცალი ხაზი მიუთითებს მღვიმის დერეფნებზე. თითოეული ხაზი შეიცავს ერთი ჰარით(სფეისით) გამოყოფილ 2 მთელ რიცხვს a,b-ს (1<=a<b<=n), რაც იმას ნიშნავს, რომ ისინი დერეფნით უკავშირდებიან ერთმანეთს. თითოეული დერეფანი აღწერაში ზუსტად ერთხელ გვხვდება.
                თქვენ შეგიძლიათ ჩათვალოთ,რომ ტესტებში, რომლებიც ქულების 10%-ს შეადგენს
n<=10, ხოლო ტესტებში, რომლებიც ქულების 40%-ს შეადგენს n<=1000.
               

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

გამოსატანი მონაცემების პირველი და ერთადერთი ხაზი უნდა შეიცავდეს 1 მთელ რიცხვს, რომელიც ტოლია მინიმალური დროის, ცეცხლის ანთებიდან ყველა დინამიტის აფეთქებამდე.




მაგალითები

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

შენიშვნა

მაგალითის ახსნა: ჩვენ ცეცხლს ვანთებთ მე3 და მე5 ღრუებში. დროის 0 მომენტში, დინამიტი ფეთქდება მე3 ღრუში, ხოლო დროის 1 ერთეულის შემდეგ დინამიტები 1, 4, 6, 7 ღრუებში ინთება.

 

თარგმანი შესრულებულია ირაკლი ბარელაძის მიერ