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
Input
The first line contains an entire , the number of cities. Cities are identified by integers from 1 to . The following lines contain two integers and , 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
Input Samples | Output Samples |
---|---|
8 1 2 2 3 3 4 5 3 6 5 6 7 8 7 |
3
|
2 1 2 |
1
|