题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Stacja

拜托西亚的铁路网络是一个树结构（任意两个车站间有唯一路径，无环）。需选择一个车站作为枢纽 Bitowice，从其他所有车站车站开通到该枢纽的往返连接。两车站间的通行成本为到达对方所需的最小连接次数（即途经的连接数）。目标是选择使所有不同车站对的平均通行成本最小的枢纽。

输入格式

1. 第一行：整数 n（2 ≤ n ≤ 1000000），表示火车站数量；
2. 接下来 n-1 行：每行两个正整数 a 和 b（1 ≤ a < b ≤ n），表示连接车站 a 和 b 的轨道段。

输出格式

输出一行整数，表示作为 Bitowice 的最佳车站编号（若有多个，输出任意一个）。

样例

输入

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

输出

7

图中圆圈代表车站（圆圈内的数字为车站编号），边代表轨道段。Bitowice 的最佳位置可以是车站 7 或 8。