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