P14997 [Nordic OI 2020] 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 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 | 15 | $S \leq 10$ 且 $F \leq 20$ | | 2 | 15 | $S \leq 500$ 且 $F \leq 10000$ | | 3 | 50 | 无额外约束。 | | 4 | 20 | 所有学生都有偶数个朋友。 | 翻译由 DeepSeek V3 完成