[石门中学2009]切割树

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 treecut.in 输出文件 treecut.out

treecut

题目描述：

  有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。 

数据范围

   1 <= N <= 10,000

输入文件 treecut.in

  第一行：一个整数N。

  后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。

输出文件 treecut.out

   输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行："NONE".

样例

输入

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

样例说明：

删除3号或8号

节点，则分枝

最多有5个节点

 

输出

3
8