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.</p>

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, b ≤ n).

출력 형식

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

예제 입력

6
1 2
2 3
5 2
3 4
6 1

예제 출력

4