题目描述

农夫约翰意识到贝茜以惊人的成本在他的(N)（(1 ≤ N ≤ 10000)）个谷仓间安装了一个“树状”网络后，起诉了贝茜以减少损失。

心怀怨恨的贝茜决定通过切断某个谷仓的电源来破坏农夫约翰的网络（从而中断所有涉及该谷仓的连接）。当贝茜这样做时，网络会被分割成更小的部分，每个部分内部仍保持完全连通。为了尽可能造成破坏，贝茜希望确保这些部分中每个部分连接的谷仓数量不超过约翰谷仓总数的一半。

请帮助贝茜确定所有适合切断连接的谷仓。

输入

第 1 行：一个整数(N)，谷仓编号为(1)到(N)。

第 2 行到第(N)行：每行包含两个整数(X)和(Y)，表示谷仓(X)和谷仓(Y)之间有连接。

输出

第 1 行到若干行：每行包含一个整数，是一个谷仓的编号（从(1)到(N)），移除该谷仓会将网络分割成若干部分，且每个部分的谷仓数量最多为原谷仓总数的一半。按编号升序输出谷仓编号。如果没有合适的谷仓，输出应是单独一行，包含单词“NONE”。

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

3
8

提示

输入详情：

输入中的连接集合描述了一个“树”：它将所有谷仓连接在一起且没有环。

输出详情：

如果移除谷仓 3 或谷仓 8，那么剩余的网络将有一个由 5 个谷仓组成的部分和两个由 2 个谷仓组成的部分。如果移除任何其他谷仓，那么至少有一个剩余部分的大小至少为 6（超过原谷仓总数 10 的一半）。

来源

USACO 2004 年 12 月银牌赛