题目描述

译自 CCO 2024 Day2 T1「Infiltration」。

Ondrej 和 Edward 是两名间谍，他们计划潜入邪恶组织 AQT 的基地。AQT 基地可以想象成一个由房间构成的树形结构，总共 $100$ 个房间，编号从 $0$ 到 $99$。为了完成任务，他们需要先让自己被抓进基地，然后在午夜同时逃脱并会合，再里应外合捣毁 AQT。

问题是，他们被关押的房间是不同的，而且彼此不知道对方的位置。为了尽快碰头，他们制定了以下行动计划：

• Ondrej 只能在奇数分钟行动，可以选择待在当前房间或移动到相邻的房间之一。
• Edward 只能在偶数分钟行动，同样可以选择待在当前房间或移动到相邻的房间之一。

为了尽快汇合，他们制定了如下策略：记下 $V(A, R, T)$ 表示某个间谍 $A$ 在特定时间 $T$ 应该待在房间 $R$。例如，$V(\text{Ondrej}, 10, 3)$ 表示 Ondrej 在午夜后第 $3$ 分钟应该待在编号为 $10$ 的房间。根据这个记法，他们要在某个时刻 $t(o, e)$ 满足 $V(\text{Ondrej}, o, t(o, e)) = V(\text{Edward}, e, t(o, e))$，这样他们就算汇合了。

Ondrej 和 Edward 希望无论他们被关在哪里，汇合的时间都尽可能短。记距离 $d$ 为他们初始房间之间最少需要经过的走廊数量。请帮助他们设计一个策略，使得在所有可能的初始房间组合下，汇合时间 $t$ 与距离 $d$ 的比值 $\frac{t(o, e)}{d(o, e)}$ 尽可能小。

输入格式

第一行一个整数 $N\ (N = 100)$，表示房间总数。

接下来 $N-1$ 行每行包含两个空格隔开的整数，表示两个相邻房间的编号 (说明存在一条双向通道连接这两个房间)。

输出格式

第一行一个正整数 $T\ (T\leq 1440)$，表示每个房间对应的策略需要记录的步数。

接下来是 Ondrej 的策略，然后是 Edward 的策略。

对于每个间谍的策略，都需要输出 $N$ 行，第 $n$ 行表示该间谍从 $n$ 号房间出发时的具体行动路线。每行包含 $T$ 个空格隔开的整数，依次表示该间谍在第 $1, 2,\ldots ,T$ 分钟应该待的房间编号。

5
0 2
3 2
1 4
2 4

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

请注意，这不是一个合法的测试数据，因为房间数不是 $100$。

根据给出的示例输出，该策略是无效的，因为如果 Ondrej 一开始在 $1$ 号房间，Edward 在 $3$ 号房间，那么他们将永远无法碰头。

数据范围与提示

如果输出不合法，或者存在测试用例和初始房间组合 $(o, e)$ 使得间谍在 $T$ 分钟之前没有汇合，则不得分。

否则，记所有测试用例和初始房间组合 $(o, e)(o \neq e)$ 中最大的 $\frac{t(o, e)}{d(o, e)}$ 为 $S$。根据 $S$ 的大小，可以获得的最高分如下：