一个国家有n个城市。最初,该国没有公路。有一天,国王决定修建一些连接两座城市的道路。无论哪种方式都可以穿过道路。他希望这些道路的建设方式使得从每个城市到任何其他城市最多可以穿越两条道路。你还得到了 m 对城市——这些城市对之间不能修建道路。
你的任务是建造最少数量的仍满足上述条件的道路。约束将保证这始终是可能的。
输入
第一行由两个整数 n 和 m $$( 1 \leq n \leq 1 0 ^ { 3 }, 0 \leq m < \frac { n } { 2 } )$$ 组成。
接下来是m行,每行由两个整数ai和bi组成(1≤ai,bi≤n,ai≠bi),这意味着不可能建造一条连接城市ai和bi的道路。考虑城市从 1 到 n 编号。
保证每对城市在输入中最多出现一次。
输出
您应该在第一行打印一个整数 s:应建造的最少道路数。然后应有 s 条线,每条线由两个整数 ai 和 bi 组成(1 ≤ ai,bi ≤ n,ai ≠ bi),这意味着在城市 ai 和 bi 之间应修建一条道路。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
4 1 1 3
输出 #1
3 1 2 4 2 2 3
注意
这是该示例的一种可能的解决方案:
以下是错误解决方案的示例: