Algorithms and Data Structures

# Find the Centroid of a Tree

You are given a tree with v vertices and your task is to find the centroid of the tree. The centroid of a tree is a vertex such that when it is removed, all the remaining subtrees have a size of at most nodes.

#### Input

The first line of the input contains a single integer v (1 ≤ v ≤ 100 000).
The following v-1 lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

#### Output

The program should print the centroid of the given tree. If there are several possible answers, the program can print any of them.

#### Examples

 Input Output 3 1 2 1 3 1 5 1 2 2 3 3 4 3 5 3
Hint
You can calculate the size of the subtree for each node (the number of child nodes).
Then, check for all the subtrees of each node if their size is smaller or equal to half of the vertices in the whole tree (all the child nodes and v-currentNodeSize to account for the parent subtree).

#### Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB