CF527E.Data Center Drama

The project of a data center of a Big Software Company consists of n computers connected by m cables. Simply speaking, each computer can be considered as a box with multiple cables going out of the box. Very Important Information is transmitted along each cable in one of the two directions. As the data center plan is not yet approved, it wasn't determined yet in which direction information will go along each cable. The cables are put so that each computer is connected with each one, perhaps through some other computers.

The person in charge of the cleaning the data center will be Claudia Ivanova, the janitor. She loves to tie cables into bundles using cable ties. For some reasons, she groups the cables sticking out of a computer into groups of two, and if it isn't possible, then she gets furious and attacks the computer with the water from the bucket.

It should also be noted that due to the specific physical characteristics of the Very Important Information, it is strictly forbidden to connect in one bundle two cables where information flows in different directions.

The management of the data center wants to determine how to send information along each cable so that Claudia Ivanova is able to group all the cables coming out of each computer into groups of two, observing the condition above. Since it may not be possible with the existing connections plan, you are allowed to add the minimum possible number of cables to the scheme, and then you need to determine the direction of the information flow for each cable (yes, sometimes data centers are designed based on the janitors' convenience...)

一家大型软件公司的数据中心项目由 $n$ 台计算机和 $m$ 根电缆构成。简而言之，每台计算机可视为一个盒子，有多根电缆从该盒子中引出。非常重要的信息沿每根电缆在两个方向之一进行传输。由于数据中心设计方案尚未获批，目前尚未确定每根电缆上信息的具体传输方向。这些电缆的布设方式保证了任意两台计算机之间均存在（可能经由其他计算机中转的）连通路径。

负责数据中心清洁工作的将是保洁员克劳迪娅·伊万诺娃（Claudia Ivanova）。她喜欢用扎带将电缆捆扎成束。出于某些原因，她总是将从一台计算机引出的所有电缆两两配对捆扎；若无法实现完全两两配对，则她会勃然大怒，并用水桶里的水攻击该计算机。

还需注意：由于“非常重要的信息”具有特殊的物理特性，严格禁止将两根信息流向相反的电缆捆扎在同一束中。

数据中心管理层希望确定每根电缆上的信息流向，使得克劳迪娅·伊万诺娃能够将每台计算机引出的所有电缆全部两两配对捆扎，且满足上述约束条件。由于在当前连接方案下该目标未必可行，你被允许向现有拓扑中添加最少数量的新电缆；随后，你需要为所有电缆（包括新增的） 确定信息的传输方向。（是的，有时数据中心的设计确实要以保洁员的便利性为优先考量……）

The first line contains two numbers, n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — the number of computers and the number of the already present cables, respectively.

Each of the next lines contains two numbers a__i, b__i (1 ≤ a__i, b__i ≤ n) — the indices of the computers connected by the i-th cable. The data centers often have a very complex structure, so a pair of computers may have more than one pair of cables between them and some cables may connect a computer with itself.

第一行包含两个数 $n$ 和 $m$（$1 \leq n \leq 100\,000$，$1 \leq m \leq 200\,000$）——分别表示计算机的数量和已存在的电缆数量。

接下来的每行包含两个数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$）——表示第 $i$ 条电缆所连接的两台计算机的编号。数据中心的结构通常非常复杂，因此一对计算机之间可能存在多条电缆，且某些电缆甚至可能将一台计算机与自身相连。

In the first line print a single number p (p ≥ m) — the minimum number of cables in the final scheme.

In each of the next p lines print a pair of numbers c__i, d__i (1 ≤ c__i, d__i ≤ n), describing another cable. Such entry means that information will go along a certain cable in direction from c__i to d__i.

Among the cables you printed there should be all the cables presented in the original plan in some of two possible directions. It is guaranteed that there is a solution where p doesn't exceed 500 000.

If there are several posible solutions with minimum possible value of p, print any of them.

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

接下来的 $p$ 行中，每行输出一对整数 $c_i,\,d_i$（$1 \leq c_i,\,d_i \leq n$），表示一条电缆。该条目表示信息将沿此电缆从 $c_i$ 单向传输至 $d_i$。

你所输出的所有电缆中，必须包含原始方案中的全部电缆（每条电缆可任选两个可能方向之一）。题目保证存在满足 $p \leq 500\,000$ 的解。

若存在多个满足最小 $p$ 值的可行解，输出任意一个即可。

Picture for the first sample test. The tied pairs of cables are shown going out from the same point.

Picture for the second test from the statement. The added cables are drawin in bold.

Alternative answer for the second sample test:

第一个样例测试的示意图。图中从同一点引出的成对电缆表示已连接（绑扎）。

题目中第二个测试的示意图。新增加的电缆用粗线标出。

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