题目描述

新加坡的互联网主干网由 $n$ 个网络站点组成，这些站点分配了从 $0$ 到 $n-1$ 的 序号。互联网中还有 $n-1$ 条双向链路，它们从 $0$ 到 $n-2$ 编号。每条链路连接两个不同的站点。被一条链路连接着的两个站点互相称作对方的邻居。

一个由互不相同的站点所组成的站点序列 $a_0,a_1,\ldots,a_p$ 被称作一条从站点 $x$ 到站点 $y$ 的路径，当且仅当 $a_0=x$，$a_p=y$，并且序列中每两个连续的站点都是邻居。保证从任意站点 $x$ 到任意其他站点 $y$ 有且仅有 一条路径。

任意站点 $x$ 可以生成一个数据包，并把它发送给任意其他站点 $y$，站点 $y$ 称作这个数据包的 目的站点。数据包需要按下述规则在站点 $x$ 到站点 $y$ 的唯一路径上进行路由。假设数据包当前发送到了站点 $z$，其中 $y$ 是数据包的目的站点且 $z \ne y$，则站点 $z$ 会：

1. 执行 路由函数，找到 $z$ 到 $y$ 的唯⼀路径中 $z$ 的邻居。然后
2. 将数据包转发给这个邻居。

然而，站点有存储内存限制，可能无法存下路由函数中需要使用的完整的主干网链路列表。

你的任务是实现主干网的路由机制，它由两个函数组成。

• 第一个函数的输入参数为 $n$、主干网链路的列表和一个整数 $k \ge n-1$。该函数需要为每个站点分配一个独一无二的 编号，其大小在 $0$ 到 $k-1$ 之间（包括 $0$ 和 $k-1$）。
• 第二个函数是路由函数，它在站点编号分配好后部署到所有站点上。它的输入参数如下：
  • $s$，数据包当前所处的站点的 编号，
  • $t$，数据包的目的站点的 编号 $(t \ne s)$，
  • $c$，表示 $s$ 的所有邻居站点的 编号 的列表。

该函数应该返回一个 $s$ 的邻居的 编号，表示数据包需要转发到的下个站点。

在每个子任务中，你的得分取决于所有站点被分配到的编号的最大值（通常来说，编号最大值越小越好）。

实现细节

你需要实现下列函数：

int[] label(int n, int k, int[] u, int[] v)

• $n$: 主干网中站点的数量。
• $k$: 可用的编号的最大值。
• $u$ 和 $v$: 大小为 $n-1$ 的数组，表示链路。对每个 $i(0 \le i \le \le n-2)$，链路 $i$ 连接着序号为 $u[i]$ 和 $v[i]$ 的站点。
• 该函数应该返回一个大小为 $n$ 的数组 $L$。对每个 $i(0 \le i \le n-1)$，$L[i]$ 表示序号为 $i$ 的站点所分配到的编号。数组 $L$ 中的所有元素必须互不相同并且大小在 $0$ 到 $k$ 之间。

int find_next_station(int s, int t, int[] c)

• $s$: 数据包当前所在站点的编号。
• $t$: 数据包目的站点的编号。
• $c$: 一个数组，包含 $s$ 的所有邻居的编号。数组 $c$ 按照元素大小升序排列。
• 该函数应该返回一个 $s$ 的邻居的编号，表示数据包需要转发到的下个站点。

每个测试用例包含一个或多个独立的场景（也就是不同的主干网描述）。 对于一个包含 $r$ 个场景的测试用例，调用上述函数的评测程序会按下列步骤运行恰好两次。

程序第一次运行期间：

• label 函数被调用 $r$ 次，
• 返回的编号将被评测系统保存，并且
• find_next_station 不会被调用。

程序第二次运行期间：

• find_next_station 会被调用若干次。对于每次调用，评测程序会选择任意某个场景，该场景中的 label 函数所返回的编号方式将用于本次 find_next_station 调用。
• label 不会被调用。
• 特别地，在评测程序第一次运行期间，保存在静态或全局变量中的信息将无法在 find_next_station 函数中使用。

