트리의 스텝 순회

그래프는 쌍 $(V, E)$ 로 정의된다. $V$ 는 정점(vertex)이라고 부르는 원소들의 유한 집합이고, $E$ 는 서로 다른 두 정점으로 이루어진 순서 없는 쌍들의 집합으로 그 각 원소를 간선(edge)이라고 부른다. 서로 다른 임의의 두 정점 $u$, $v$ 에 대하여 $w_0 = u$, $w_k = v$ 이고 모든 $i = 0, \dots, k-1$ 에서 $\{w_i, w_{i+1}\} \in E$ 를 만족하는, 서로 다른 정점들의 수열 $w_0, w_1, \dots, w_k$ 가 항상 정확히 하나 존재하면 그 그래프를 트리(tree)라고 한다. 이때 트리에서 두 정점 $u$ 와 $v$ 사이의 거리를 $k$ 로 정의한다.

정점이 $n$ 개인 트리는 항상 정확히 $n-1$ 개의 간선을 가진다. 정점에 $1$ 부터 $n$ 까지 번호를 매긴 트리는 정점의 개수 $n$ 과, 각 간선의 두 끝점을 나타내는 $n-1$ 개의 정수 쌍으로 유일하게 표현할 수 있다.

트리의 순회 순서(traversing order)란 모든 정점이 정확히 한 번씩 나타나는 정점들의 순열이다. $1$ 이상의 정수 $c$ 에 대하여, 어떤 순회 순서에서 연속한 두 정점 사이의 거리가 항상 $c$ 이하이면 그 순서를 스텝(step) $c$ 의 순회 순서라고 한다.

아래 그림은 정점이 7개인 트리를 나타낸 것으로, 정점은 점으로, 간선은 두 점을 잇는 선분으로 그려져 있다.

모든 트리는 스텝 $3$ 의 순회 순서를 가진다는 사실이 알려져 있다. 따라서 순회 순서가 존재하는 가장 작은 스텝 값은 항상 존재하며 그 값은 $3$ 이하이다.

트리가 주어질 때, 그 트리가 스텝 $c$ 의 순회 순서를 가지는 가장 작은 $c$ 를 구하는 프로그램을 작성하라.

• 첫째 줄에 트리의 정점 개수를 나타내는 양의 정수 $n$ 이 주어진다 ($1 \le n \le 5000$).
• 다음 $n-1$ 개의 각 줄에는 하나의 간선을 이루는 두 양의 정수가 공백 하나로 구분되어 주어진다.

• 트리가 스텝 $c$ 의 순회 순서를 가지는 가장 작은 정수 $c$ 를 한 줄에 출력한다.