...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 \(n-di\)mensional hipercube \(Q@@RISE_MATH_BLOCK_0@@n\) is a graph with nodes 0, 1, . . . \(2^{n} - 1\), in which nodes \(x\) and \(y\) 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 \(Q\)\(n\) with as many copies of the given tree \(T\) , which has \(n\) edges.

If your solution correctly places \(k\) trees, you will receive \(f\)(\(k\)) · 110 points for that test case, where
\(f\)(\(k\)) =
(
0.\(7 \cdot k/2^{n}\)^{−}
if \(k < 2^{n}\)^{−}
1
if \(k = 2^{n}\)^{−}.
Of course, if your solution is not correct, you will receive 0 points.
Your total number of points is equal to the minimum number of points your solution receives over all of
the test cases.
It is possible to prove that there always exists a solution which uses all of the \(2^{n}\)^{−} trees.

The first line contains a positive integer \(n\) (\(1 \le n \le 16\)), the dimension of the hipercube.
Each of the following \(n\) lines contains two integers \(x\) and \(y\) (\(0 \le x\), \(y \le n\), \(x\)̸ = \(y\)) which denote that the
nodes \(x\) and \(y\) are connected by an edge in tree \(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 \(T\) .
In the \(i-th\) line print \(n + 1\) numbers \(a\)^{(}}^{)
0 ^{, a}^{(}}^{)
1 ^{. . . a}^{(}}^{)
\(n\) ^{.} ^{These} ^{numbers} ^{denote} ^{that} ^{the} ^{i}} ^{tree} ^{is} ^{placed} ^{so
that the hipercube node \(a\)^{(}}^{)
\(j\)
corresponds to the tree node \(j\), for all \(j = 0\), . . . , n.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 2