5331. 修建道路（Building Roads）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 比特兰有 `n` 个城市，现有 `m` 条道路连接这些城市。目标是修建新的道路，使得任意两个城市之间都有一条路径相连。 你的任务是求出需要修建的最少道路数量，并确定应修建哪些道路。 ## 输入格式 第一行包含两个整数 `n` 和 `m`：分别表示城市数量和现有道路数量。城市编号为 $1, 2, \dots, n$。 接下来 `m` 行描述现有道路，每行包含两个整数 `a` 和 `b`，表示城市 `a` 和 `b` 之间有一条道路。 保证每条道路连接两个不同的城市，且任意两个城市之间最多有一条道路。 ## 输出格式 首先输出一个整数 `k`：需要修建的最少道路数量。 然后输出 `k` 行，每行描述一条需要新建的道路。输出任意有效方案均可。 ## 输入输出样例 ### 输入 #1 ``` 4 2 1 2 3 4 ``` ### 输出 #1 ``` 1 2 3 ``` ## 说明/提示 ### 数据规模与约定 -$ 1 \le n \le 10^5$ -$ 1 \le m \le 2\times10^5$ -$ 1 \le a, b \le n$