你有一个整数$$$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 的生成无法生成树。