One Node is Gone

시간 제한1초메모리 제한1024 MB

요약
주어진 트리가 완전 이진 트리에서 루트가 아닌 정점 하나를 제거해 만들어진 것인지 판정하고, 가능한 제거된 정점의 부모를 모두 구한다.
난이도

어려움10점 중 8점

유형
트리, DFS, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

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

  1. Make a complete and full binary tree of 2n−12^{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 vv from that binary tree.
  3. Remove vv from tree and make new edges between vv's parent and vv's direct children. If vv 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.

입력

The first line contains integer nn (2≤n≤172 \le n \le 17).

The ii-th of the next 2n−32^{n} - 3 lines contains two integers a_ia\_{i} and b_ib\_{i} (1≤a_i<b_i≤2n−21 \le a\_{i} \lt b\_{i} \le 2^{n} - 2) --- meaning there is an edge between a_ia\_{i} and b_ib\_{i}. It is guaranteed that the given edges form a tree.

출력

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 00.

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.

힌트

In the first example, 33 is the only possible answer.

In the second example, there are 22 possible answers.

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

예제3

  1. 예제 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
    3
    
  2. 예제 2

    입력
    2
    1 2
    
    예상 출력
    2
    1 2
    
  3. 예제 3

    입력
    3
    1 2
    2 3
    3 4
    4 5
    5 6
    
    예상 출력
    0