Problem Description

You are given an $n$-dimensional hypercube.

Abstract the hypercube as a graph with $2^n$ vertices, labeled $0,1,\cdots,2^n-1$. Two vertices $x,y$ are connected if and only if $x \oplus y$ is an integer power of $2$.

Now you need to place several trees $T$, each with $n$ edges, into this hypercube. The vertices of each tree are labeled $0,1,\cdots,n$. You are given the endpoints of the $n$ edges of the tree. Each placed tree must satisfy all of the following conditions:

• Each vertex in the tree corresponds one-to-one to a vertex of the hypercube.
• All corresponding hypercube vertices are distinct.
• For every edge in the tree, the two corresponding hypercube vertices are connected by an edge in the hypercube (i.e., the XOR of the two corresponding vertex labels is an integer power of $2$).
• The edge sets of any two trees, after being mapped into the hypercube, are disjoint. That is, each edge of the hypercube can belong to at most one tree.

You need to output a placement scheme so that every tree placed in the hypercube satisfies the requirements.

Input Format

The first line contains a positive integer $n$, representing the dimension of the hypercube.

The next $n$ lines each contain two integers $x,y$, indicating that in each tree $T$, there is an edge connecting $x$ and $y$.

Output Format

In the first line, output the number of placed trees $k$.

In the next $k$ lines, output $n+1$ integers per line, representing the corresponding hypercube vertex labels for the vertices of this tree.

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

Hint

[Sample 3 Explanation]

[Constraints]

For $100\%$ of the testdata, $1 \le n \le 16$, $0 \le x,y \le n$, and $x \neq y$.

[Hints and Notes]

If your program correctly places $k$ trees, then the score for each test point is $f(k) \cdot 110$, where:

$$f(k)=\begin{cases} \dfrac{0.7k}{2^{n-1}} & (k \lt 2^{n-1}) \cr 1 & (k=2^{n-1}) \cr \end{cases}$$

If the placement is incorrect, then the score for that test point is $0$. It can be proven that there is always a way to place $2^{n-1}$ trees.

Due to the special scoring method, this problem uses a custom-written Special Judge. You are welcome to hack it.

This problem is translated from COCI 2021-2022 CONTEST #2 Task 3 Hiperkocka.

In the original COCI problem, the full score is $110$, but for easier calculation, the full score has been changed to $26 \times 5=130$.

Translated by ChatGPT 5