加固支柱

核心区最里面有一个天然的空洞——不是Zero建的，是陨石撞出来的。洞顶有几根石柱撑着，像巨人的手指。

"这里。"你说，"做最后的据点。"

"石柱不稳。"CC敲了敲，"空的。"

"那就加固。"你说，"在石柱之间加横梁，把力分散。"

"咋个加？"

你看着那几根石柱——七根，排成不规则的形状。有的高，有的低，有的粗，有的细。

"这样。"你说，"在每两根相邻的石柱之间加一根横梁。不是全加——加最少的，让整体稳固。"

"最少的？"

"对。"你说，"加太多浪费材料，加太少撑不住。我们要找那个刚好够的数量。"

你开始算。七根石柱，可能的横梁有二十一条。但只需要加……

"六根。"你说，"六根横梁，把七根石柱连成一体。"

"为啥子是六根？"

"因为七根柱子，连成一棵树，需要六条边。"你说，"多一条就多，少一条就断。"

"树？"

"对。"你说，"就像七个点连成一张网，最少需要六条线。"

CC开始搬木头——从废弃的货柜上拆下来的合金条，又轻又硬。她一根一根地装上，用铆钉固定。

"最后一根。"她说，"装好了。"

你推了推石柱——纹丝不动。

"稳了。"你说。

"比原来还稳。"CC说，"你算的？"

"我算的。"你说，"七根柱子，六根梁，一个整体。"

Echo把据点的结构图存进服务器。

"据点建立。"她说，"最后防线，就绪。"

题目描述

$n$ 根石柱，要在它们之间加横梁。每根横梁连接两根石柱。要求加最少的横梁，使得任意两根石柱之间都有路径（通过横梁连接）。

输入格式

$n, m$。然后 $m$ 对 $(u, v)$ 表示这两根石柱之间可以加横梁。

输出格式

最少横梁数，以及方案。

输入样例

3 2
1 2
2 3

输出样例

Case 1: 2 1

提示

• 最小生成树问题。
• 用Kruskal或Prim算法求最小生成树。
• 如果图不连通，则无法让所有石柱连通，输出 "NO"。

"据点稳了。"你说。

"然后呢？"CC问。

"然后。"你说，"联络。"

"联络谁？"

"所有人。"你说，"分散在各区的抵抗组织。我们要联合起来，一起攻核心。"

"他们信我们？"

"不信。"你说，"所以我们要一个一个说服。"

"咋个说服？"

"用事实。"你说，"告诉他们，我们有据点了，有退路了，有解法了。让他们来。"

"如果还是不来？"

"那就——"你想了想，"我们就自己去。"

"几个人？"

"六个。"你说，"我们六个。"

"够了？"

"够了。"你说，"因为我们是最后的拼图。"

[第八题：联络各方]