问题 25206 --砍树

25206: 砍树

时间限制: 1 Sec  内存限制: 128 MB
提交: 141  解决: 31
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][59168kb]

题目描述

 给出一个树形图(“tree-shaped network,N个顶点。如果删除树上某一个顶点,整棵树就会分割成若干个部分。显然,每个部分内部仍保持连通性。

现在问:删除哪个点,使得分割开的每个连通子图中点的数量不超过N/2?如果有很多这样的点,就按升序输出。

    例如,如下图所示的树形图,砍掉顶点3或者顶点8,分割开的各部分满足条件。

 

输入

 1行:1个整数N,表示顶点数。顶点编号1-N    接下来n-1行每行两个整数x,y,表示xy有一条边。

输出

 若干行,每行1个整数,表示一个符合条件的顶点的编号。如果没有顶点符合条件,则仅在第1行输出“NONE”。

样例输入

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

样例输出

3
8

提示

 


【数据范围及约定】



对于50%的数据,满足1N10000



对于100%的数据,满足1N1000000

来源

[提交][状态]