2250: 黑手党

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

    去年的芝加哥充满了黑帮争斗和奇怪的谋杀。警察局长真的厌倦了所有这些罪行,决定逮捕黑手党领袖。
    不幸的是,芝加哥黑手党相当复杂的结构。没有人知道黑手党的信息。警方已经追踪他们一段时间的活动,并且知道他们中的一些人互相通信。根据收集到的资料,警察局长表明黑手党的层次结构可以表示为一棵树。黑手党首脑是树的根,每个节点表示一个人,一个节点的孩子即为这个节点表示的人的直接下属。
    更不幸的是,虽然警方知道了匪徒的通讯,他们不知道谁是黑手党首脑。因此他们只有通信关系的无向树。
    基于这样的思想,警察局长猜测可能表示黑手党首脑的节点必须满足:在删除它后,包含最多节点的剩余连通块的节点数最小。帮助警察找到所有可能成为黑手党首脑的节点。

输入格式

    第一行包含一个整数n(2≤n≤50000),表示有n个人,编号为1~n。
    接下来n-1行,每行两个数x,y,表示编号为x的人和编号为y的人之间有通信。

输出格式

输出所有可能成为黑手党首脑的人的编号,按升序排列,两个编号之间用空格隔开。

输入样例 复制

6
1 2
2 3
2 5
3 4
3 6

输出样例 复制

2 3