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) \neq (A_k, B_k)$（$1 \le i < k \le N-1$）
• 任意两座城市之间都存在路径。

子任务

对于每个输入，你的得分计算如下： 如果你的输出不符合格式，得分为 0 分。否则，设按照你的方案新建道路后的总距离为 $W$，该输入的满分为 $P$。定义：

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

则该输入你获得的分数为：

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

本题的总得分为每个输入的得分之和，四舍五入到最接近的整数。 各输入的 $N, K, W_0, P$ 值如下表所示：

样例

样例输入 1

4 1 8
1 2
2 3
3 4

样例输出 1

1 4

说明 1

在现有道路的基础上，通过修建一条连接第 1 座城市和第 4 座城市的道路，总距离变为 8。 对于此输入，设 $P = 10$。此时 $S = 0$，因此得分为 10 分。

样例输入 2

4 1 8
1 2
2 3
3 4

样例输出 2

1 2

说明 2

在这种情况下，修建道路后总距离为 10。 对于此输入，设 $P = 10$。此时 $S = -0.25$，因此得分为 $4.728 \dots$ 分。