Capitals

Linearlândia has built a network of high-speed railways connecting certain city pairs so that: it is possible to travel between any city pair using only railways, and there is only one railroad path (sequence of railways) between any city pair. There is a lot of dispute between the capitals of the Linearlândia states, so it was decided that each capital would be connected by rail to only one other city and that every city that is not capital would be connected to other cities by two or more railways. Thus, no trip between a pair of capital cities using only railroads passes through a third capital city.

Figure 1

Let's define as railroad distance between two cities the number of railways that are necessary to travel between these two cities. Given only the information about which pairs of cities are connected by a railroad, you should write a program to compute the smallest railroad distance between all the capital pairs. In the figure above, there are nine capital cities and the smallest rail distance between any pair of capital cities is 3, between capital cities 5 and 12.

Input

The first line contains an entire NN, the number of cities. Cities are identified by integers from 1 to NN. The following N1N-1 lines contain two integers UU and VV, representing a pair of cities connected by a railroad.

Output

Your program should produce a single line, containing a single integer, the shortest distance between all the capital pairs.

Constraints

  • 2 \leq NN 105\leq 10^5
Input Samples Output Samples
8
1 2
2 3
3 4
5 3
6 5
6 7
8 7
3
2
1 2
1
Translated by Luis Paulo