Optimal House Selection

In Toyland, houses are connected in a tree structure. The local council has decided to build a new playground, and they want to choose the house such that the maximum size of any connected component (formed when that house is removed) is minimized. This special house is the centroid of the tree.

A node \(v\) in a tree with \(n\) nodes is called a centroid if after its removal, every connected component has at most \(\lfloor n/2 \rfloor\) nodes. It can be shown that every tree has at least one centroid. Given the number of houses and the roads connecting them, your task is to compute the centroid and thus determine the optimal house for building the playground.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of houses.
• The next \(n-1\) lines each contain two space-separated integers \(u\) and \(v\) (\(1 \le u, v \le n\)) representing a bidirectional road connecting house \(u\) and house \(v\).

outputFormat

Output a single integer to stdout representing the optimal house (centroid) for building the playground.

5
1 2
1 3
3 4
3 5

3