给你一个森林——一个具有 $$$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了。