[AdditionalFile5352.zip](file://AdditionalFile5352.zip?type=additional_file)

#5352. 「POI2008 R3」车站 Station

标签: 传统 | 时间限制: 2500 ms | 内存限制: 192 MiB |

题目描述

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

在拜托西亚，铁路网络改革的第一阶段已经完成。该网络由连接火车站的双向轨道段组成。任意两个车站之间最多只有一条轨道段连接。此外，已知从任意一个火车站可以通过唯一一条路线到达其他任意火车站。路线可能由多个轨道段组成，但从不会经过同一个车站超过一次。

改革第二阶段的目标是规划铁路连接。Bajtazar 希望你能帮助他完成这一任务。为了简化问题，Bajtazar 决定：

• 其中一个车站将成为大型铁路枢纽，并命名为 Bitowice，
• 从其他所有车站将开通到 Bitowice 的往返铁路连接，
• 每列火车将在 Bitowice 和另一个终点站之间运行，沿唯一可能的路线行驶，并在途经的所有车站停靠。

现在的问题是，应该选择哪个车站作为 Bitowice。决策标准是，连接系统应设计为使不同火车站之间的平均通行成本最小。在拜托西亚，只使用单程票，票价为 $1$ 拜塔拉尔（bajtalar），允许乘坐任意距离的单次连接。因此，两个特定车站之间的通行成本是到达对方所需使用的最小连接次数。

编写一个程序，完成以下功能：

• 从标准输入读取拜托西亚铁路网络的描述，
• 确定应作为 Bitowice 的车站，
• 将结果输出到标准输出。

输入格式

输入数据的第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示火车站的数量。火车站编号为 $1$ 到 $n$。有 $n-1$ 个轨道段连接这些车站。接下来的 $n-1$ 行，每行描述一个轨道段。每行包含两个正整数 $a$ 和 $b$ $(1 \leq a < b \leq n)$，用单个空格分隔，表示连接车站 $a$ 和 $b$ 的轨道段。

输出格式

第一行且仅一行输出一个整数，表示作为 Bitowice 的最佳车站位置。如果存在多个最佳答案，你可以输出其中任意一个。

样例

输入

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

输出

7

图中圆圈代表车站（圆圈内的数字为车站编号），边代表轨道段。Bitowice 的最佳位置可以是车站 $7$ 或 $8$。选择其中任意一个时，不同车站之间的平均通行成本为 $\frac{36}{28} \approx 1.2857$（样例中有 $28$ 对无序的不同车站对）。