P6951 [ICPC 2018 WF] Wireless is the New Fiber

一种新型的无限带宽无线通信刚刚通过测试，并被证明可以替代现有的基于光纤的通信网络，后者正努力跟上流量增长的步伐。你被委托决定新通信网络的布局。当前的通信网络由一组节点（用于路由消息）和光纤链路组成，每条链路连接两个不同的节点。对于每对节点，至少存在一条（但可能更多，为了带宽目的）光纤路径。 新的通信网络将不再使用光纤。相反，它将使用无线链路，每条链路连接两个节点。这些链路具有无限带宽，但成本昂贵，因此决定尽可能少地建设这些链路以提供连通性；对于每对节点，应该只有一条路径通过无线链路连接。此外，你发现每个节点的设计都考虑了特定数量的连接。如果每个节点的连接数与今天不同，则需要重新组织，这将非常昂贵。 你的任务是设计新的网络，使其在每对节点之间恰好有一条路径，同时最小化与原始网络连接数不同的节点数量。图 K.1 显示了原始网络和样例输入 1 的解决方案。  图 K.1：样例输入 1 的示意图。

输入以一行两个整数 $n (2 \le n \le 10^{4})$ 和 $m (1 \le m \le 10^{5})$ 开始，表示现有网络中的节点数和光纤链路数。节点编号从 $0$ 到 $n - 1$。接下来的 $m$ 行中的每一行包含两个不同的整数 $a_{i}$ 和 $b_{i}$，表示第 $i$ 条光纤链路连接编号为 $a_{i}$ 和 $b_{i}$ 的节点。保证对于每对节点，至少存在一条路径连接这两个节点。任何一对节点之间可能有多条光纤链路连接。

显示需要更改连接数的最小节点数。从下一行开始，以与输入相同的格式显示连接系统。即，显示一行包含节点数（这将与输入相同）和无线链路数，然后在后续行中描述这些链路。如果有多种布局可能，任何有效的布局都将被接受。

时间限制：2 秒，内存限制：1024 MB。 SPJ 提供者：@[shenyouran](/user/137367)。 题面翻译由 ChatGPT-4o 提供。