Trees

Task

Little Tree is interested in trees of various sizes. She has a rooted binary tree $T$ (i.e.~one where every vertex has at most 2 children), not necessarily a balanced tree, in front of her, whose root is denoted by $1$ and whose vertices are labeled $1, \ldots, 2^N$. The label of any vertex is always strictly less than any of its children.

A set of vertices $S$ is called valid if no vertex in $S$ is the ancestor of any other vertex in $S$. The value of $S$, denoted by $\text{val}(S)$, is given by the number of vertices within the tree that have any vertex of $S$ as an ancestor. (We consider a node to be its own ancestor.) In other words, it is the sum of the sizes of the subtrees rooted at vertices in $S$.

Her enemy, Little Cactus, challenges her to the following task: Given $N$ and the tree $T$, create as many valid, nonempty sets $S_1, \ldots, S_K$ as possible, such that

and $\text{val}(S_i) \neq \text{val}(S_j)$ for any $i \neq j$.

Input data

The first line of the input file contains the integer $N$. The second line contains integers $p_2, \ldots, p_{2^N}$, separated by spaces, where $p_i$ denotes the parent of node $i$.

Output data

Output $K$, the number of sets you can create, followed by each of the $K$ sets on its own line. To output a set, first output its size, then its elements, separated by spaces.

Constraints and clarifications

• $N \leq 18$.
• If you output an incorrect solution (i.e.~one using too many vertices, or where two sets have the same value) then you will receive 0 points for a test. Otherwise, the fraction of the score you will receive for a particular test will be equal to $(K / 2^N)^{1.5}$.

Example 1

stdin

2
1 2 3

stdout

4
1 4
1 3
1 2
1 1

Explanation

The tree is given by

We see that the sets $S_1 = \{ 4 \}$, $S_2 = \{3\}$, $S_3 = \{2 \}$, $S_4 = \{1 \}$ all have distinct values (namely 1, 2, 3, 4 respectively), and have total size $4 \leq 2 \times 2^{2 - 1} + 1 = 5$. Hence this output is correct.

Example 2

stdin

2
1 2 2

stdout

4
1 4
2 3 4
1 2
1 1

Explanation

The tree is given by

We see that the sets $S_1 = \{ 4 \}$, $S_2 = \{3, 4\}$, $S_3 = \{2\}$, $S_4 = \{1\}$ all have distinct values (namely 1, 2, 3, 4 respectively), and have total size $5 \leq 2 \times 2^{2 - 1} + 1 = 5$. Hence this output is correct.