One Node is Gone
Contest: Codeforces Round 589 (Div. 2)
Difficulty rating: 2500
Tags: constructive algorithms, implementation, trees

You have an integer $$$n$$$. Let's define following tree generation as McDic's generation:

1. Make a complete and full binary tree of $$$2^{n} - 1$$$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.
2. Select a non-root vertex $$$v$$$ from that binary tree.
3. Remove $$$v$$$ from tree and make new edges between $$$v$$$'s parent and $$$v$$$'s direct children. If $$$v$$$ has no children, then no new edges will be made.

You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.

Input format:
The first line contains integer $$$n$$$ ($$$2 \le n \le 17$$$).

The $$$i$$$-th of the next $$$2^{n} - 3$$$ lines contains two integers $$$a_{i}$$$ and $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le 2^{n} - 2$$$) — meaning there is an edge between $$$a_{i}$$$ and $$$b_{i}$$$. It is guaranteed that the given edges form a tree.

Output format:
Print two lines.

In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $$$0$$$.

In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$3$$$ is the only possible answer.

In the second example, there are $$$2$$$ possible answers.

In the third example, the tree can't be generated by McDic's generation.

Example input:
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

Example output:
1
3

Example input:
2
1 2

Example output:
2
1 2

Editorial:
Let me suggest this observation;
• Root of generated tree should be one of middle of diameter. Because only $$$1$$$ node is deleted from complete full binary tree.
So there are $$$3$$$ valid cases;
• The removed node is child of root. In this case, there are $$$2$$$ answers($$$2$$$ center nodes), diameter is decreased by $$$1$$$ (odd), and tree looks like two complete full binary trees' roots are connected. You have to check if two center's subtrees are complete full binary tree.   In this case, there are $$$2$$$ answers, which are $$$2$$$ centers of diameter.
• The removed node is leaf($$$n \gt 2$$$) or normal node. In this case, there is only $$$1$$$ answer and $$$1$$$ root node. Check if whole tree is complete full binary tree with $$$1$$$ node error toleration. You can do case-handling by degree of nodes.  If non-root has degree $$$3$$$, then this node is normal.  If non-root has degree $$$2$$$ (error), then this node should be parent of removed leaf. You should check if this node's child node is leaf.  If non-root has degree $$$1$$$, then this node should be leaf.  If non-root has degree $$$4$$$ (error), then this node should be parent of removed normal node. This is the hardest case. I did this by checking depth of each child's subtree using DFS, then consider each tree to be complete and binary tree with no error, but with different depths. If you encountered multiple error nodes, then this tree is invalid. To check my exact approach, please look at my code.    In these cases, we can fix the center of whole tree by center of diameter.
• If non-root has degree $$$3$$$, then this node is normal.
• If non-root has degree $$$2$$$ (error), then this node should be parent of removed leaf. You should check if this node's child node is leaf.
• If non-root has degree $$$1$$$, then this node should be leaf.
• If non-root has degree $$$4$$$ (error), then this node should be parent of removed normal node. This is the hardest case. I did this by checking depth of each child's subtree using DFS, then consider each tree to be complete and binary tree with no error, but with different depths.
To check if specific subtree is complete and full binary tree, you can use top-down recursive approach. Maybe you can use bottom-up approach by collapsing leaf nodes too, but it's very hard(at least I think) to check all conditions strictly.
Time complexity is $$$O(2^{n})$$$. But you can solve this in like $$$O(n \cdot 2^{n})$$$ or something bigger one.