CF847J.Students Initiation

Soon the first year students will be initiated into students at the University of Berland. The organizers of the initiation come up with a program for this holiday. In their opinion, it would be good if the first-year students presented small souvenirs to each other. When they voiced this idea to the first-year students, they found out the following:

• some pairs of the new students already know each other;
• each new student agrees to give souvenirs only to those with whom they are already familiar;
• each new student does not want to present too many souvenirs.

The organizers have written down all the pairs of first-year friends who are familiar with each other and now want to determine for each new student, whom they should give souvenirs to. In their opinion, in each pair of familiar students exactly one student must present a souvenir to another student.

First year students already decided to call the unluckiest the one who will have to present the greatest number of souvenirs. The organizers in return promised that the unluckiest will be unlucky to the minimum possible degree: of course, they will have to present the greatest number of souvenirs compared to the other students, but this number will be as small as possible.

Organizers are very busy, and they asked you to determine for each pair of first-year friends who and to whom should present a souvenir.

很快，一年级新生将正式成为贝尔兰大学的学生。迎新活动的组织者为这一节日策划了一项活动。在他们看来，如果一年级新生彼此互赠小礼物，将是一件很美好的事情。当他们向一年级新生提出这一想法时，得到了如下反馈：

• 某些新生之间已经相互认识；
• 每位新生只愿意向自己已经熟悉的人赠送礼物；
• 每位新生都不希望赠送过多的礼物。

组织者已将所有相互熟悉的新生对记录下来，现在希望为每位新生确定：他/她应当向谁赠送礼物。在组织者看来，在每一对相互熟悉的新生中，恰好有一人须向另一人赠送礼物。

一年级新生们已决定：将最终需要赠送礼物数量最多的人称为“最不幸者”。而组织者则承诺，将使“最不幸者”的不幸程度尽可能最小——即：此人虽仍需比其他所有人赠送更多礼物，但该最大数量将被降至可能的最小值。

组织者事务繁忙，因此委托你来确定：在每一对相互熟悉的新生中，究竟谁应向谁赠送礼物。

The first line contains two integers n and m (1 ≤ n ≤ 5000, 0 ≤ m ≤ min(5000, n·(n - 1) / 2)) — the number of the first year students and the number of pairs of the students that know each other. The students are numbered from 1 to n.

Each of the following m lines contains two integers x__i, y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i) — the students in each pair.

It is guaranteed that each pair is present in the list exactly once. It is also guaranteed that if there is a pair (x__i, y__i) in the list, then there is no pair (y__i, x__i).

第一行包含两个整数 $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)$。

Print a single integer into the first line — the smallest number of souvenirs that the unluckiest student will have to present.

Following should be m lines, each containing two integers — the students which are familiar with each other. The first number in the pair must be the student that will present the souvenir to the second student in the pair.

Pairs can be printed in any order. If there are many solutions, print any of them.

在第一行输出一个整数——最不幸的学生需要送出的纪念品的最小数量。

接下来应有 $m$ 行，每行包含两个整数——彼此熟悉的两名学生。每对中第一个数字表示将向第二个数字所代表的学生赠送纪念品的学生。

这些对可以以任意顺序输出。若存在多个解，输出任意一个即可。