← 返回题目列表

Codeforces · 1092/E

E. 最小直径森林

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

给你一个森林——一个具有 $$$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 2
1 2
2 3

输出 #1

2
4 2

输入 #2

2 0

输出 #2

1
1 2

输入 #3

3 2
1 3
2 3

输出 #3

2

注意

在第一个示例中,添加边 (1, 4) 或 (3, 4) 将导致总直径为 3。但是,添加边 (2, 4) 将使总直径为 2。

Edge (1, 2) 是第二个示例的唯一选项。直径为1。

您无法在第三个示例中添加任何边。直径已经是2了。