台湾拥有高密度的崇山峻岭，有超过 250 座海拔 3,000 米以上的山峰。阿明计划在台湾中央山脉建设机器人滑索配送网络，以便在偏远村庄之间运输包裹。

在阿明的计划中，每个网络由 $N$ 个节点组成，编号为 $0$ 到 $N - 1$。在这些节点中，恰好有 $K = 6$ 个是发电站，其余 $N - K$ 个是村庄节点。节点之间由 $N - 1$ 条双向缆索连接，编号为 $0$ 到 $N - 2$。对于每个 $i$ ($0 \le i \le N - 2$)，缆索 $i$ 连接节点 $U[i]$ 和 $V[i]$。每条缆索连接两个不同的节点，且每对节点之间最多由一条缆索连接。保证使用这些缆索可以在任意两个节点之间移动。

节点 $a$ 和 $b$ 之间的距离记为 $d(a, b)$，定义如下：

• 如果 $a = b$，则 $d(a, b) = 0$。
• 否则，$d(a, b)$ 是从 $a$ 到 $b$ 所需的最少缆索数量。

如果网络中每个节点要么连接了恰好 $1$ 条缆索，要么连接了至少 $\delta$ 条缆索，则称该网络的分支因子至少为 $\delta$。阿明已知一个正整数 $B$，使得该网络的分支因子至少为 $B$。

阿明准备了 $100$ 种不同的缆索类型，编号为 $0, 1, \dots, 99$。网络中的每条缆索都将使用其中一种类型建造。

机器人将沿着滑索缆索执行配送任务。阿明希望安装一个导航程序，帮助机器人返回发电站并充电。然而，机器人的内存极小。因此，在设计导航程序时，机器人仅根据发电站数量 $K = 6$、保证的分支因子 $B$ 以及机器人当前位置所连接的缆索类型进行导航。

当机器人想要在连接了两条或更多缆索的村庄节点 $u$ 处导航时，机器人首先以任意顺序扫描连接到 $u$ 的缆索。程序随后会收到一个包含这些缆索类型的列表。对于每条缆索，程序需要计算有多少个发电站满足：沿着该缆索移动会减小机器人与该发电站之间的距离。

具体来说，令 $v_1, \dots, v_k$ ($k \ge 2$) 为直接通过缆索与 $u$ 相连的节点，$c_i$ ($1 \le i \le k$) 为连接节点 $u$ 和 $v_i$ 的缆索类型。程序随后会收到 $K$、$B$ 以及列表 $c_1, c_2, \dots, c_k$。对于每个 $i$ ($1 \le i \le k$)，程序必须确定满足 $d(v_i, p) < d(u, p)$ 的发电站 $p$ 的数量。

你的任务是设计一种分配缆索类型的策略并设计导航程序。你的解决方案得分取决于所使用的不同缆索类型的数量（详见“子任务与评分”部分）。

实现细节

你需要实现两个过程，一个用于分配缆索类型，另一个用于机器人的程序。

你应该实现的用于分配缆索类型的过程是：

std::vector<int> construct_network(int N, int K, int B,
                                   std::vector<int> U, std::vector<int> V,
                                   std::vector<int> P)

• $N$：节点数量。
• $K$：发电站数量。
• $B$：网络保证的最小分支因子。
• $U, V$：长度为 $N - 1$ 的数组，描述缆索连接。
• $P$：长度为 $K = 6$ 的数组，描述发电站节点。
• 对于每个测试用例，此过程最多被调用 $10\,000$ 次。

此过程应返回一个长度为 $N - 1$ 的数组 $T$：

• 类型为 $T[i]$ 的缆索用于连接节点 $U[i]$ 和 $V[i]$。
• 每个元素 $T[i]$ 必须满足 $0 \le T[i] < 100$。

你应该实现的用于机器人程序的过程是：

std::vector<int> navigate(int K, int B, std::vector<int> C)

• $K$：发电站数量。
• $B$：网络保证的最小分支因子。
• $C$：连接到某个连接了至少 $2$ 条缆索的村庄节点的所有缆索类型列表，顺序任意。
• 保证 $C$ 的长度至少为 $B$。
• 对于每个测试用例，此过程最多被调用 $100\,000$ 次。
• 过程 navigate 不得依赖于原始网络结构；特别地，评分系统可能会在同一个测试用例中跨不同的已构建网络重新排序所有对 navigate 的调用。

此过程应返回一个数组 $D$：

