CF847J Students Initiation

很快，新生们将在 Berland 大学正式成为学生。组织者为这个节日策划了一个活动。他们认为，如果新生们彼此赠送小纪念品会很不错。当他们把这个想法告诉新生时，得知了以下事实： - 有些新生之间已经互相认识； - 每个新生只愿意向自己已经认识的人赠送纪念品； - 每个新生都不想赠送太多纪念品。 组织者已经记录下了所有已经互相认识的新生对，现在他们想要决定每个新生到底应该向谁赠送纪念品。按照他们的设想，在每对认识的新生中，必须正好有一个人向另一个人赠送纪念品。 新生们已经决定，将不得不赠送最多纪念品的人称为“最倒霉的人”。而组织者则承诺，最倒霉的人也会是“最少倒霉”：当然“最倒霉”的人赠送的纪念品数量会比其他人都多，但这个数量应当尽量小。 由于组织者很忙，他们请求你，帮他们确定对于每一对认识的新生，谁应当向谁赠送纪念品。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5000$，$0 \leq m \leq \min(5000, n \cdot (n-1)/2)$）——新生的人数以及已互相认识的学生对数。新生从 $1$ 到 $n$ 编号。 接下来的 $m$ 行，每行包含两个整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$），表示相互认识的新生。 保证每对只出现一次，也保证如果有 $(x_i, y_i)$，就不会有 $(y_i, x_i)$。

输出第一行一个整数——最倒霉的人需要赠送的最小纪念品数。 接下来 $m$ 行，每行两个整数，表示认识的两位新生中是谁向谁赠送纪念品。第一位为赠送者，第二位为接受者。 输出顺序可以任意。如果有多组方案，输出任意一组即可。

由 ChatGPT 5 翻译