← 返回题目列表

Codeforces · 1423/C

C. 杜尚铁路

中文机器翻译题面 查看原题

您可能已经知道,Dušan 热衷于玩铁路模型。他有一张大地图,上面有与铁路相连的城市。他的地图可以看作是一个图表,其中顶点是城市,连接城市的铁路是边缘。到目前为止,他的地图对应的图是一棵树。正如您所知,树是一个连通的无环无向图。

他很好奇是否可以以某种方式优化他的铁路。他想增加所谓的捷径,也就是连接城市之间的铁路。这条捷径将代表其连接的两座城市之间树中唯一路径中的铁路。由于 Dušan 不喜欢重复铁路,因此他还在新获得的网络中定义了良好的路径(请注意,添加快捷方式后,他的图不再是树)。如果没有边出现超过一次,他称一条路径为好路径,无论是作为常规铁路边缘还是由某些快捷方式表示的边缘(好路径中的每个快捷方式的长度都是 1,但用尽了它所表示的所有边 - 它们不能再次出现在该路径中)。定义好路径后,他将两个城市之间的好距离定义为它们之间的最短好路径的长度。最后,他的网络的捷径直径是任意两个城市之间的最大良好距离。

现在他很好奇是否有可能实现小于或等于$$$k$$$的捷径直径,同时添加尽可能少的捷径。

您的解决方案添加的快捷方式不应超过 $$$\mathbf{10 \cdot n}$$$。

输入

标准输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$),代表 Dušan 铁路图中的城市数量,以及一个整数 k ($$$3 \le k \le n$$$) 代表他想要实现的捷径直径。

以下 $$$n - 1$$$ 行中的每一行都将包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i$$$),这意味着城市 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条铁路。

输出

输出的第一行应包含一个数字 $$$t$$$ ,表示已添加的快捷方式的数量。

以下$$$t$$$ 行应包含两个整数$$$u_i$$$ 和$$$v_i$$$,表示在城市$$$u_i$$$ 和$$$v_i$$$ 之间添加了快捷方式。

示例

输入 #1

10 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

输出 #1

8
3 7
3 5
3 6
3 1
7 9
7 10
7 4
7 5

注意

请注意,在所有城市和城市 1 之间添加快捷方式将使图论直径变为 2。另一方面,通过这种方式获得的路径可能不好,因为某些边可能会重复。在示例中,在所有城市和城市 1 之间添加快捷方式不会创建有效的解决方案,因为对于城市 5 和 10,使用快捷方式 5-1 和 1-10 的路径无效,因为它两次使用边 1-2、2-3、3-4、4-5。