题目描述

某大型软件公司的一个数据中心项目由 $n$ 台计算机和连接它们的 $m$ 根电缆组成。简单来说，每台计算机都可以看作一个盒子，有多根电缆从盒子中伸出。非常重要的信息会沿着每根电缆的两个方向之一传输。由于数据中心的方案尚未获得批准，目前还没有确定信息将沿每根电缆的哪个方向传输。这些电缆的布置方式保证每台计算机都与其他每台计算机相连，也许需要经过一些其他计算机。

负责清洁数据中心的人将是清洁工 Claudia Ivanova。她喜欢用扎带把电缆绑成一束。出于某些原因，她会把从一台计算机伸出的电缆每两根分成一组；如果无法做到这一点，她就会非常生气，并用桶里的水攻击这台计算机。

还需要注意的是，由于非常重要的信息具有特殊的物理特性，严格禁止把两根信息流向不同的电缆绑在同一束中。

数据中心管理层想要确定如何让信息沿每根电缆传输，使得 Claudia Ivanova 能够把每台计算机伸出的所有电缆都分成两根一组，并满足上述条件。由于现有连接方案可能无法做到这一点，你可以向方案中添加尽可能少的电缆，然后需要确定每根电缆上信息流的方向（是的，有时数据中心的设计会基于清洁工的便利性……）

输入格式

第一行包含两个整数 $n$ 和 $m$（ $1\le n\le 100000$，$1\le m\le 200000$ ）——分别表示计算机的数量和已经存在的电缆数量。

接下来的每一行包含两个整数 $a_{i},b_{i}$（ $1\le a_{i},b_{i}\le n$ ）——表示第 $i$ 根电缆连接的两台计算机的编号。数据中心通常具有非常复杂的结构，因此一对计算机之间可能有不止一对电缆，某些电缆也可能连接一台计算机自身。

输出格式

第一行输出一个整数 $p$（ $p\ge m$ ）——最终方案中的最小电缆数量。

接下来的 $p$ 行中，每行输出一对整数 $c_{i},d_{i}$（ $1\le c_{i},d_{i}\le n$ ），描述一根电缆。这样的输出表示信息将沿某根电缆从 $c_{i}$ 流向 $d_{i}$。

你输出的电缆中应当包含原方案中存在的所有电缆，并且每根原有电缆可以采用两个可能方向之一。保证存在一种解使得 $p$ 不超过 $500000$。

如果存在多种使 $p$ 取到最小可能值的解，输出任意一种即可。

4 6
1 2
2 3
3 4
4 1
1 3
1 3

6
1 2
3 4
1 4
3 2
1 3
1 3

3 4
1 2
2 3
1 1
3 3

6
2 1
2 3
1 1
3 3
3 1
1 1

提示

第一个样例测试的图片。被绑在一起的一对电缆显示为从同一点伸出。

题面中第二个测试的图片。添加的电缆以粗体绘制。

第二个样例测试的另一种答案：