题目描述

在 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 100000$，$1 \leq F \leq 200000$）。
• 接下来的 $F$ 行：每行两个由空格分隔的整数 $A$ 和 $B$，表示 $A$ 和 $B$ 是朋友（$1 \leq A < B \leq S$）。

（输入中的所有友谊都是相互的，并且每段友谊在输入中只会出现一次。）

输出格式

• 第一行：可能的最小不公平分数。
• 接下来的 $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 段友谊。所示解并非唯一——任何正确的解都将被接受。

评分细则

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

翻译由 DeepSeek V3 完成