You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1666 题。

题目描述

Byteland 有 $n$ 个城市，和 $m$ 条道路连接它们。目标是建设新的道路，使得任意两个城市之间都可以通过道路相连。

你的任务是找出需要建设的最小数量的道路，并确定应该修建哪些道路。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示城市的数量和现有道路的数量。城市编号为 $1,2,…,n$。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城市 $a$ 和城市 $b$ 之间有一条道路。

每条道路始终连接两个不同的城市，且每两个城市之间至多有一条道路。

输出格式

首先输出一个整数 $k$，表示需要修建的道路数量。

然后输出 $k$ 行，每行描述一条新修建的道路。你可以输出任意一个有效的解决方案。

样例

4 2
1 2
3 4

1
2 3

说明/提示

$1\le n \le 10^5$；

$1\le m \le 2 \cdot 10^5$；

$1\le a,b \le n$。