23522번 - Make Spoiled Binary Tree a Tree Again! 스페셜 저지다국어

문제

John had a beautiful complete binary tree with exactly 2ドル^k$ leaves. Once he walked through his garden, and to his grave disappointment, there was a path going through all the leaves of his beautiful binary tree!

The vertices of John's tree are numbered such that the root has number 1ドル,ドル and the direct successors of a vertex number $i$ are the vertices with numbers 2ドルi$ and 2ドルi + 1$. The new path spoiling John's tree consists of edges $(v, v + 1)$ for all consecutive pairs of leaves: more precisely, edges $(2^k, 2^k + 1), (2^k + 1, 2^k + 2), \ldots, (2^{k + 1} - 2, 2^{k + 1} - 1)$. John denoted the set of vertices of his tree as $V$ and the set of edges (including the spoiling path) as $E$.

John thought very hard about this problem and came up with a solution: he is going to merge some vertices of his spoiled binary tree such that the result is a tree (though not necessarily binary) again.

Formally, John will partition all vertices of his binary tree into disjoint sets $S_1, \ldots, S_m$. After that, for each set $S_i,ドル he will merge all vertices in it into a single new vertex $i$. In the graph with new vertices $\{1, \ldots, m\},ドル an edge between $i$ and $j$ exists if and only if in the original graph, there was an edge between some vertex from $S_i$ and some vertex from $S_j$.

John wants to find such sets $S_1, \ldots, S_m$ that the new graph is a tree. Additionally, in order to make the tree beautiful, John wants the sets to be small enough: precisely, $|S_i| \le 8 k$ for all $i \in \{1, \ldots, m\}$. Help him find such sets.

입력

The only line contains a single integer $k$ (1ドル \le k \le 20$).

출력

On the first line, print an integer $m$ (1ドル \le m \le 2^{k+1} - 1$): the number of sets of vertices John would like to have. In each of the next $m$ lines, print the size of the set, and then print the vertices in that set in any order. Each vertex of the tree should belong to exactly one of the printed sets, and the new graph with merged vertices should be a tree, as described in the statement.

제한

힌트