题目背景

翻译自 CSES-1685 题。

题目描述

有 $n$ 个城市和 $m$ 条航班连接。你的任务是添加新的航班，使得从任何一个城市都能到达其他所有城市。请问，最少需要添加多少条新航班？

输入格式

第一行包含两个整数 $n$ 和 $m$：城市的数量和航班的数量。城市编号为 $1, 2, \ldots, n$。

接下来有 $m$ 行描述了航班，每行包含两个整数 $a$ 和 $b$，表示从城市 $a$ 到城市 $b$ 有一条单向航班。

输出格式

首先输出一个整数 $k$：表示需要添加的最少新航班数量。接着输出 $k$ 行，每行描述一条新航班。你可以输出任何一个有效的解。

样例

4 5
1 2
2 3
3 1
1 4
3 4

1
4 2

数据范围

• $1 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• $1 \le a, b \le n$