ხე

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

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

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

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

წყარო: GEOI, 2010, დასკვნითი, XI-XII კლასი


 მოცემულია ხე (გრაფი, რომელშიც ნებისმიერი ორი წვერო დაკავშირებულია ზუსტად ერთი მარტივი გზით) რომელიც 1-დან N-მდე გადანომრილი N რაოდენობის წვეროსაგან შედგება. 
 
    დაწერეთ პროგრამა, რომელიც დაადგენს, წიბოთა რა მინიმალური რაოდენობა უნდა დაემატოს ხეს, რომ ყოველი წვერო ზუსტად ერთ ციკლს ეკუთვნოდეს, ან გამოიტანს შესაბამის შეტყობინებას, თუ ამის გაკეთება  შეუძლებელია. ბუნებრივია, უკვე არსებული წიბოს დამატება (ორი სიგრძის ციკლის შექმნის მიზნით) არ შეიძლება.
 
    შესატანი მონაცემები: შესატან მონაცემთა ფაილის პირველ სტრიქონში მოცემულია ერთი ნატურალური N რიცხვი (3 ≤ N ≤ 100) - ხეში წვეროების რაოდენობა. მომდევნო N-1 რაოდენობის სტრიქონიდან თითოეულში ჩაწერილია თითო ჰარით გამოყოფილი ორი მთელი დადებითი რიცხვი. ფაილის (i+1)-ე სტრიქონში ჩაწერილი რიცხვთა (x[i], y[i]) წყვილი (1 ≤ x[i], y[i] ≤ N) იმ წვეროთა ნომრებია, რომლებიც ერთმანეთთან i-ური წიბოთია დაკავშირებული. გარანტირებულია რომ შესატანი მონაცემები აღწერენ კორექტულ ხეს.
 
    გამოსატანი მონაცემები: გამოსატან მონაცემთა ფაილის ერთადერთ სტრიქონში უნდა ჩაიწეროს ხეში დამატებული წიბოების მინიმალური რაოდენობა, თუ ამოცანას ამონახსნი აქვს და -1 წინააღმდეგ შემთხვევაში.



მაგალითები

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