#YHNO5042. 树的中心

树的中心

题目:树的中心

题目描述

  • 已知一棵树包含 n 个结点,结点编号范围是从 1n。树的中心定义为:该结点距离树中其他所有结点的最远距离是最近的。要求根据给定的树的相关信息,求出树的中心结点编号。若存在多个中心结点,则需按照从小到大的顺序输出这些中心结点的编号。
  • 给出了相应示例树及示例树中的中心结点情况,便于直观理解树的中心这一概念。

输入

  • 第一行:输入一个整数 nn ≤ 10^5),用于表示树中结点的数量。
  • 接下来的 n - 1 行:每行包含两个整数 xy,表示结点 x 与结点 y 之间存在一条边,这里并不确定结点之间的父子关系。

输出

输出树的中心结点的编号,若有多个,按从小到大的顺序依次输出各中心结点编号。

样例

  • 输入示例
5
2 1
1 3
3 4
3 5
  • 输出示例
1 3