You have an integer $n$. Let's define following tree generation as McDic's generation:  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.  Select a non-root vertex $v$ from that binary tree.  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-----

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

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.


-----Examples-----
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

Output
1
3

Input
2
1 2

Output
2
1 2

Input
3
1 2
2 3
3 4
4 5
5 6

Output
0



-----Note-----

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

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

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

Difficulty: interview

Starter code:

Solutions:
3

import array
import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, M, G):
    if N == 2:
        return [0, 1]

    degv = [set() for _ in range(5)]
    for i in range(M):
        d = len(G[i])
        if d == 0 or d >= 5:
            return []
        degv[d].add(i)

    layer_vcount = 1 << (N - 1)
    vs = degv[1]
    levels = bytearray(M)
    ans = []
    for level in range(1, N):
        #dprint('level', level, [x for x in levels])
        #dprint('vs', vs)
        #dprint('layer_vcount', layer_vcount)

        if len(vs) not in (layer_vcount - 1, layer_vcount):
            return []
        if len(vs) == layer_vcount - 1:
            if ans:
                return []
            if level == 1:
                sp_deg_off = -1
            else:
                sp_deg_off = 1
        else:
            sp_deg_off = 0
        #dprint('sp_deg_off', sp_deg_off)

        ndeg = 3 if level < N - 1 else 2
        us = set()
        ss = set()

        for v in vs:
            #dprint('v', v)
            levels[v] = level
            p = None
            for u in G[v]:
                if levels[u] == 0:
                    if p is not None:
                        return []
                    p = u
                    break
            #dprint('  p', p)
            if p is None:
                return []
            deg = len(G[p])
            #dprint('  deg', deg)

            if deg == ndeg:
                us.add(p)
            elif deg == ndeg + sp_deg_off:
                ss.add(p)
            elif sp_deg_off == 0 and deg == ndeg + 1:
                ss.add(p)
            else:
                return []

        #dprint('us', us)
        #dprint('ss', ss)

        if sp_deg_off != 0:
            if len(ss) != 1:
                return []
            (sp,) = list(ss)
            ans = [sp]
            us.add(sp)

        if sp_deg_off == 0:
            if level == N - 2:
                if ss:
                    return []
                if not ans:
                    li = list(us)
                    li.sort()
                    return li
            if len(ss) > 1:
                return []

        vs = us
        layer_vcount >>= 1

    return ans


def main():
    N = int(inp())
    M = (1 << N) - 2
    G = [[] for _ in range(M)]
    for _ in range(M - 1):
        a, b = [int(e) - 1 for e in inp().split()]
        G[a].append(b)
        G[b].append(a)

    ans = solve(N, M, G)
    print(len(ans))
    if ans:
        print(*[v + 1 for v in ans])


def __starting_point():
    main()

__starting_point()

3

import array
import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, M, G):
    if N == 2:
        return [0, 1]

    degv = [set() for _ in range(5)]
    for i in range(M):
        d = len(G[i])
        if d == 0 or d >= 5:
            return []
        degv[d].add(i)

    layer_vcount = 1 << (N - 1)
    vs = degv[1]
    levels = [0] * M
    ans = []
    for level in range(1, N):
        #dprint('level', level, [x for x in levels])
        #dprint('vs', vs)
        #dprint('layer_vcount', layer_vcount)

        if len(vs) not in (layer_vcount - 1, layer_vcount):
            return []
        if len(vs) == layer_vcount - 1:
            if ans:
                return []
            if level == 1:
                sp_deg_off = -1
            else:
                sp_deg_off = 1
        else:
            sp_deg_off = 0
        #dprint('sp_deg_off', sp_deg_off)

        ndeg = 3 if level < N - 1 else 2
        us = set()
        ss = set()

        for v in vs:
            #dprint('v', v)
            levels[v] = level
            p = None
            for u in G[v]:
                if levels[u] == 0:
                    if p is not None:
                        return []
                    p = u
                    break
            #dprint('  p', p)
            if p is None:
                return []
            deg = len(G[p])
            #dprint('  deg', deg)

            if deg == ndeg:
                us.add(p)
            elif deg == ndeg + sp_deg_off:
                ss.add(p)
            elif sp_deg_off == 0 and deg == ndeg + 1:
                ss.add(p)
            else:
                return []

        #dprint('us', us)
        #dprint('ss', ss)

        if sp_deg_off != 0:
            if len(ss) != 1:
                return []
            (sp,) = list(ss)
            ans = [sp]
            us.add(sp)

        if sp_deg_off == 0:
            if level == N - 2:
                if ss:
                    return []
                if not ans:
                    li = list(us)
                    li.sort()
                    return li
            if len(ss) > 1:
                return []

        vs = us
        layer_vcount >>= 1

    return ans


def main():
    N = int(inp())
    M = (1 << N) - 2
    G = [[] for _ in range(M)]
    for _ in range(M - 1):
        a, b = [int(e) - 1 for e in inp().split()]
        G[a].append(b)
        G[b].append(a)

    ans = solve(N, M, G)
    print(len(ans))
    if ans:
        print(*[v + 1 for v in ans])


def __starting_point():
    main()

__starting_point()