某大型软件公司的数据中心项目由n台计算机组成,通过m条电缆连接。简单来说,每台计算机可以被认为是一个盒子,盒子里有多根电缆。非常重要的信息沿着每根电缆以两个方向之一传输。由于数据中心计划尚未获得批准,因此尚未确定信息将沿着每条电缆传输的方向。电缆的放置使得每台计算机都相互连接(可能通过其他一些计算机)。
负责数据中心清洁的人员将是清洁工 Claudia Ivanova。她喜欢用扎带将电缆扎成束。由于某些原因,她将伸出计算机的电缆分成两组,如果不可能,她就会勃然大怒,用桶里的水攻击计算机。
还应该注意的是,由于非常重要信息的特定物理特性,严格禁止将信息流向不同方向的两根电缆连接在一束中。
数据中心的管理层希望确定如何沿着每条电缆发送信息,以便 Claudia Ivanova 能够将每台计算机的所有电缆分成两组,同时观察上述情况。由于现有的连接方案可能无法实现,因此您可以在方案中添加尽可能少的电缆数量,然后您需要确定每条电缆的信息流方向(是的,有时数据中心的设计是基于看门人的便利性......)
输入
第一行包含两个数字,n 和 m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — 分别是计算机的数量和已存在电缆的数量。
接下来的每一行包含两个数字 ai, bi (1 ≤ ai, bi ≤ n) — 第 i 根电缆连接的计算机的索引。数据中心通常具有非常复杂的结构,因此一对计算机之间可能有多对电缆,并且一些电缆可能将计算机与其自身连接。
输出
在第一行中打印一个数字 p (p ≥ m) — 最终方案中的最小电缆数量。
在接下来的 p 行中,每行打印一对数字 ci, di (1 ≤ ci, di ≤ n),描述另一根电缆。这样的输入意味着信息将沿着特定的电缆从ci 到di 的方向传送。
在您打印的电缆中,应该包含原始计划中在两个可能方向中的一些方向上呈现的所有电缆。保证存在 p 不超过 500 000 的解。
如果有几个可能的解,且 p 的可能值最小,则打印其中任何一个。
示例
输入 #1
4 6 1 2 2 3 3 4 4 1 1 3 1 3
输出 #1
6 1 2 3 4 1 4 3 2 1 3 1 3
输入 #2
3 4 1 2 2 3 1 1 3 3
输出 #2
6 2 1 2 3 1 1 3 3 3 1 1 1
注意
第一个样本测试的图片。显示成对的捆绑电缆从同一点引出。
声明中第二次测试的图片。添加的电缆以粗体绘制。
第二个样本测试的替代答案: