COCI 2008/2009, Contest #1

Task KRTICA

Moles are tidy and hard-working animals. Our mole likes to keep its underground residence in utmost order, so that everyone living there knows where to find things.

To achieve this, the mole connected rooms with tunnels so that there is a single unique way to get from one room to any other room. The distance between two rooms is the number of halls passed on the way from one to the other.

Despite all the effort, some of the mole's guests are complaining that it takes too long to walk between certain pairs of rooms.

The mole decided to reconstruct her residence, closing one tunnel and opening a new one, so that the distance between the farthest two rooms is the smallest possible, but so that it is still possible to reach every room from every other room.

Write a program which determines the distance between the farthest two rooms after reconstruction, which tunnel to close and which to open.

Input

The first line contains an integer N (1 ≤ N ≤ 300 000), the number of rooms. The rooms are numbered 1 to N.
Each of the next N-1 lines contains two integers, the numbers of rooms a tunnel connects.

Output

Output the distance between the two farthest rooms after reconstruction.

Grading

In test cases worth 40% of points, N will be less than 30.
In test cases worth 70% of points, N will be less than 3000.

Examples

Input

4
1 2
2 3
3 4

Output

2

Input

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

Output

3

All Submissions
Best Solutions


Point Value: 35 (partial)
Time Limit: 3.00s
Memory Limit: 128M
Added: Oct 18, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

is it possible to open the tunnel you've just closed, so that the graph stays the same, but that there was reconstruction?

I guess that's okay according to the question statement...