Problem description

– Jadę ulicą, opony asfalt drą, pingwiny jak zobaczą drzewo, na zawał umerą. Hej! Julian, Julian, on twardy jest jak głaz. – radośnie śpiewał sobie Król Julian, jadąc ciężarówką, na którą załadowane było zwędzone świąteczne drzewo.

– Jedziemy panie ciut za wolno, trzeba wcisnąć gaz – donucił melodyjnie piszczącym głosem Mort.

– Gonią nas z dużą prędkością.

– O poważnie, to wcisnę sprzęgło.

– Panowie, lemury zbliżają się do nas ze zbyt dużą prędkością, a do tego wiozą jakieś nie najgorszej jakości drzewo – zarzucił Skipper. – Nie możemy być gorsi; Kowalski opcje!

– No wie szef, można byłoby wysadzić Lemury – opowiedział Kowalski, na co Rico entuzjastycznie wypluł laskę dynamitu.

– Rico, Kowalski ma na myśli wysadzenie Choinki Lemurów, a nie Lemurów. Prawda Kowalski? – zareagował z oburzeniem Szeregowy.

– Yyy, tak, to miałem na myśli, oczywiście – Wychrząkał Kowalski. – Możemy też zrobić własne drzewo.

– Uuu to mi się podoba Kowalski. Rico piła! A Ty Kowalski powiedz jak zrobić, żeby drzewo było piękne.

No więc szefie. Drzewo jest grafem spójnym, ma N wierzchołków, ponumerowanych kolejnymi liczbami naturalnymi od 1 do N i N − 1 krawędzi je łączących. Moim zdaniem drzewo, podające się za choinkę, jest najpiękniejsze, gdy odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami jest minimalna. Powinniśmy pozbyć się jednej krawędzi i dołożyć jedną tak, by było możliwie najładniejsze (i oczywiście dalej było poprawnym drzewem).

No i tutaj pojawił się problem, bo Pingwiny nie wiedzą, jak piękne może być drzewo po ich poprawce. Twoim zadaniem będzie napisanie programu, który wyznaczy minimalną odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami, jaką można uzyskać po usunięciu jednej krawędzi z oryginalnego drzewa i dodaniu nowej.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N. W kolejnych N − 1 wierszach znajdują się po dwie liczby naturalne X_i i Y_i, oddzielone pojedynczym odstępem i oznaczające krawędź pomiędzy wierzchołkami o numerach X_i i Y_i.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami, jaką można uzyskać po usunięciu jednej krawędzi z oryginalnego drzewa i dodaniu nowej.

Ograniczenia

1 ≤ N ≤ 300 000, 1 ≤ X_i, Y_i ≤ N.

Przykład

5
1 2
2 3
3 4
4 5

3

7
1 2
2 3
2 4
2 5
3 6
6 7

3

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.