CF1423C.Dušan's Railway

As you may already know, Dušan is keen on playing with railway models. He has a big map with cities that are connected with railways. His map can be seen as a graph where vertices are cities and the railways connecting them are the edges. So far, the graph corresponding to his map is a tree. As you already know, a tree is a connected acyclic undirected graph.

He is curious to find out whether his railway can be optimized somehow. He wants to add so-called shortcuts, which are also railways connecting pairs of cities. This shortcut will represent the railways in the unique path in the tree between the pair of cities it connects. Since Dušan doesn't like repeating the railways, he has also defined good paths in his newly obtained network (notice that after adding the shortcuts, his graph is no more a tree). He calls a path good, if no edge appears more than once, either as a regular railway edge or as an edge represented by some shortcut (Every shortcut in a good path has length 1, but uses up all the edges it represents - they can't appear again in that path). Having defined good paths, he defines good distance between two cities to be the length of the shortest good path between them. Finally, the shortcutting diameter of his network is the largest good distance between any two cities.

Now he is curious to find out whether it is possible to achieve shortcutting diameter less or equal than $k$, while adding as few shortcuts as possible.

Your solution should add no more than $\mathbf{10 \cdot n}$ shortcuts.

你可能已经知道，杜尚热衷于玩铁路模型。他有一张大型地图，上面标有若干城市，这些城市之间由铁路连接。他的地图可以看作一个图，其中顶点表示城市，连接城市的铁路则为边。到目前为止，对应于他地图的图是一棵树。如你所知，树是一种连通的、无环的无向图。

他很好奇自己的铁路系统是否能在某种程度上被优化。他希望添加所谓“捷径”（shortcuts），即连接某些城市对的额外铁路。每条捷径代表树中该城市对之间唯一路径上的所有铁路边。由于杜尚不喜欢重复铺设铁路，他在新增捷径后得到的新网络中（注意：加入捷径后，图不再是一棵树）定义了“好路径”（good paths）。他称一条路径是“好”的，当且仅当其中任意一条边至多出现一次——无论是作为原始铁路边，还是作为某条捷径所代表的边（每条捷径在好路径中长度为 1，但会“占用”其所代表的所有边——这些边在该路径中不能再出现）。在定义了“好路径”之后，他将两座城市之间的“好距离”（good distance）定义为它们之间最短好路径的长度。最后，“捷径直径”（shortcutting diameter）是指所有城市对之间的最大好距离。

现在，他想知道：在保证捷径直径不超过 $k$ 的前提下，最少需要添加多少条捷径？

你的解法所添加的捷径数量不得超过 $\mathbf{10 \cdot n}$ 条。

The first line in the standard input contains an integer $n$ ($1 \le n \le 10^4$), representing the number of the cities in Dušan's railway map, and an integer k ($3 \le k \le n$) representing the shortcutting diameter that he wants to achieve.

Each of the following $n - 1$ lines will contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), meaning that there is a railway between cities $u_i$ and $v_i$.

标准输入的第一行包含一个整数 $n$（$1 \le n \le 10^4$），表示杜尚铁路地图中的城市数量，以及一个整数 $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$ 之间存在一条铁路。

The first line of the output should contain a number $t$ representing the number of the shortcuts that were added.

Each of the following $t$ lines should contain two integers $u_i$ and $v_i$, signifying that a shortcut is added between cities $u_i$ and $v_i$.

输出的第一行应包含一个数字 $t$，表示所添加的捷径数量。

接下来的 $t$ 行中，每行应包含两个整数 $u_i$ 和 $v_i$，表示在城市 $u_i$ 与 $v_i$ 之间添加了一条捷径。

Notice that adding a shortcut between all cities and city 1 will make a graph theoretic diameter become 2. On the other hand, the paths obtained that way might not be good, since some of the edges might get duplicated. In the example, adding a shortcut between all cities and city 1 doesn't create a valid solution, because for cities 5 and 10 the path that uses shortcuts 5-1 and 1-10 is not valid because it uses edges 1-2, 2-3, 3-4, 4-5 twice.

注意，若在所有城市与城市 1 之间都添加一条捷径，则图论意义上的直径将变为 2。另一方面，这样得到的路径可能并不合适，因为其中某些边可能会被重复使用。在示例中，在所有城市与城市 1 之间添加捷径并不能构成一个有效解，原因是：对于城市 5 和城市 10，采用捷径路径 5-1 和 1-10 所得的路径是无效的，因为它重复使用了边 1-2、2-3、3-4、4-5。