407727: GYM102888 B 连接美国

人类文明已崩溃，鬼魅横行，危机四伏，山姆·布里吉斯必须横跨满目疮痍的世界，拯救面临灭顶之灾的人类。

现在满目疮痍的美国，可以看作一个简单无向图。即有 n 个节点和 m 条边，没有重边。

山姆·布里吉斯需要让美国重新连接起来，即让这个无向图变为连通无向图。也即让每对节点之间，都至少存在一条路径相连。

危在旦夕，请你帮助山姆·布里吉斯规划一个连接美国的方案——在无向图中加入尽可能少的边，使得图变为连通图。

第一行，两个整数 n, m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, )，表示所给无向图的点数和边数。

接下来 m 行，每行两个整数 u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i)，表示第 i 条边所连接的两个节点的编号。保证没有重边。

第一行，输出一个整数 k (0 ≤ k ≤ n)，表示方案新加入的边数。

输出的接下来 k 行，每行两个整数 u_j, v_j (1 ≤ u_j, v_j ≤ n, u_j ≠ v_j)，表示第 j 条新加入的边所连接的两个节点的编号。

如果在新加入边数尽可能少的前提下，有多种方案，则输出任意一种即可。

4 2
4 1
2 3

1
2 4

5 0

4
1 2
1 3
2 4
2 5

6 4
5 4
3 4
2 6
5 3

2
6 1
5 1

5 4
4 3
2 1
4 5
1 4

0

第一个样例中，1 和 4 已经连通，2 和 3 也已经连通。在这种情况下，只要不加入与已有边重复的任意一条边，即可让图重新连通。

第二个样例中，没有边，因此加入的边只要组成一棵树即为合法的方案。