Problem Description

Given an \( n \)-dimensional hypercube.

Abstract the hypercube into a graph with \( 2^n \) nodes, labeled as \( 0, 1, \cdots, 2^n-1 \). Two nodes \( x \) and \( y \) are connected if and only if \( x \oplus y \) is a power of 2.

You need to place several trees \( T \) with \( n \) edges into this hypercube. Each tree's nodes are labeled as \( 0, 1, \cdots, n \). Given the \( n \) edges of each tree, each tree must satisfy the following conditions:

• Each node in the tree corresponds to one node in the hypercube.
• All nodes are distinct.
• Each edge in the tree connects two nodes that, when mapped to the hypercube, have an edge between them (i.e., the XOR of the corresponding nodes is a power of 2).
• The edge sets of any two trees do not overlap in the hypercube, meaning each edge in the hypercube is included in at most one tree.

Provide a placement scheme such that each tree placed in the hypercube meets 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 \) and \( y \), indicating an edge connecting \( x \) and \( y \) in each tree \( T \).

Output Format

The first line should output the number of trees \( k \) placed.

The next \( k \) lines should each contain \( n+1 \) integers, representing the node numbers in the hypercube corresponding to the nodes of that tree.

Sample Input and Output

Input Sample #1

1
0 1

Output Sample #1

1
0 1

Input Sample #2

2
0 1
1 2

Output Sample #2

2
0 1 3
0 2 3

Input Sample #3

3
0 1
0 2
0 3

Output Sample #3

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

Notes

[Sample 3 Explanation]

[Data Range and Constraints]

For \( 100\% \) of the data, \( 1 \le n \le 16 \), \( 0 \le x, y \le n \), \( x \neq y \).

[Scoring]

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

\[ f(k) = \begin{cases} \dfrac{0.7k}{2^{n-1}} & (k < 2^{n-1}) \\ 1 & (k = 2^{n-1}) \\ \end{cases} \]

If the placement is incorrect, the score for that test case is \( 0 \). It can be proven that there always exists a way to place \( 2^{n-1} \) trees.

This problem uses a custom Special Judge and is open to hacks.

Translated from COCI 2021-2022 CONTEST #2 Task 3 Hypercube.

This problem originally scored \( 110 \) points in the COCI, but for convenience in calculation, the maximum score has been adjusted to \( 26 \times 5 = 130 \).

见题面 Input 部分

见题面 Output 部分