In the kingdom of Arbolia, $n$ cities are connected by roads. There is exactly one simple route between any two cities, so the road network forms a tree.

Mira wants to compress this network into a single super-city. She may repeatedly merge any two distinct cities into one new city, even if they are not directly connected by a road.

During this process, every pair of remaining cities has one of three possible relationships:

• a black edge,
• a red edge, or
• no edge.

Initially, every road is a black edge, all other pairs have no edge, and there are no red edges.

Suppose Mira merges cities $u$ and $v$ into a new city $w$. For each other remaining city $x$, the relationship between $w$ and $x$ is determined as follows:

• If at least one of the relationships $(u,x)$ or $(v,x)$ is a red edge, $(w,x)$ becomes a red edge.
• Otherwise, if both relationships are black edges, $(w,x)$ is a black edge.
• Otherwise, if both relationships have no edge, $(w,x)$ has no edge.
• In all other cases, $(w,x)$ becomes a red edge.

The two old cities and all their relationships disappear after the merge.

The red degree of a city is the number of red edges incident to it. Mira wants to merge all cities into one while keeping the red degree of every city, at every moment, as small as possible.

Find the smallest integer $d$ for which Mira can perform all merges without any city ever having red degree greater than $d$.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$) --- the number of cities.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$), describing a road between cities $u$ and $v$.

It is guaranteed that the given roads form a tree.

Output

Print a single integer: the minimum possible value of $d$.

Example

stdin

4
4 3
2 1
4 2

stdout

1

Note

In the first example, there are $4$ cities connected by $3$ roads: $(4,3)$, $(2,1)$, and $(4,2)$. These roads form the path $1 - 2 - 4 - 3$.

The answer is $1$, meaning that it is possible to merge all cities into a single city while ensuring that, at every moment, each remaining city has at most one incident red edge.

However, it is impossible to complete the process without creating any red edges. Therefore, the minimum possible value of $d$ is $1$.