CF1092E.Minimal Diameter Forest

You are given a forest — an undirected graph with $n$ vertices such that each its connected component is a tree.

The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.

You task is to add some edges (possibly zero) to the graph so that it becomes a tree and the diameter of the tree is minimal possible.

If there are multiple correct answers, print any of them.

给你一片森林——一个包含 $n$ 个顶点的无向图，其每个连通分量均为一棵树。

一个连通无向图的直径（又称“最长最短路径”）是指该图中任意两个顶点之间最短路径所含边数的最大值。

你的任务是向该图中添加若干条边（可以不添加），使其成为一棵树，并使得所得树的直径尽可能小。

若存在多个正确答案，输出任意一个即可。

The first line contains two integers $n$ and $m$ ($1 \le n \le 1000$, $0 \le m \le n - 1$) — the number of vertices of the graph and the number of edges, respectively.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$, $v \ne u$) — the descriptions of the edges.

It is guaranteed that the given graph is a forest.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 1000$，$0 \le m \le n - 1$），分别表示图的顶点数和边数。

接下来的 $m$ 行中，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$，$v \ne u$），表示一条边的两个端点。

保证给定的图是一片森林。

In the first line print the diameter of the resulting tree.

Each of the next $(n - 1) - m$ lines should contain two integers $v$ and $u$ ($1 \le v, u \le n$, $v \ne u$) — the descriptions of the added edges.

The resulting graph should be a tree and its diameter should be minimal possible.

For $m = n - 1$ no edges are added, thus the output consists of a single integer — diameter of the given tree.

If there are multiple correct answers, print any of them.

在第一行输出所得树的直径。

接下来的 $(n - 1) - m$ 行中，每行应包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$，且 $v \ne u$），表示所添加的边。

最终得到的图必须是一棵树，且其直径应为可能的最小值。

当 $m = n - 1$ 时，不添加任何边，因此输出仅包含一个整数——即给定树的直径。

若存在多个正确答案，输出任意一个即可。

In the first example adding edges (1, 4) or (3, 4) will lead to a total diameter of 3. Adding edge (2, 4), however, will make it 2.

Edge (1, 2) is the only option you have for the second example. The diameter is 1.

You can't add any edges in the third example. The diameter is already 2.

在第一个例子中，添加边 (1, 4) 或 (3, 4) 将使总直径变为 3；然而，添加边 (2, 4) 则会使总直径变为 2。

在第二个例子中，唯一可选的边是 (1, 2)，此时直径为 1。

在第三个例子中，无法添加任何边，因为直径已经是 2。