Splitting Trees (4 Points)

Problem Statement

You are given a tree with $n$ nodes labelled $1$ to $n$ and is rooted at node $1$. For $1 \leq u \leq n$ we define $|u|$ to be the size (number of nodes) of the subtree rooted at $u$. You are to perform the following operation:

• Pick a node $u$ such that one of its children $v$ have the property $|u| \leq 2 \cdot |v|$
• Change the parent of either $u$ or $v$ to be any $w$ where $1 \leq w \leq n$ and such that the tree remains a tree.

After performing any number of operations, determine the smallest length you can make the diameter.

Recall the definition of a tree is a connected graph with no cycles. Recall the diameter of the tree is defined to be the largest distance between any two nodes in the tree, and the distance between two nodes in a tree is the number of edges on the (only) path between those two nodes.

Input Format

Your first line will contain $n$, the number of nodes. Your next $n - 1$ lines will contain two space-separated integers each, $u$ and $v$, meaning there is an edge between $u$ and $v$.

Output Format

Output a single integer representing the smallest length you can make the diameter.

Constraints

• $1 \leq n \leq 10^5$

Sample Cases

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

2

5
1 2
1 3
3 4
3 5

3

10
1 2
1 3
1 4
1 5
1 6
1 7
7 8
7 9
7 10

3