题目描述

给定一个 $n$ 维的超正方体。

将该超正方体抽象为一个含 $2^n$ 个结点的图，结点分别用序号 $0,1,\cdots,2^n-1$ 表示。两个结点 $x,y$ 联通，当且仅当 $x \oplus y$ 为 $2$ 的整数幂。

现需将若干棵含有 $n$ 条边的树 $T$ 放置于该超正方体中。结点分别用序号 $0,1,\cdots,n$ 表示。给定每棵树的 $n$ 条边所连接的点的序号，则每一棵树需满足下列条件：

• 每个树上的结点都与超正方体的其中一个结点一一对应
• 每个结点互不相同
• 每一棵树的每一条边所连接的两个结点在超正方体中所对应的两个结点在超正方体中有边相连（即对应的两个结点的异或值为 $2$ 的整数幂）
• 每两棵树的边集在超正方体中所对应的边集不交，即超正方体中的每条边最多包含于一棵树中

请给定一种放置方案，使得放在超正方体中的每一棵树都符合题意。

输入格式

第一行一个正整数 $n$，表示超正方体的维数。

接下来的 $n$ 行，每行两个整数 $x,y$，表示在每棵树 $T$ 中，有一条连接 $x,y$ 的边。

输出格式

第一行输出放置的树的数目 $k$。

接下来的 $k$ 行，每行输出 $n+1$ 个整数，表示这棵树的对应结点在超正方体中的结点编号。

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

提示

【样例 3 解释】

【数据规模与约定】

对于 $100\%$ 的数据，$1 \le n \le 16$，$0 \le x,y \le n$，$x \neq y$。

【提示与说明】

如果程序正确地放置了 $k$ 棵树，则每个测试点的得分为 $f(k) \cdot 110$，其中：

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

若放置方式错误，则该测试点得分为 $0$。可以证明，总存在一种方式可以放置 $2^{n-1}$ 棵树。

因评分方式特殊，本题启用自行编写的 Special Judge，欢迎大家 hack。

题目译自 COCI 2021-2022 CONTEST #2 Task 3 Hiperkocka。

本题在 COCI 原题中满分 $110$，但由于为了计算方便，将满分修改为 $26 \times 5=130$。