ქვეხის ამორჩევა

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

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

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

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

წყარო: COCI, 2008/2009, 1


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

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი N (1 ≤ N ≤ 300 000), ხის წვეროთა რაოდენობა. მომდევნო N−1 სტრიქონიდან თითოეულში ორ-ორი მთელი რიცხვი, რომლრბიც აღწერენ ხის წიბოებს.

გამოსატანი მონაცემები: ერთადერთ სტრიქონში ერთი მთელი რიცხვი - ახალი ხის დიამეტრი. 




მაგალითები

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