Hiperkocka

문제

...it’s dark in the cube, it’s dark in the cube...

Five in the morning. Daniel wakes up, he opens his eyes. His head hurts a bit. He can still hear the ringing in his ears.

He comes to realize that he has found himself at a playground, in a big metal box.

...I was in the cube, I was in the cube...

He remembers a similar situation he found himself in, three years ago, COCI round 2, task Kocka.

...I’m in the cube again, I’m in the cube again...

But this time, things are much more complicated... Daniel is in an $nn$-dimensional hipercube ${\mathcal{Q}}_n\backslash mathcal\{Q\}\_n$. $2^{n-1}2^\{n-1\}$ identical copies of a tree $\mathcal{T}\backslash mathcal\{T\}$ with $nn$ edges are scattered around him. It soon became clear to him that salvation lies in tiling the edges of the hipercube with the trees.

Formally, a hipercube ${\mathcal{Q}}_n\backslash mathcal\{Q\}\_n$ is a graph with nodes $00$, $11$, $\dots \backslash dots$, $2^n-12^n-1$, in which nodes $xx$ and $yy$ are connected if and only if their bitwise xor is a power of two.

A tree can be placed on the hipercube so that:

• each node of the tree corresponds to some node of the hipercube
• those nodes have to be distinct
• if there is an edge between two nodes in the tree, then there has to be an edge between the corresponding nodes in the hipercube.

A tiling of the hipercube is done by placing several trees so that each edge of the hipercube belongs to at most one tree.

Your task is to tile the hipercube ${\mathcal{Q}}_n\backslash mathcal\{Q\}\_n$ with as many copies of the given tree $\mathcal{T}\backslash mathcal\{T\}$, which has $nn$ edges.

입력

The first line contains a positive integer $nn$ (1 ≤ n ≤ 16), the dimension of the hipercube.

Each of the following $nn$ lines contains two integers $xx$ and $yy$ (0 ≤ x, y ≤ n, $x\mathrm{\ne }yx\; \backslash ne\; y$) which denote that the nodes $xx$ and $yy$ are connected by an edge in tree $\mathcal{T}\backslash mathcal\{T\}$.

출력

In the first line print the number of trees in your tiling.

Each of the following lines should describe a placement of a single copy of the tree $\mathcal{T}\backslash mathcal\{T\}$.

In the $ii$-th line print $n+1n\; +\; 1$ numbers $a_0^{(i)}a\_0^\{(i)\}$, $a_1^{(i)}a\_1^\{(i)\}$, $\dots \backslash ldots$ $a_n^{(i)}a\_n^\{(i)\}$. These numbers denote that the $ii$-th tree is placed so that the hipercube node $a_j^{(i)}a\_j^\{(i)\}$ corresponds to the tree node $jj$, for all $j=0,\dots ,nj\; =\; 0,\; \backslash dots\; ,\; n$.

힌트

Clarification of the third example:

1
0 1

1
0 1

2
0 1
1 2

2
0 1 3
0 2 3

3
0 1
0 2
0 3

4
0 1 2 4
3 1 2 7
5 1 4 7
6 2 4 7