მეტრო

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

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

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

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

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


Ერთ-ერთ ქალაქში გადაწყდა მეტროს მშენებლობა თუმცა არასწორი დაგეგმარების გამო აღმოჩნდა რომ ფინანსები არასაკმარისია მშენებლობის შემდეგ მეტროს მატარებლების შესაძენად. Მოცემული მშენებლობები საკმარისი აღმოჩნდა, რომ ყოველი მეტროს სადგურისთვის შესაძლებელი ყოფილიყო ყველა სხვა სადგურში მისვლა მეტროს ხაზებით. Ამასთან მეტროს ხაზების რაოდენობა (მეტროს ხაზით აღვნიშნოთ 2 მეზობელი მეტროს სადგურს შორის მონაკვეთი) ერთით ნაკლებია სადგურების რაოდენობაზე.

 Შესაბამისად, დარჩენილი თანხით ქალაქმა მხოლოდ რამდენიმე მატარებლის შეძენა მოახერხა. Თავისი სახელის გადასარჩენად გადაწყვიტეს, რომ შეძენილი ფიქსირებული რაოდენობის მატარებლებისთვის ისეთი მარშრუტი შეედგინათ, რომ ჯამში მატარებლებლის მარშრუტების მიერ დაფარული სადგურების რაოდენობა მაქსიმალური ყოფილიყო. Თუმცა ერთი შეზღუდვით - მატარებლის მარშრუტი უნდა ყოფილიყო სწორი ხაზი რაც ნიშნავს რომ მარშრუტი შეადგენს მეტროს ხაზების მიმდევრობას რომელიც ერთ-ერთი სადგურიდან იწყება  და სხვა რომელიმე სადგურში მთავრდება (ეს შეზღუდვა არ ნიშნავს რომ სხვადასხვა მატარებლის ხაზებს არ ექნებათ თანაკვეთა მეტროს სადგურების ან ხაზების სიმრავლეში).

 

 Თქვენი ამოცანაა:

 

  • Წაიკითხოთ მეტროს ლიანდაგებისა და სადგურების განლაგება და კავშირები წინასწარ მოცემულ ფორმატში სტანდარტული ინფუთიდან.
  • Იპოვოთ მაქსიმალური რაოდენობის მეტროს სადგურები რაც შეიძლება დაიფაროს მოცემული რაოდენობის მატარებლების მარშრუტების სწორად დაგეგმვით.
  • Დაბეჭდეთ ეს მნიშვნელობა სტანდარტულ აუთფუთში.

 შესატანი მონაცემები: Პირველ ხაზზე მოცემულია 2 რიცხვი N და L სადაც N არის მეტროს სადგურების რაოდენობა (რომელიც გადანომრილია 1 დან N მდე) და L არის შეძენილი მატარებლების რაოდენობა. Მეორე ხაზიდან მოცემულია N-1 რიცხვთა წყვილი თუ რომელი სადგურებია დაკავშირებული (მეზობლები) ერთმანეთთან.

 

 გამოსატანი მონაცემები: Პასუხად დაბეჭდეთ მაქსიმალური რაოდენობის მეტროს სადგურები რაც შეიძლება დაიფაროს მოცემული რაოდენობის მატარებლების მარშრუტებით.

ქვემოთ მოყვანილი მაგალითის შესაბამისი ნახაზი იხილეთ ლინკზე:

https://szkopul.edu.pl/problemset/problem/iho4pUEITa4G4NJDKU1-8z8g/site/?key=statement

 




მაგალითები

შესატანი მონაცემები
17 3 1 2 3 2 2 4 5 2 5 6 5 8 7 8 9 8 5 10 10 13 13 14 10 12 12 11 15 17 15 16 15 10 დაკოპირება
გამოსატანი მონაცემები
13 დაკოპირება