Problems
Find the centroid
Find the centroid
Find any centroid in the tree.
\InputFile
The first line contains one integer $n$ $(1 ≤ n ≤ 2 · 10^5)$ — the number of vertices. Each of the following $n − 1$ lines contains two integers $v_i$ and $u_i$ $(1 ≤ v_i$ , $u_i ≤ n)$ - vertices connected with an edge.
It is guaranteed that this graph is a tree.
\OutputFile
Print the number of the vertex that is the centroid. If there are several centroids, print any one.
\includegraphics{https://static.eolymp.com/content/fs/fsn3om7lol7tr7jrord7fd4744.gif}
Input example #1
12 1 3 2 3 3 4 4 5 4 6 6 7 6 10 10 11 10 12 6 8 8 9
Output example #1
6