在北欧奥林匹克学院（NOI），学生们有在圣诞节与朋友交换礼物的传统。更具体地说，如果 $A$ 和 $B$ 是朋友，要么 $A$ 送给 $B$ 一个礼物，要么 $B$ 送给 $A$ 一个礼物。

去年圣诞节，NOI 发生了一起大丑闻，因为有些学生收到了很多礼物却一个也没送出去，而有些学生送了很多礼物却一个也没收到。NOI 需要你的帮助来让这个圣诞礼物交换变得更加公平。你需要决定谁应该送礼物给谁，即对于 $A$ 和 $B$ 之间的每段好友关系，你需要决定是 $A$ 应该送礼物给 $B$，还是 $B$ 应该送礼物给 $A$。

设 $g_i$ 为学生 $i$ 送出的礼物数量，$r_i$ 为学生 $i$ 收到的礼物数量。NOI 管理层决定，一个公平的礼物交换方案应该使不公平度得分 $\sum_{i=1}^{S} |g_i - r_i|$ 最小。

给定 $F$ 段好友关系的列表，计算最小可能的不公平度得分，并对于每段好友关系，写出谁应该送礼物给谁。出于 GDPR（通用数据保护条例）的考虑，所有学生都用 $1, \dots, S$ 的编号代替了他们的名字。

输入格式

• 第 1 行：以空格分隔的整数 $S$ 和 $F$（$2 \le S \le 100000$ 且 $1 \le F \le 200000$）。
• 接下来的 $F$ 行：以空格分隔的整数 $A$ 和 $B$，表示 $A$ 和 $B$ 是朋友（$1 \le A < B \le S$）。

（输入中的所有好友关系都是双向的，且每段好友关系在输入中只会精确出现一次）

输出格式

• 第 1 行：最小可能的不公平度得分。
• 接下来的 $F$ 行：整数 $A$ 和 $B$，表示 $A$ 应该送礼物给 $B$（你可以以任何顺序输出这些行，但每段好友关系必须在输出中精确出现一次）。

样例

输入样例 1

4 5
1 2
2 3
2 4
1 3
3 4

输出样例 1

2
2 4
4 3
1 3
3 2
2 1

说明

在这个样例中，有 4 个学生和 5 段好友关系。给出的解不是唯一的——任何正确的解都将被接受。

子任务

你的解法将在一系列测试点上进行测试。要获得一个子任务的分数，你需要通过该子任务中的所有测试用例。