Description

Given a tree with $n$ nodes, find a node such that when this node is chosen as the root, the sum of depths of all nodes is maximized.

The depth of a node is defined as the number of edges on the simple path from that node to the root.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.
The next $(n - 1)$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

Output Format

This problem uses Special Judge.

Output one line with an integer, the index of the chosen node. If multiple nodes satisfy the requirement, output any one of them.

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

7

Hint

Sample 1 Explanation:

Outputting $7$ or $8$ are both correct answers.

Constraints:

For all test points, it is guaranteed that $1 \leq n \leq 10^6$, $1 \leq u, v \leq n$, and the input is a tree.

Translated by ChatGPT 5