题目描述

这是一道提交答案题。如果希望直接提交答案的生成代码，请确保它不会运行超过 20 秒。

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$ 行（$1 \le i \le N - 1$）包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 条道路连接的城市。

输出格式

在提交文件中写入 $K$ 行。

输出的第 $j$ 行包含两个整数 $X_j$、$Y_j$（$1 \le X_j \le N$，$1 \le Y_j \le N$），表示待修建道路所连接的两座城市。

提示

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 1000$。
• $1 \le A_i < B_i \le N$（$1 \le i \le N - 1$）。
• $(A_i, B_i) \ne (A_k, B_k)$（$1 \le i < k \le N - 1$）。
• 任意两座城市之间均存在路径。

评分规则

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

若你的输出不符合格式要求，则得分为零分。否则，设按你的方案修建道路后，总距离为 $W$，该输入对应的满分为 $P$。我们定义：

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

那么，你在此输入中获得的得分为：

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

本任务的总分为所有输入得分之和，四舍五入取最接近的整数。

各输入数据对应的 $N$、$K$、$W_0$、$P$ 值如下表所示：

输入数据	$N$	$K$	$W_0$	$P$
$1$	$20$	$4$	$512$	$10$
$2$	$1000$	$100$	$2650000$	$18$
$3$		$300$	$1755000$
$4$		$100$	$2900000$
$5$			$2690000$
$6$		$300$	$1745000$

翻译由 Qwen3-235B 完成。