გამოქვაბული

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

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

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

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

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


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

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

  შემომავალი მონაცემები:  პირველად შემოდის დადებითი მთელი რიცხვი n (1 ≤ n ≤ 50,000), რომელიც განსაზღვრავს ოთახების რაოდენობას გამოქვაბულში. ოთახები გადანომრილია 1-დან n-მდე. შემდეგ შემოდის n – 1 ხაზი. ეს ხაზი შედეგება ორი დადებითი მთელი რიცხვისგან a და b (1 ≤ a, b ≤ n), რომელიც დაშორებულია ჰარით(space-ით). ეს ორი რიცხვი აღწერს დერეფანს, ანუ ოთახი a და b დაკავშირებულია დერეფნით.

  გამოსატანი მონაცემები: თქვენმა პროგრამამ უნდა გამოიტანოს ერთი რიცხვი. რიცხვი აღწერს მინიმალურ კითხვების რაოდენობას, რომელიც გრეტელმა უნდა დასვას იმისთვის, რომ ყვეალზე უარეს შემთხვევაშიც მოძებნოს საგანძური (ვვარაუდობთ, რომ გრეტელი სვამს კითხვებს მაქსიმალურად ოპტიმალურად, მაგრამ საგანძური დამალულია, ისეთ ოთახში, რომელიც ითხოვს შეკითხვების ყვეალზე დიდი რაოდენობის დასმას.)

 

 




მაგალითები

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