...立方体里一片漆黑，立方体里一片漆黑……

凌晨五点。Daniel 醒了过来，他睁开眼睛。他的头有点疼。他还能听到耳边的嗡嗡声。

他意识到自己身处一个游乐场，在一个巨大的金属盒子里。

……我曾在立方体里，我曾在立方体里……

他想起三年前自己也曾陷入过类似的情况，那是 COCI 第二轮的 Kocka 题。

……我又在立方体里了，我又在立方体里了……

但这一次，情况复杂得多……Daniel 身处一个 $n$ 维超立方体 $Q_n$ 中。他周围散落着 $2^{n-1}$ 个包含 $n$ 条边的树 $T$ 的相同副本。他很快意识到，拯救他的方法在于用这些树来平铺超立方体的边。

形式上，超立方体 $Q_n$ 是一个包含节点 $0, 1, \dots, 2^n - 1$ 的图，其中节点 $x$ 和 $y$ 相连当且仅当它们的按位异或结果是 2 的幂。

一棵树可以放置在超立方体上，需满足： 树的每个节点对应超立方体的一个节点 这些节点必须互不相同 * 如果树中两个节点之间有一条边，那么超立方体中对应的节点之间也必须有一条边

超立方体的平铺是通过放置若干棵树来完成的，使得超立方体的每条边最多属于一棵树。

你的任务是用尽可能多的给定树 $T$（它有 $n$ 条边）的副本平铺超立方体 $Q_n$。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 16$)，即超立方体的维度。 接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x, y \le n, x \neq y$)，表示树 $T$ 中节点 $x$ 和 $y$ 之间有一条边。

输出格式

第一行输出你平铺中使用的树的数量。 接下来的每一行描述单个树 $T$ 副本的放置方式。 在第 $i$ 行，输出 $n+1$ 个数字 $a_0^{(i)}, a_1^{(i)}, \dots, a_n^{(i)}$。这些数字表示第 $i$ 棵树的放置方式，使得超立方体节点 $a_j^{(i)}$ 对应于树节点 $j$，对于所有 $j = 0, \dots, n$。

子任务

如果你的方案正确放置了 $k$ 棵树，你将获得 $f(k) \cdot 110$ 分，其中：

$$f(k) = \begin{cases} 0.7 \cdot k/2^{n-1} & \text{如果 } k < 2^{n-1} \\ 1 & \text{如果 } k = 2^{n-1} \end{cases}$$

当然，如果你的方案不正确，你将获得 0 分。 你的总得分等于你在所有测试点中得分的最小值。 可以证明，总是存在一种使用全部 $2^{n-1}$ 棵树的方案。

样例

输入 1

1
0 1

输出 1

1
0 1

输入 2

2
0 1
1 2

输出 2

2
0 1 3
0 2 3

输入 3

3
0 1
0 2
0 3

输出 3

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

说明

第三个样例的示意图：