CSES1685 新航班路线
#CS1685. 新航班路线
新航班路线
题目背景
翻译自 CSES-1685 题。
题目描述
有 n 个城市和 m 条航班连接。你的任务是添加新的航班，使得从任何一个城市都能到达其他所有城市。请问，最少需要添加多少条新航班？
输入格式
第一行包含两个整数 n 和 m：城市的数量和航班的数量。城市编号为 1,2,…,n1, 2, \dots, n1,2,…,n。
接下来有 m 行描述了航班，每行包含两个整数 a 和 b，表示从城市 a 到城市 b 有一条单向航班。
输出格式
首先输出一个整数 k：表示需要添加的最少新航班数量。接着输出 k 行，每行描述一条新航班。你可以输出任何一个有效的解。
样例
4 5
1 2
2 3
3 1
1 4
3 4
1
4 2
说明/提示