P11517 [CCO 2024] Infiltration

翻译自 [CCO](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=80) 的 [2024P4题](https://dmoj.ca/problem/cco24p4)。

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$ 时这个间谍在的房间编号。

如果输出不合法，或者存在测试用例和初始房间组合 $(o, e)$ 使得间谍在 $T$ 分钟之前没有汇合，则不得分。 否则，记所有测试用例和初始房间组合 $(o, e)(o \neq e) $ 中最大的 $\frac{t(o, e)}{d(o, e)}$ 为 $S$。根据 $S$ 的大小，可以获得的最高分如下： | 分值 | $S$ 的限制 | | :----------: | :----------: | |$12$ | $200