გრაფის დიამეტრი

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

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

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

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

წყარო: BULG, 2007/08, დასკვნითი, 11-12


მოცემულია არაორიენტირებული გრაფი n წვეროთი და n–1 წიბოთი. გრაფი ბმულია და თითოეულ წიბოს გააჩნია მთელი არაუარყოფითი რიცხვით გამოსახული წონა. აღვნიშნოთ d(x,y)-ით უმოკლესი მანძილი x და y წვეროებს შორის. გრაფის დიამეტრი ვუწოდოთ d(x,y) რიცხვებს შორის უდიდესს, სადაც x და y გრაფის ნებისმიერი ორი წვეროა. დაწერეთ პროგრამა, რომელიც იპოვის გრაფის დიამეტრს.

შესატანი მონაცემები: პირველ სტრიქონში შემოდის ერთი მთელი რიცხვი n (0 < n < 1000) - წვეროების რაოდენობა გრაფში. წვეროები გადანომრილია რიცხვებით 1-დან n-მდე. მომდევნო n–1 სტრიქონიდან თითოეულში სამ-სამი რიცხვით აღწერილია გრაფის წვეროები: პირველი ორი რიცხვით მოცემულია იმ წვეროების ნომრები, რომელთაც შესაბამისი წიბო აერთებს. ხოლო მესამე რიცხვი აღნიშნავს წიბოს წონას. წიბოს წონა არაუარყოფითი მთელი რიცხვია და არ აღემატება 1000-ს. 

გამოსატანი მონაცემები: გრაფის დიამეტრი. 




მაგალითები

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