407727: GYM102888 B 连接美国
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
B. 连接美国time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output
人类文明已崩溃,鬼魅横行,危机四伏,山姆·布里吉斯必须横跨满目疮痍的世界,拯救面临灭顶之灾的人类。
现在满目疮痍的美国,可以看作一个简单无向图。即有 n 个节点和 m 条边,没有重边。
山姆·布里吉斯需要让美国重新连接起来,即让这个无向图变为连通无向图。也即让每对节点之间,都至少存在一条路径相连。
危在旦夕,请你帮助山姆·布里吉斯规划一个连接美国的方案——在无向图中加入尽可能少的边,使得图变为连通图。
Input第一行,两个整数 n, m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, ),表示所给无向图的点数和边数。
接下来 m 行,每行两个整数 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi),表示第 i 条边所连接的两个节点的编号。保证没有重边。
Output第一行,输出一个整数 k (0 ≤ k ≤ n),表示方案新加入的边数。
输出的接下来 k 行,每行两个整数 uj, vj (1 ≤ uj, vj ≤ n, uj ≠ vj),表示第 j 条新加入的边所连接的两个节点的编号。
如果在新加入边数尽可能少的前提下,有多种方案,则输出任意一种即可。
ExamplesInput4 2 4 1 2 3Output
1 2 4Input
5 0Output
4 1 2 1 3 2 4 2 5Input
6 4 5 4 3 4 2 6 5 3Output
2 6 1 5 1Input
5 4 4 3 2 1 4 5 1 4Output
0Note
第一个样例中,1 和 4 已经连通,2 和 3 也已经连通。在这种情况下,只要不加入与已有边重复的任意一条边,即可让图重新连通。
第二个样例中,没有边,因此加入的边只要组成一棵树即为合法的方案。