## USACO 2020 February Contest, Platinum

## Problem 1. Delegation

Contest has ended.

**Log in to allow submissions in analysis mode**

Thus, his plan is to partition the set of roads into several paths and delegate responsibility for these path among his worthy farm hands. He doesn't care about the number of paths. However, he wants to make sure that these paths are all as large as possible, so that no farm hand can get away with asymptotically inefficient algorithms!

Help Farmer John determine the largest positive integer $K$ such that the roads can be partitioned into paths of length at least $K$.

#### SCORING:

- In test cases 2-4 the tree forms a star; at most one vertex has degree greater than two.
- Test cases 5-8 satisfy $N\le 10^3$.
- Test cases 9-15 satisfy no additional constraints..

#### INPUT FORMAT (file deleg.in):

The first line contains a single integer $N$.The next $N-1$ lines each contain two space-separated integers $a$ and $b$ describing an edge between vertices $a$ and $b$. Both $a$ and $b$ are in the range $1 \ldots N$.

#### OUTPUT FORMAT (file deleg.out):

Print $K$.#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

3

One possible set of paths is as follows:

Problem credits: Mark Gordon and Dhruv Rohatgi