Maximize Total Depth in a Tree by Choosing the Optimal Root

You are given an undirected tree with n nodes. A tree is a connected graph with no cycles. Your task is to choose a node such that when the tree is rooted at that node, the sum of the 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. In other words, if a node is the root, its depth is 0; its direct children have depth 1; their children have depth 2; and so on.

If there are multiple nodes that yield the same maximum sum of depths, you may output any one of them.

Note: The tree is given as an undirected graph with n nodes and n-1 edges.

inputFormat

The first line contains an integer n (the number of nodes in the tree).

Each of the following n-1 lines contains two space-separated integers u and v representing an undirected edge between nodes u and v.

outputFormat

Output a single integer representing the index of the node which yields the maximum sum of depths when used as the root. If there are multiple valid answers, output any one of them.

sample

3
1 2
2 3

1