Extra
Time
2015.8.12 noip模拟赛——二叉树的根 Time:1s Memory:50M AC:15% Submit:20

题目描述

什么叫二叉树?这个应该是每个人都知道的。在本题
中,我们的二叉树是有根的:对于每个节点,它至多有左右
两个子节点(可以为空),并且每个子树也都是二叉树。如
果无视有根二叉树中的父子关系,那么它就变成了无根树。
现在我们给出任意的无根树,想让你找到这样的节点:存在
某个有根二叉树的根为这个节点,且无视有根二叉树中的父
子关系后,所变成的无根树恰好为给出的无根树。
由于有可能无解,也有可能有很多解,你需要对这些情况作
出判断。

输入格式

第一行为一个正整数 n,代表树中点的个数。
接下来 n-1 行,每行一对非负整数 a[i],b[i],表示
a[i]与 b[i]之间连有一条边。

输出格式

第一行为一个非负整数,表示解的数量。
如果解的数量不为 0,那么第二行有若干正整数,每
个表示一个答案,且按升序排列。

样例输入

样例输入 1

3
1 2
2 3

样例输出 1

3
1 2 3

样例输入 2

4
1 2
1 3
1 4

样例输出 2

3
2 3 4

数据范围与约定

对于 20%的数据,n≤3。
对于 40%的数据,n≤4。
对于 60%的数据,n≤100。
对于 80%的数据,n≤1,000。
对于 100%的数据,n≤100,000。

样例解释

对于第一个样例,任意一个节点都可以成为根,使得
树成为二叉树。
对于第二个样例,如果以节点 1 为根,那么它就会有
3 个子节点,破坏了二叉树性质。而对于其余节点都是可行
的。