CSES1666 修建道路
#CS1666. 修建道路
修建道路
题目背景
翻译自 CSES-16 题。
题目描述
Byteland 有 n 个城市，和 m 条道路连接它们。目标是建设新的道路，使得任意两个城市之间都可以通过道路相连。
你的任务是找出需要建设的最小数量的道路，并确定应该修建哪些道路。
输入格式
第一行包含两个整数 n 和 m，分别表示城市的数量和现有道路的数量。城市编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来的 m 行，每行包含两个整数 a 和 b，表示城市 a 和城市 b 之间有一条道路。
每条道路始终连接两个不同的城市，且每两个城市之间至多有一条道路。
输出格式
首先输出一个整数 k，表示需要修建的道路数量。
然后输出 k 行，每行描述一条新修建的道路。你可以输出任意一个有效的解决方案。
样例
4 2
1 2
3 4
1
2 3
说明/提示