提示

样例说明

例 1

考虑下列调用：

label(5, 10, [0, 1, 1, 2], [1, 2, 3, 4])

共有 $5$ 个站点和 $4$ 条链路，链路对应的站点序号对分别为 $(0,1)$, $(1,2)$, $(1,3)$ 和 $(2,4)$。编号的大小范围为 $0$ 到 $k=10$。

为了返回下列编号方案：

序号	编号
$0$	$6$
$1$	$2$
$2$	$9$
$3$
$4$	$7$

函数 label 应该返回 $[6,2,9,3,7]$。下图中的数字表示站点的序号（左图）与分配到的编号（右图）。

假设编号按照上图所示进行分配，考虑下列的调用：

find_next_station(9, 6, [2, 7])

它表示数据包当前所处的站点编号为 $9$，其目的站点的编号为 $6$。从当前站点到目的站点的路径上，站点编号依次为 $[9,2,6]$。因此，函数应该返回 $2$，表示数据包应该转发给编号为 $2$ 的站点（其序号为 $1$）。

考虑另一个可能的调用：

find_next_station(2, 3, [3, 6, 9])

该函数应该返回 $3$，因为目的站点（编号 $3$）是当前站点（编号 $2$）的邻居，因此目的站点直接接收到了数据包。

约束条件

• $1 \le r \le 10$

对于 label 的每次调用：

• $2 \le n \le 1000$
• $k \ge n-1$
• $0 \le u[i],v[i] \le n-1$（对于所有 $0 \le i \le n-2$）

对于 find_next_station 的每次调用，其输入参数来自于任意选择的某次之前对 label 的调用。考虑它所产生的编号，

• $s$ 和 $t$ 是两个不同站点的编号。
• $c$ 是编号为 $s$ 的站点的所有邻居的编号的序列，升序排列。

对于每个测试用例，所有场景加到⼀起，传递给函数 find_next_station 的所有数组 $c$ 的总长度不超过 $10^5$。

子任务

1. （5 分）$k=1000$，不会出现拥有多于 $2$ 个邻居的站点。
2. （8 分）$k=1000$，链路 $i$ 连接站点 $i+1$ 和 $\lfloor\frac{i}{2}\rfloor$。
3. （16 分）$k=10^6$，最多一个站点拥有多于 $2$ 个的邻居。
4. （10 分）$n \le 6$，$k \le 10^9$
5. （61 分）$k \le 10^9$

在子任务 5 中，你可以获得部分分。 令 $m$ 为所有场景中 label 返回的最大编号。 对于这个子任务，你的得分将根据下表计算得到：

最大编号	得分
$m \ge 10^9$	$0$
$2000 \le m < 10^9$	$50 \cdot \log_{5 \cdot10^5}(\frac{10^9}{m})$
$1000 < m < 5000$	$50$
$m \le 1000$	$61$

评测程序示例

评测程序示例以如下格式读取输入数据：

第 $1$ 行：$r$

接下来是 $r$ 块内容，每块描述了一个单独的场景，格式如下：

第 $1$ 行：$n\ k$
第 $2+i(0 \le i \le n-2)$ 行：$u[i]\ v[i]$
第 $1+n$ 行：$q$，find_next_station 的调用次数
第 $2+n+j(0 \le j \le q-1)$ 行：$z[j]\ y[j]\ w[j]$，第 $j$ 次调用 find_next_station 时所涉及的站点的 序号。此时，数据包在站点 $z[j]$，目的站点为 $y[j]$，应该要转发给站点 $w[j]$。

评测程序示例以如下格式打印你的结果：

第 $1$ 行：$m$

接下来是 $r$ 块内容，分别对应输入中的场景。每块的格式如下：

第 $1+j(0 \le j \le q-1)$ 行：站点的 序号，它所对应的 编号 是第 $j$ 次调用 find_next_station 时返回的结果。

注意：评测程序示例每次执行时会同时调用 label 和 find_next_station。