Problem 4133: Conspirație

At the beginning of the year 2026, the entire planet was infected by multiple viruses. In each country, a unique virus appeared. Due to the economic crisis that came along with these pandemics, international travel was restricted such that there exists a single route between any two distinct countries.

World leaders agreed that each day only one road among the remaining ones would be available for traversal. When a route between two countries is opened, the people of the two states infect each other, and the virus chosen by the leaders between the two remains alive in both states.

World leaders hired you to determine the minimum number of days needed for the entire planet to be infected by a single virus.

Task

Formally, you are given the list of edges of a tree with $n$ nodes. Initially, state $i$ is considered to be infected with the virus $virus_i = i$ . On day $x$ , the edge $x$ modulo $(n - 1)$ (let it be $U - V$ ) will be available and we are forced to perform one of the following two operations:

$virus_U = virus_V$ (node $U$ receives the value of node $V$ )
$virus_V = virus_U$ (node $V$ receives the value of node $U$ )

Edges and days are indexed starting from $0$ .

You are asked to output the minimum number of days after which it is guaranteed that all nodes will have the same value, assuming you apply an optimal strategy.

Input Data

On the first line, a single natural number $n$ is read, representing the number of nodes in the tree.

On the next $n - 1$ lines, the edges that form the tree are read. On each line there are two distinct natural numbers between $1$ and $n$ , representing the endpoints of the respective edge.

Output Data

You must output a single natural number representing the minimum number of days required to infect the entire planet with the same virus.

Constraints

$1 \le n \le 1\,000\,000$

#	Points	Restrictions
1	30	$1 \le n \le 1\,000$
2	70	No additional constraints

Example 1

stdin

stdout

Explanation

In the first example, the tree is a chain of the form $1$ -- $3$ -- $2$ -- $4$ . On day $0$ , the edge $1$ -- $3$ will be available and we will choose $virus_1$ to receive the value of $virus_3$ . On day $1$ , the edge $2$ -- $4$ will be available and we will choose $virus_4$ to receive the value of $virus_2$ . On day $2$ , we will choose $virus_3$ to receive the value of $virus_2$ , and on day $3$ we will choose $virus_1$ to receive the value of $virus_3$ . After four days, all nodes will have the same value. It can be shown that the nodes cannot obtain the same value in fewer than four days.

After each step, the array $virus$ looks as follows:

$[1 , 2 , 3 , 4]$ (initial)
$[3 , 2 , 3 , 4]$
$[3 , 2 , 3 , 2]$
$[3 , 2 , 2 , 2]$
$[2 , 2 , 2 , 2]$

Example 2