题目描述

译自 COCI 2021/2022 Contest #2 T3「超方形」

...这方块里伸手不见五指，伸五指不见手...

早上五点，小 D 醒了，睁开双眼，感觉头有点疼，耳朵还是嗡嗡的。随后，他发现他在一个大操场上的一个铁盒里。 译者注

...我在方块里啊，在方块里...

他记得三年前打 COCI Round 2 的时候，写 Kocka 那题的时候也是这种情况。

...我又在方块里了啊，又在了啊...

但是这次，事情变得复杂了许多……小 D 在一个 $n$ 维的超方形 $\mathcal Q_n$ 里。他周围有 $2^{n-1}$ 棵带有 $n$ 条边且完全一致的树 $\mathcal T$ 散落在他的周围。而他的唯一出路，便是用这些树搭出超方形的边。

形式化地说，一个超方形 $\mathcal Q_n$ 是一个由编号从 $0$ 到 $2^{n-1}$ 的节点构成的图，其中 $x$ 和 $y$ 节点连通当且仅当它们按位异或的结果是 $2$ 的幂次。

当满足以下条件时，一棵树将可以被放到超方形上：

• 树的每一个节点对应到超方形的不同节点
• 如果树上两节点之间有边，那么超边形上对应的节点之间也要有边

在超边形上搭树则是把多棵树放到超边形上使得超边形的每条边至多属于一棵树。你的任务是在超边形 $\mathcal Q_n$ 上放尽量多的带有 $n$ 条边的树 $\mathcal T$。

输入格式

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

接下来 $n$ 行，每一行两个整数 $x$ 和 $y$ $(x \neq y)$ 表示节点 $x$ 和 $y$ 在树 $\mathcal T$ 上有连边。

输出格式

第一行输出你铺的树的数量。

接下来每行描述你铺的一棵树。

第 $i$ 行输出 $n+1$ 个数 $a_0^{(i)},a_1^{(i)},\ldots,a_n^{(i)}$，表示第 $i$ 棵树的节点 $j$ 对应超方形的节点 $a^{(i)}_j$ $(j\in[0,~n])$。

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

评分方式

如果你的算法正确地放置了 $k$ 棵树，你该测试点的得分将会是 $f(k)\cdot 110$ 分，其中

$$f(k)= \begin{cases} \begin{aligned} 0.7\cdot\frac{k}{2^{n-1}}~&(k<2^{n-1})\\ 1~&(k=2^{n-1}) \end{aligned} \end{cases} $$

显然，如果你的解不正确，在该测试点你将得到零分。你本题的得分为各测试点得分取最小值，保证存在一组解使得 $2^{n-1}$ 棵树全部用上。

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