Ondrej 和 Edward 是间谍，他们准备摧毁邪恶组织 AQT。为了达成目标，他们需要潜入 AQT 基地。该基地可以建模为一棵拥有 $N = 100$ 个房间的树，房间编号从 $0$ 到 $N - 1$。Ondrej 和 Edward 的潜入计划是先被绑架，然后在执行计划前会合。被绑架后，两人会被放置在互不知晓的房间里。一旦被放置在房间中，他们都会在午夜挣脱，并尝试在执行计划前会合。

他们会合的计划如下：在每一个奇数分钟，Ondrej 可以选择留在当前房间或移动到相邻房间。在每一个偶数分钟，Edward 可以选择留在当前房间或移动到相邻房间。

策略定义如下：令 $V(A, R, T)$ 表示特工 $A$ 在午夜位于房间 $R$ 时，在午夜后 $T$ 分钟时应该所在的房间。该策略必须符合上述条件。若 $t(o, e)$ 是满足 $V(\text{Ondrej}, o, t(o, e)) = V(\text{Edward}, e, t(o, e))$ 的最小时间，则称特工在 $t(o, e)$ 时会合。

Ondrej 和 Edward 希望相对于他们两个起始房间之间的距离，尽可能快地会合。距离 $d(o, e)$ 是从 $o$ 到 $e$ 所需经过的最少走廊数量。请帮助找到一种策略，使得对于所有不同的房间对 $o$ 和 $e$，$\frac{t(o, e)}{d(o, e)}$ 的最大值最小。

输入格式

第一行输入包含 $N$ ($N = 100$)。[CCO 后续编辑：如果 $N$ 的值不是 100，请立即退出程序。]

接下来的 $N - 1$ 行，每行包含两个空格分隔的整数，表示两个房间之间存在一条双向走廊。

输出格式

首先输出一个正整数 $T$，表示每个起始房间的条目数。注意必须满足 $T \le 1440$，否则将无法获得任何分数。

然后，输出 Ondrej 的策略，接着输出 Edward 的策略。

输出特工的策略时，输出 $N$ 行，其中第 $n$ 行（从 $0$ 开始）表示该特工从房间 $n$ 出发时的路径。对于每一行，输出 $T$ 个空格分隔的整数：表示特工在时间 $1, 2, \dots, T$ 时应该所在的房间。

子任务

如果输出无效，或者存在某个测试用例以及一对不同的房间 $o$ 和 $e$，使得特工在时间 $T$ 或之前没有会合，则不会获得任何分数。

否则，令 $S$ 为所有测试用例及所有不同房间对 $o$ 和 $e$ ($o \neq e$) 中 $\frac{t(o, e)}{d(o, e)}$ 的最大值。下表显示了 25 分的分布情况：

样例

输入 1

5
0 2
3 2
1 4
2 4

输出 1

8
2 2 4 4 1 1 1 1
1 1 1 1 1 1 1 1
3 3 2 2 3 3 2 2
3 3 2 2 0 0 2 2
4 4 4 4 2 2 2 2
0 2 2 3 3 3 3 2
1 4 4 2 2 0 0 0
2 3 3 3 3 3 3 3
3 3 3 3 3 3 3 3
4 1 1 1 1 4 4 4

说明 1

注意这是一个无效的测试用例，因为 $N \neq 100$，所以它不会出现在评测的测试用例中。该测试用例的输出是有效的。注意，这不会获得任何分数，因为如果 Ondrej 从房间 1 出发，Edward 从房间 3 出发，他们将永远不会会合。