집으로 돌아가기

아르만은 최근 시골의 외딴 마을로 이사했다. 마을 지도는 트리 모양이다. 즉 $n$개의 교차로를 잇는 도로가 정확히 $n-1$개 있고, 어느 두 교차로 사이에도 도로를 따라가는 경로가 있다.

아르만은 아침마다 사무실로 가고 밤늦게 집으로 돌아온다. 밤에는 매우 어둡고 마을 도로에는 가로등이 없어서 아르만은 집으로 돌아오는 길을 찾기가 어려워졌다. 교차로에는 표지판이 없고 교차로를 서로 구별할 수도 없다. 게다가 길에서는 휴대전화 신호가 잡히지 않아 GPS도 쓸 수 없다. 이 문제를 해결하려고 아르만은 손전등을 사기로 했다. 손전등의 조명 거리는 정수이고, 조명 거리가 길수록 값이 비싸다. 조명 거리가 $d$인 손전등은 지금 있는 교차로에서 거리가 $d$ 이하인 교차로를 모두 비춘다. 마을의 모든 도로는 길이가 1로 같다.

사무실에서 집으로 출발한 아르만은 지나가는 교차로마다 다음과 같이 판단한다.

1. 집이 보이면 집을 향해 곧바로 이동한다.
2. 지금 교차로 $u$에 있다고 하자. $A$는 $u$에 연결된 모든 도로의 집합이다. $B$는 출발 시점에는 공집합이고, 그 외에는 아르만이 $u$로 들어올 때 지나온 도로 $e$ 하나만 담은 집합 $\{e\}$이다. $C$는 $u$에 연결된 쓸모없는 도로의 집합이다. $u$에서 출발해 도로 $e'$를 지나는 모든 단순 경로의 길이가 $d$보다 작으면, $u$에 연결된 도로 $e'$를 쓸모없다고 한다. $A - (B \cup C)$가 공집합이 아니면 이 집합에서 도로 하나를 무작위로 고른다. 공집합이면 도로 $e$를 다시 고른다.

무작위로 어떻게 고르더라도 도로를 최대 $10^9$개만 지나면 결국 집에 도착한다는 보장만 있다면, 아르만은 조금 더 걷는 것을 개의치 않는다. 그런 보장을 받을 수 있는 가장 싼 손전등을 사려고 한다. 아르만이 집에 도착할 수 있는 손전등의 최소 조명 거리를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 마을의 교차로 개수 $n$이 주어진다 ($2 \le n \le 30000$). 다음 $n-1$개의 줄에는 각각 두 정수 $a$, $b$가 주어지며, 교차로 $a$와 $b$를 잇는 도로가 있다는 뜻이다 ($1 \le a, b \le n$). 아르만의 집은 1번 교차로이고 사무실은 $n$번 교차로이다. 입력은 0 하나만 있는 줄로 끝나며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 무작위로 어떻게 고르더라도 아르만이 도로를 최대 $10^9$개만 지나 집에 도착하도록 보장하는 손전등의 최소 조명 거리 $d$를 한 줄에 출력한다. 손전등이 필요 없으면 0을 출력한다.