Description

Farmer John has $N$ pastures. These pastures are connected by $N - 1$ roads, forming a tree.

However, after 28 years of running the farm (translator’s note: USACO was founded in 1992), FJ feels that dealing with tree problems is very difficult. He believes problems on paths are simpler.

So he decides to split the whole tree into several paths, and give the management of each path to a worker. He does not care about the number of paths, but he cares about their lengths. He wants all paths in the partition to be as long as possible, so that no one can get by using an inefficient algorithm.

FJ now wants to know the largest positive integer $K$ such that the entire tree can be partitioned into several paths, and the length of each path is at least $K$.

Input Format

The first line contains an integer $N$ ($1 \leq N \leq 10^5$).

The next $N - 1$ lines each contain two integers $u, v$ ($1 \leq u, v \leq N$), describing a road connecting $u$ and $v$.

Output Format

Output $K$.

8
1 2
1 3
1 4
4 5
1 6
6 7
7 8

3

Hint

Sample Explanation

One possible partition is:

Subtasks

• Test points $2 \sim 4$ satisfy that at most one node has degree greater than $2$.
• Test points $5 \sim 8$ satisfy $N \leq 10^3$.
• Test points $9 \sim 15$ have no special constraints.

Translated by ChatGPT 5