Step Traversing a Tree

A graph is a pair $(V, E)$, where $V$ is a finite set of elements called vertices and $E$ is a set of unordered pairs of distinct vertices, whose elements are called edges. The graph is a tree if for every pair of distinct vertices $u$ and $v$ there is exactly one sequence of distinct vertices $w_0, w_1, \dots, w_k$ such that $w_0 = u$, $w_k = v$ and $\{w_i, w_{i+1}\} \in E$ for every $i = 0, \dots, k-1$. The distance between $u$ and $v$ in the tree is defined to be $k$.

A tree on $n$ vertices has exactly $n-1$ edges. A tree whose vertices are numbered from $1$ to $n$ is described uniquely by the number of vertices $n$ together with the $n-1$ pairs of endpoints of its edges.

A traversing order of a tree is a permutation of its vertices, that is, a sequence in which every vertex appears exactly once. For an integer $c \ge 1$, a traversing order has step $c$ if the distance between every two consecutive vertices in the order is at most $c$.

The picture below shows a tree on seven vertices, with vertices drawn as dots and edges as segments joining them.

It is known that every tree has a traversing order with step $3$, so the smallest step for which a traversing order exists always exists and is at most $3$.

Write a program that reads a tree and outputs the smallest $c$ for which the tree has a traversing order with step $c$.

• The first line contains a positive integer $n$ ($1 \le n \le 5000$), the number of vertices of the tree.
• Each of the next $n-1$ lines contains one edge, given as two positive integers separated by a single space.

• Output a single integer: the smallest $c$ for which the tree has a traversing order with step $c$.