Minimizing Tree Diameter by Edge Replacement

You are given a tree with n nodes and all edge weights equal to 1. You are allowed to remove exactly one edge and add exactly one edge (between any two nodes from different resulting components) such that the resulting structure is still a tree. Your goal is to minimize the diameter of the new tree.

The diameter of a tree is defined as the maximum distance between any two nodes. In this problem, distance is the sum of the weights along the unique simple path connecting two nodes.

Hint: Suppose you remove an edge and obtain two trees T₁ and T₂. Let the diameter of T₁ be \(d_1\) and that of T₂ be \(d_2\). If we connect a center of T₁ with a center of T₂, then the diameter of the new tree will be

[ \max\Bigl(d_1,,d_2,,\Bigl(\Bigl\lceil\frac{d_1}{2}\Bigr\rceil + \Bigl\lceil\frac{d_2}{2}\Bigr\rceil + 1\Bigr)\Bigr) ]

Your task is to determine the minimum possible diameter achievable by performing such an edge replacement.

inputFormat

The first line contains an integer n (n \(\geq 2\)), representing the number of nodes in the tree.

Each of the following n-1 lines contains two integers u and v (1 \(\leq u,v \leq n\)), indicating an edge between nodes u and v.

The nodes are numbered from 1 to n.

outputFormat

Output a single integer, the minimum diameter achievable after removing one edge and adding one edge optimally.

sample

3
1 2
2 3

2