페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4153

Delegation 2초 512MB

문제

Farmer John's farm consists of N pastures (2 \leq N \leq 10^5) connected by N-1 roads, so that any pasture is reachable from any other pasture. That is, the farm is a tree. But after 28 years of dealing with the tricky algorithmic problems that inevitably arise from trees, FJ has decided that a farm in the shape of a tree is just too complex. He believes that algorithmic problems are simpler on paths.

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..

Problem credits: Mark Gordon and Dhruv Rohatgi


입력

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.


출력

Print K.


예제1

입력
8
1 2
1 3
1 4
4 5
1 6
6 7
7 8
출력
3

One possible set of paths is as follows:

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


출처

USACO 2020 February Platinum

역링크 공식 문제집만