Peanut 准备去 Silvermill 城市度假，因此他需要一张 Silvermill 的地图。不幸的是，他的电脑坏了，所以他无法通过 Google 获取地图。

Silvermill 是一个由 $N$ 个道路交叉口组成的城市，编号为 $1$ 到 $N$，共有 $N-1$ 条道路。每条道路 $i$ 连接两个交叉口 $A_i$ 和 $B_i$，且是双向的。通过每条道路需要 $W_i$ 分钟。保证该城市是完全连通的，这意味着可以通过城市中的道路从任意一个交叉口到达另一个交叉口。为了避免拥堵，Silvermill 的总督决定，城市中每个交叉口连接的道路不超过三条。

Peanut 需要获得 Silvermill 的地图。换句话说，他需要获得 $i = 1, \dots, N-1$ 的 $(A_i, B_i, W_i)$。

Peanut 在 Silvermill 雇佣了一名制图师来完成这项任务。由于制图师不太熟练，他只能回答一个非常简单的问题：从交叉口 $X$ 到 $Y$ 所需的最短时间（以分钟为单位）是多少？Peanut 没有支付足够的钱给这名制图师，所以他在辞职前只能回答 $Q$ 个这样的问题。

Peanut 需要你帮助他设计一系列问题，以便他能绘制出 Silvermill 的地图并享受他的假期。你能帮帮他吗？

实现细节

在本任务中，你需要实现以下函数：（这与要求程序从标准输入读取并输出到标准输出的普通任务不同。）

void find_roads(int N, int Q, int A[], int B[], int W[])

该函数将被调用且仅被调用一次，包含两个输入参数和三个输出参数。两个输入参数是 $N$ 和 $Q$。$N$ 是道路交叉口的数量，而 $Q$ 是允许的最大查询次数。三个输出参数是 $A$、$B$ 和 $W$。你需要确定城市中的 $N-1$ 条道路，并将它们存入数组 $A$、$B$ 和 $W$ 中。道路的端点以及道路本身的顺序可以是任意的。

你可以调用以下评测库函数来完成任务：

long long get_distance(int X, int Y)

该函数将返回一个整数，即从交叉口 $X$ 到 $Y$ 所需的旅行时间（以分钟为单位）。如果你调用此函数的次数超过 $Q$ 次，或者作为参数提供了无效的交叉口编号，程序将立即终止，并将获得“答案错误”（Wrong Answer）的判决。

图 4：一个有 5 个道路交叉口和 4 条道路的城市。

考虑图 4 中的城市地图。假设 $Q = 500000$。那么，你需要实现以下函数：

find_roads(5, 500000, A[], B[], W[])

你的程序 find_roads 与评测库函数 get_distance 之间的一种可能的交互过程如下：

• get_distance(5, 4) = 10 get_distance 函数被要求查找交叉口 4 和 5 之间的距离。答案是 10，因为从交叉口 5 到 3 需要 3 分钟，然后从交叉口 3 到 4 又需要 7 分钟。
• get_distance(2, 4) = 1 get_distance 函数被要求查找交叉口 2 和 4 之间的距离。答案是 1，因为从交叉口 2 直接到 4 需要 1 分钟。
• get_distance(1, 3) = 15 get_distance 函数被要求查找交叉口 1 和 3 之间的距离。答案是 15，因为从交叉口 1 到 4 需要 8 分钟，然后从交叉口 4 到 3 又需要 7 分钟。
• get_distance(1, 2) = 9 get_distance 函数被要求查找交叉口 1 和 2 之间的距离。答案是 9，因为从交叉口 1 到 4 需要 8 分钟，然后从交叉口 4 到 2 又需要 1 分钟。

此时，参赛者的 find_roads 函数认为它已经掌握了足够的信息来推断城市地图。它设置 $A = [3, 4, 4, 5]$，$B = [4, 1, 2, 3]$ 且 $W = [7, 8, 1, 3]$，然后终止。这是一个可能的正确答案。道路的端点以及道路本身的顺序可以以任何顺序提供。

子任务

每个实例的最大执行时间为 1.0 秒。你的程序将在满足以下限制的输入实例集上进行测试：

• $2 \le N \le 1000$
• $1 \le A_i, B_i \le N$
• $1 \le W_i \le 10^9$

请阅读“评分”部分以获取更多详细信息。

评分

子任务 5 是一个特殊的评分子任务。你的得分取决于你在任何测试用例中进行的最大查询次数 $q$。

• 如果 $q > 25000$，你将获得 0 分。
• 如果 $12000 < q \le 25000$，你将获得 $10 - 10 \times \frac{q-12000}{13000}$ 分。
• 如果 $6500 < q \le 12000$，你将获得 $40 - 30 \times \frac{q-6500}{5500}$ 分。
• 如果 $q \le 6500$，你将获得 43 分。