• 数组 $D$ 的长度必须与数组 $C$ 相同。
• $D[i]$ 必须是满足“沿着对应于 $C[i]$ 的缆索移动会减小机器人与该发电站之间的距离”的发电站数量。

注意，在评分系统中，construct_network 和 navigate 过程在两个独立的进程中调用。

数据范围

• $K = 6$。
• $K < N \le 100\,000$。
• 每个测试用例中，所有对 construct_network 的调用中 $N$ 的总和不超过 $100\,000$。
• 对于每个 $0 \le i \le N - 2$，满足 $0 \le U[i] < V[i] < N$。
• 保证可以使用缆索从任意节点移动到其他任何节点。
• $0 \le P[0] < P[1] < \dots < P[K - 1] < N$。
• 每个数组 $C$ 都是连接到某个连接了至少 $2$ 条缆索的村庄节点的所有缆索类型列表的一个排列。
• 每个测试用例中，所有对 navigate 的调用中数组 $C$ 的长度总和不超过 $200\,000$。

子任务与评分

在任何测试用例中，如果满足以下至少一个条件，则该测试用例的得分为 $0$（在 CMS 中报告为 Output isn't correct）：

• 任何对 construct_network 的调用的返回值无效。
• 任何对 navigate 的调用的返回值不正确。

否则，令 $S$ 为从每个 construct_network 调用返回的所有数组 $T$ 中所有数字的最大值加 $1$。换句话说，$S$ 是使得所有构建的网络仅使用类型为 $0, 1, \dots, S - 1$ 的缆索的最小整数。

你对每个子任务的得分取决于 $S$，如下表所示：

特别地，在子任务 1、2 和 5 中，如果 $S \le 5$，你将获得满分；在子任务 3 和 4 中，如果 $S \le 4$，你将获得满分。

样例

考虑 $N = 9, K = 6, B = 2$ 的场景。网络计划由 $U = [0, 0, 0, 2, 2, 2, 2, 7], V = [1, 2, 3, 4, 5, 6, 7, 8]$ 指定。发电站为 $P = [1, 3, 4, 5, 6, 7]$。考虑对第一个进程的以下调用：

construct_network(9, 6, 2, [0, 0, 0, 2, 2, 2, 2, 7],
                  [1, 2, 3, 4, 5, 6, 7, 8],
                  [1, 3, 4, 5, 6, 7])

假设阿明通过返回以下数组来构建网络：

[0, 10, 1, 2, 3, 4, 5, 5]

构建的网络示意图如下：

然后，在第二个进程中，假设机器人需要在节点 $0$ 处导航。节点 $0$ 连接到节点 $1, 2$ 和 $3$。如果机器人按此顺序读取缆索类型，将进行以下调用：

navigate(6, 2, [0, 10, 1])

基于网络结构：

• 第一个发电站，节点 $1$，到自身的距离最短。特别地，$0 = d(1, 1) < 1 = d(0, 1) < 2 = d(2, 1) = d(3, 1)$。
• 第二个发电站，节点 $3$，到自身的距离最短。特别地，$0 = d(3, 3) < 1 = d(0, 3) < 2 = d(1, 3) = d(2, 3)$。
• 其他发电站，节点 $4, 5, 6$ 和 $7$，到节点 $2$ 的距离更短。特别地，当 $u = 4, 5, 6$ 或 $7$ 时，$1 = d(2, u) < 2 = d(0, u) < 3 = d(1, u) = d(3, u)$。

沿着缆索 $(0, 1), (0, 2)$ 和 $(0, 3)$ 后，距离减小的发电站数量分别为 $1, 4$ 和 $1$。因此，该过程应返回：

[1, 4, 1]

注意，navigate 也可以针对 $C$ 的不同排列进行调用。例如，navigate(6, 2, [1, 0, 10]) 也是节点 $0$ 的一个可能调用。该过程应相应地返回 [1, 1, 4]。

假设机器人需要在节点 $2$ 处导航。进行以下调用：

navigate(6, 2, [10, 2, 3, 4, 5])

该过程应返回：

[2, 1, 1, 1, 1]

在此网络中，navigate 过程永远不会被用于其他节点，因为：

• 节点 $1, 3, 4, 5, 6$ 和 $7$ 均为发电站，且
• 节点 $8$ 仅连接到一条缆索。

在此测试用例中，使用的缆索类型为 $0, 1, 2, 3, 4, 5$ 和 $10$。因此，$S = 11$ 将被用于确定得分。