Maximum Minimum Subtree After Node Removal

You are given a tree with (n) nodes and (n-1) edges. Imagine that by removing exactly one node from the tree, the tree splits into several connected components (subtrees). Equivalently, consider removing one edge, which disconnects the tree into two subtrees, and let (\min(a, b)) denote the size of the smaller subtree when the tree is split into two parts of sizes (a) and (b). Your task is to determine the maximum possible value of (\min(a, b)) over all possible removals. This problem requires efficient tree traversal techniques and the use of depth first search (DFS) to compute the sizes of subtrees.

Note: All formulas are provided in ( \LaTeX ) format. For example, for a given removal resulting in two subtrees of sizes (a) and (b), the candidate value is (\min(a, b)).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) (the number of nodes). Each of the next (n-1) lines contains two space-separated integers (u) and (v) indicating that there is an edge between nodes (u) and (v). It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer to standard output (stdout), representing the maximum possible value of (\min(a, b)) after removing exactly one node (equivalently, breaking one edge) from the tree.## sample

5
1 2
1 3
1 4
4 5

2