题目背景

翻译自 CCO 的 2024P4题。

题目描述

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−1$ 行每一行包含两个空格分隔的整数，表示这两个房间之间有双向走廊。

输出格式

第一行应包含一个正整数 $T$，表示每个起始房间的条目数量，注意你需确保 $t \le 1440$。

接下来 $N \times 2$，分别输出奥德雷和爱德华的计划。

对于每个人的计划，输出 $N$ 行，每行 $T$ 个整数 $t_i$，表示时间 $i$ 时这个间谍在的房间编号。

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

提示

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

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