CF527E Data Center Drama

某大型软件公司的数据中心项目由 $n$ 台计算机和 $m$ 根电缆组成。简单来说，每台计算机可以被看作一个盒子，有多根电缆从盒子中引出。每根电缆上传输着非常重要的信息，并且信息的传输方向只能是两种中的一种。由于数据中心的规划尚未最终批准，因此还未确定每根电缆的信息传输方向。不过，所有计算机都是连通的，即任意两台计算机之间都至少可以通过电缆直接或间接连接。 负责清洁数据中心的人叫 Claudia Ivanova，她非常喜欢用扎带把电缆捆成束。出于某些原因，她要求每台计算机上引出的所有电缆必须两两分组，如果无法做到这一点，她就会非常生气，用水桶的水“攻击”计算机。 还需要注意的是，因为非常重要的信息的特殊物理属性，严禁将信息流动方向不同的两根电缆捆在同一束内。 数据中心的管理层希望决定每根电缆的信息传输方向，使得 Claudia Ivanova 能按照上述条件对每台计算机的电缆分组。如果当前的连接方案无法实现这一点，你可以在方案中最少添加一些电缆。之后，你需要为每一根电缆指定信息的传输方向（是的，有时候数据中心的设计确实会根据保洁员的便利性做出调整……）

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100000$，$1 \leq m \leq 200000$），分别表示计算机的数量和已有的电缆数量。 接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$（$1 \leq a_i, b_i \leq n$），表示第 $i$ 根电缆连接了 $a_i$ 和 $b_i$ 这两台计算机。由于数据中心的结构可能非常复杂，同一对计算机之间可能有多根电缆，并且有些电缆可能会连接同一台计算机自身。

输出第一行为一个整数 $p$（$p \geq m$），表示最终方案中的总电缆数。 接下来的 $p$ 行，每行输出一对整数 $c_i, d_i$（$1 \leq c_i, d_i \leq n$），表示存在一根电缆，其信息流方向由 $c_i$ 指向 $d_i$。 输出中必须包含原计划中的所有电缆，并且每根电缆只能选取两种可能的方向之一。保证存在满足 $p \leq 500000$ 的解。 如果存在多个最小的 $p$ 的方案，输出任意一种即可。

下图为第一个样例测试的示意图，同一机箱引出的线缆成对绑定。  下图为样例输入二的方案，粗体为新增的电缆。  另一个输入二的可行方案：  由 ChatGPT 5 翻译