← 返回题目列表

Codeforces · 45/H

H. 道路问题

中文机器翻译题面 查看原题

Berland 首都(如您所知)包含 n 个交叉路口,其中一些对由双向道路连接。不幸的是,首都的交通拥堵情况急剧增加,这就是决定修建几条新道路的原因。每条道路应连接两个路口。

城市管理部门注意到,在所有发达国家的城市中,任何两条道路之间都可以沿着至少两条路径行驶,使得这些路径不共享任何道路(但它们可以共享同一个路口)。政府决定增加最少数量的道路,以便在柏林首都也能履行这一规定。改革前后城市路网中每对路口之间不应有超过一条道路。

输入

第一输入行包含一对整数 n, m (2 ≤ n ≤ 900, 1 ≤ m ≤ 100000),其中 n 是路口数量,m 是道路数量。以下 m 行中的每一行都包含一条道路的描述,该道路由所连接的路口 ai、bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 的编号给出。结点从 1 到 n 编号。沿着道路行驶的任何一个路口都可以到达城市的任何一个路口。

输出

在第一行打印 t — 添加的道路数量。然后在 t 行上以输入数据的格式打印添加的道路的描述。您可以使用任何顺序打印道路本身以及每条道路连接的路口。如果该问题有多种解决方案,请打印其中任何一个。

如果资本不需要改革,则打印单数0。

如果没有解决方案,则打印单个数字-1。

示例

输入 #1

4 3
1 2
2 3
3 4

输出 #1

1
1 4

输入 #2

4 4
1 2
2 3
2 4
3 4

输出 #2

1
1 3