두 집배원

바이톨리 마을에 새 우체국이 문을 열었다. 우체국은 집배원 두 명을 고용했고, 두 사람은 매일 아침 우체국에서 출발해 마을 곳곳으로 편지를 배달한다. 마지막 편지가 최대한 이른 시각에 배달되도록 두 집배원의 이동 경로를 짜야 한다.

마을에는 $1$번부터 $n$번까지 번호가 붙은 집이 $n$채 있다. 우체국은 $1$번 집이다. 집들은 양방향 도로 $n-1$개로 연결되어 있으며, 이 도로망을 통해 임의의 두 집 사이를 오갈 수 있다(즉, 도로망은 하나의 트리를 이룬다). 도로 한 구간을 지나는 데는 집배원에게 $1$분이 걸린다.

두 집배원은 모두 우체국($1$번 집)에서 출발하고, 모든 집에 편지가 배달되어야 한다. 각 도로는 두 집배원 중 적어도 한 명이 지나가면 된다. 집배원은 배달을 끝낸 뒤 우체국으로 돌아올 필요가 없다. 마지막 편지가 배달되는 시각은 두 집배원이 각자 마지막 배달을 마치는 시각 중 더 늦은 쪽이며, 이 값을 가장 작게 만드는 것이 목표다.

첫째 줄에 마을의 집 수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 3000$).

다음 $n-1$개의 줄에는 도로 정보가 한 줄에 하나씩 주어진다. 각 줄에는 정수 두 개 $a$, $b$가 있고, 이는 $a$번 집과 $b$번 집을 잇는 도로가 있음을 뜻한다 ($1 \le a, b \le n$).

두 집배원이 모든 편지를 다 배달하는 데 걸리는 최소 시간을 분 단위로 한 줄에 출력한다.