CF1092E Minimal Diameter Forest

给定一片森林——一个有 $n$ 个顶点的无向图，保证其每个连通分量都是一棵树。 一个连通无向图的直径（即“最长最短路”）定义为任意两点之间最短路径中的最大边数。 你的任务是向该图中添加一些边（可以为零），使得整个图变成一棵树，并且该树的直径尽可能小。 如果有多种方案，输出任意一种即可。

第一行包含两个整数 $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$），表示一条无向边的两个端点。 保证给定的图是一片森林。

第一行输出最终生成树的直径。 接下来的 $(n - 1) - m$ 行，每行输出两个整数 $v$ 和 $u$（$1 \le v, u \le n$，$v \ne u$），表示你添加的每一条边。 最终得到的图必须是一棵树，并且其直径应尽可能小。 当 $m = n - 1$ 时，不需要添加任何边，只需输出一行，即该树的直径。 如果有多种方案，输出任意一种即可。

在第一个样例中，添加边 $(1, 4)$ 或 $(3, 4)$，最终直径为 $3$。但如果添加边 $(2, 4)$，直径可以变为 $2$。 第二个样例中，唯一可选的边是 $(1, 2)$，直径为 $1$。 第三个样例中，不能再添加边，直径已经是 $2$。 由 ChatGPT 4.1 翻译