Optimal Sky Bridge Construction

You are given a tree structure representing a network of skyscrapers connected via sky bridges. The tree has n nodes (skyscrapers) and n - 1 bridges connecting them. Your task is to add a set of new sky bridges optimally so that the maximum distance between any two skyscrapers is minimized. It turns out that the optimal maximum distance will be the ceiling of half of the diameter of the tree. In mathematical terms, if the diameter of the tree is \(d\), the answer is \(\lceil d/2 \rceil\) which can be computed as \(\frac{d+1}{2}\) using integer division.

The input starts with an integer n representing the number of skyscrapers, followed by n - 1 pairs of integers \(u\) and \(v\) that denote a bidirectional sky bridge between skyscraper \(u\) and skyscraper \(v\).

Your program should compute and output the minimum possible maximum distance between any two skyscrapers after adding the new bridges optimally.

inputFormat

The first number is an integer n (number of skyscrapers). This is followed by exactly n - 1 pairs of integers. Each pair \(u\) \(v\) indicates there is a direct sky bridge connecting skyscraper \(u\) and skyscraper \(v\).

All numbers are separated by spaces or newlines.

outputFormat

Output a single integer: the minimal possible maximum distance, which is computed as \(\lceil\frac{\text{diameter}}{2}\rceil\).

5 1 2 1 3 3 4 3 5

2