시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

We wsi Bajtoły Dolne wybudowano piękny i nowy Urząd Pocztowy. Zatrudniono dwóch listonoszy, którzy co dzień rano będą wyruszać z budynku poczty i rozwozić listy po wsi. Należy tak zaplanować ich trasy, by ostatni list został doręczony jak najwcześniej.

W Bajtołach jest n domów ponumerowanych liczbami całkowitymi od 1 do n. Budynek poczty jest domem z numerem 1. Domy są połączone spójną siecią n - 1 dwukierunkowych dróg. Przejechanie odcinka drogi zajmuje listonoszowi jedną minutę.

입력

W pierwszym wierszu wejścia znajduje się liczba całkowita n oznaczająca liczbę domów we wsi (1 ≤ n ≤ 3 000). W kolejnych n - 1 wierszach znajdują się opisy dróg. Każdy z nich składa się z dwóch liczb a, b oznaczających drogę łączącą domy a i b (1 ≤ a, bn).

출력

W jedynym wierszu wyjścia należy wypisać minimalny czas w minutach, w którym listonoszom uda się rozwieźć wszystkie listy.

예제 입력 1

6
1 2
2 3
5 2
3 4
6 1

예제 출력 1

4

출처

Camp > POI Training Camp > ONTAK 2009 2-2번