Longest Minimum Chain Partition

Farmer John has N pastures connected by N-1 roads, forming a tree. After 28 years of managing his farms, FJ believes that tree‐based problems are too challenging and that problems on chains are simpler.

Thus, he decides to partition the entire tree into some chains and assign each chain to a worker. Although he does not care about the number of chains, he cares about their lengths – he wants every chain to be as long as possible so that no one can get away with using an inefficient algorithm.

Your task is to determine the largest positive integer K such that the tree can be partitioned into chains, with each chain having a length of at least K (i.e. each chain contains at least K edges).

Note: The tree is undirected and connected. A chain is defined as a simple path (i.e. a sequence of adjacent edges without repeating any vertex).

All formulas are given in LaTeX format. For instance, the number of pastures is given as $N$, and the number of roads is $N-1$.

inputFormat

The first line contains a single integer N ($2 \le N \le 10^5$), representing the number of pastures.

The following N-1 lines each contain two integers u and v ($1 \le u, v \le N$), indicating that there is an edge connecting pasture u and pasture v.

You can assume that the given graph is a tree.

outputFormat

Output a single integer: the maximum integer K such that the tree can be partitioned into chains, each of which has a length of at least K.

sample

2
1 2

1