Нюхли

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n개의 노드로 이루어진 트리에서 서로 다른 두 리프 사이의 최소 거리를 구한다.

난이도: 보통10점 중 6점
유형: 트리, 그래프, BFS
정답자: 아직 제출이 없습니다

문제

Ньют Саламандер в очередной раз наблюдает за детенышами нюхлей. Ему интересно, так ли хорошо они ищут золото, как и взрослые особи.

Для испытаний Ньют взял $n$ коробок и соединил их $n - 1$ двунаправленными тоннелями так, чтобы между каждыми двумя коробками был ровно один простой путь. Ньют называет тупиком любую коробку, в которую можно попасть только по одному тоннелю.

Ньют хочет разместить нюхля в одном тупике, а в каком-то другом тупике разместить золотую монету. Однако так как нюхль еще маленький, Ньют хочет выбрать тупики так, чтобы детеныш прошел как можно меньше тоннелей при поиске монеты.

Ваша задача помочь Ньюту найти минимальное число тоннелей, которое придется пройти детенышу нюхля, чтобы найти монету при оптимальном выборе тупиков.

입력

В первой строке дано целое число $n$ --- число коробок ( $2 \le n \le 10^5$ ).

В следующих $n - 1$ строках заданы по два числа $a\_i$ , $b\_i$ --- номера коробок, которые соединены $i$ -м тоннелем ( $1 \le a\_i, b\_i \le n$ ).

Гарантируется, что между любыми двумя коробками, существует ровно один простой путь.

출력

Выведите одно число --- минимальное расстояние, которое нужно пройти нюхлю, чтобы найти монету.

예제2

예제 1
입력
```
5
1 2
1 3
2 4
2 5
```
예상 출력
```
2
```
예제 2
입력
```
5
1 3
2 1
4 5
5 3
```
예상 출력
```
4
```