题目描述

题目译自 NordicOI 2020 T3 「Christmas Gifts」

在北欧奥林匹克学院（Nordic Olympic Institute, NOI），$S$ 名学生有一个圣诞节互赠礼物的传统。具体来说，如果 $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,\ldots ,S$ 的数字表示，而不是使用他们的名字。

输入格式

第一行输入包含两个整数 $S$ 和 $F$ $(2 \leq S \leq 10^5, 1 \leq F \leq 2 \cdot 10^5)$，分别表示学生人数和朋友关系的数量。

接下来的 $F$ 行每行包含两个整数 $A$ 和 $B$ $(1 \leq A, B \leq S)$，表示 $A$ 和 $B$ 是朋友。所有朋友关系都是互相的，并且在输入中只出现一次。

输出格式

第一行输出可能的最小不公平分数。接下来的 $F$ 行，每行输出两个整数 $A$ 和 $B$，表示 $A$ 给 $B$ 送礼物。你可以按任意顺序输出这些关系，但每对朋友关系必须恰好输出一次。

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

2
2 4
4 3
1 3
3 2
2 1

在这个样例中，我们有 $4$ 名学生和 $5$ 对朋友关系。所示的方案不是唯一的，你可以输出任何正确的方案。

数据范围与提示

详细子任务附加限制及分值如下表所示。