J. Посвящение в студенты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро в Берляндском университете состоится посвящение первокурсников в студенты. Организаторы посвящения придумывают программу этого праздника. По их мнению, было бы хорошо, если бы новоиспечённые студенты подарили друг другу небольшие сувениры. Когда они озвучили эту идею первокурсникам, то выяснили следующее:

  • некоторые пары первокурсников уже знакомы друг с другом;
  • каждый первокурсник согласен дарить сувениры только тем, с кем он уже знаком;
  • каждый первокурсник не хотел бы дарить много сувениров.

Организаторы записали все пары знакомых между собой первокурсников и теперь хотят определить для каждого первокурсника, кому он должен подарить сувениры. По мнению организаторов, в каждой паре знакомых между собой первокурсников ровно один должен подарить сувенир другому.

Первокурсники уже решили назвать самым невезучим того, кому придётся дарить наибольшее количество сувениров. Организаторы в ответ пообещали, что самый невезучий будет минимально невезучим: конечно, ему придётся дарить наибольшее количество сувениров по сравнению с остальными, но это количество будет минимально возможным.

Организаторам очень некогда, и они обратились к вам с просьбой определить для каждой пары знакомых первокурсников, кто кому должен подарить сувенир.

Входные данные

В первой строке содержатся два целых числа n и m (1 ≤ n ≤ 5000, 0 ≤ m ≤ min(5000, n·(n - 1) / 2)) — количество первокурсников и количество пар первокурсников, знакомых между собой. Студенты пронумерованы от 1 до n.

В каждой из следующих m строк содержится по два целых числа xi, yi (1 ≤ xi, yi ≤ n, xi ≠ yi) — номера первокурсников, знакомых между собой.

Гарантируется, что любая пара содержится в списке единожды. Также гарантируется, что если в списке содержится пара (xi, yi), в нём не содержится пара (yi, xi).

Выходные данные

В первой строке выведите единственное целое число — минимальное количество сувениров, которые подарит самый невезучий первокурсник.

В каждой из следующих m строк выведите по одной паре номеров знакомых между собой первокурсников. Первым в паре выводите номер того первокурсника, который будет дарить сувенир.

Пары можно выводить в любом порядке. Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
5 4
2 1
1 3
2 3
2 5
Выходные данные
1
1 2
2 3
3 1
5 2
Входные данные
4 3
1 2
1 3
1 4
Выходные данные
1
1 4
2 1
3 1
Входные данные
4 6
1 2
4 1
4 2
3 2
4 3
1 3
Выходные данные
2
1 4
1 3
2 1
2 3
3 4
4 2