← 返回题目列表

Codeforces · 1228/F

F. 一个节点消失了

中文机器翻译题面 查看原题

你有一个整数$$$n$$$。让我们将以下树生成定义为 McDic 生成:

1. 制作一棵由 $$$2^{n} - 1$$$ 个顶点组成的完整二叉树。完全二叉树是指一棵树中只有一个顶点是根,所有叶子都具有相同的深度(距根的距离),并且所有非叶子节点恰好有两个子节点。
2. 从该二叉树中选择一个非根顶点 $$$v$$$。
3. 从树中删除 $$$v$$$ 并在 $$$v$$$ 的父级和 $$$v$$$ 的直接子级之间创建新边。如果 $$$v$$$ 没有子节点,则不会创建新的边。

你有一棵树。确定这棵树是否可以由 McDic 一代制作。如果是,则在树中查找被移除顶点的父顶点。

输入

第一行包含整数 $$$n$$$ ($$$2 \le n \le 17$$$)。

接下来的 $$$2^{n} - 3$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_{i}$$$ 和 $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le 2^{n} - 2$$$) - 意味着之间有一条边$$$a_{i}$$$ 和 $$$b_{i}$$$。保证给定的边形成一棵树。

输出

打印两行。

在第一行中,打印一个整数 - 答案数。如果给定的树不能由 McDic 一代生成,则打印 $$$0$$$。

在第二行中,按升序打印所有可能的答案,并用空格分隔。如果给定的树不能由 McDic 一代制作,则不要打印任何内容。

示例

输入 #1

4
1 2
1 3
2 4
2 5
3 6
3 13
3 14
4 7
4 8
5 9
5 10
6 11
6 12

输出 #1

1
3

输入 #2

2
1 2

输出 #2

2
1 2

输入 #3

3
1 2
2 3
3 4
4 5
5 6

输出 #3

0

注意

在第一个示例中,$$$3$$$ 是唯一可能的答案。

在第二个示例中,有 $$$2$$$ 可能的答案。

在第三个示例中,McDic 的生成无法生成树。