2835 「JOISC 2018 Day 2」路网服务

译自 JOISC 2018 Day2 T2「道路網の整備 / Road Service」

IOI 王国有 $N$ 个城市，编号为 $1$ 到 $N$。同时又有 $N-1$ 条双向道路，编号为 $1$ 到 $N-1$。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。在任意两个城市之间存在一条路径。

两个城市之间的距离定义为连接两个城市所经过的最少路径条数。IOI 王国的总距离定义为所有不同的城市对之间的距离。

IOI 王国的国王计划再建 $K$ 条道路，以减少总距离，提高交通的便利性。

你作为国王的助理，请帮助国王找到一个好的方案。

任务

给定 IOI 王国现已存在的道路的信息和要建设的道路的条数，输出一个建设 $K$ 条道路的方案。总距离最短分值越高。

本题有 $6$ 组输入。从每组数据中读取以下内容：

第一行包含三个被一个空格隔开的正整数 $N,K$ 和 $W_0$，表示 IOI 王国有 $N$ 座城市，国王计划建 $K$ 条道路。$W_0$ 是评分用的参数；

接下来的 $N-1$ 行，第 $i$ 行包含两个正整数 $A_i, B_i$，表示第 $i$ 条道路连接的两个城市。

输出中输出 $K$ 行。第 $j$ 行包含两个整数 $X_j, Y_j$，代表要建的道路连接的两个城市。

只需要提交输出即可。只有当输出格式符合上述描述时输出合法。

在原有道路的基础上再建一条 $1$ 号城市到 $4$ 号城市的道路，总距离就变成了 $8$。

设这组数据 $P=10$。这里 $S=0$（$S$ 的定义参见「数据范围与提示」），因此这组输出的得分为 $10$ 分。

在建设这条道路之后，总距离变成了 $10$。

设这组数据 $P=10$，此处 $S=-0.25$，因此得分为 $4.728\cdots$ 分。

对于每组输出，你的得分按如下方式计算：

如果你的输出不符合输出格式要求，得 $0$ 分。否则，设按你的计划建设道路后 IOI 王国的总距离为 $W$，并且设此数据点的分值为 $P$。定义

$$S=1.0-\frac{W}{W_0}$$

这里，对于一个测试点，你得到的分数是

$$\min(P,P\times 20^{S})$$

本题的分值是每组输出能获得的分值之和，分数取与这个分数之差的绝对值最小的整数。

对于每组数据，$N,K,W_0,P$ 的值如下：