Скоро в Берляндском университете состоится посвящение первокурсников в студенты. Организаторы посвящения придумывают программу этого праздника. По их мнению, было бы хорошо, если бы новоиспечённые студенты подарили друг другу небольшие сувениры. Когда они озвучили эту идею первокурсникам, то выяснили следующее:
- некоторые пары первокурсников уже знакомы друг с другом;
- каждый первокурсник согласен дарить сувениры только тем, с кем он уже знаком;
- каждый первокурсник не хотел бы дарить много сувениров.
Организаторы записали все пары знакомых между собой первокурсников и теперь хотят определить для каждого первокурсника, кому он должен подарить сувениры. По мнению организаторов, в каждой паре знакомых между собой первокурсников ровно один должен подарить сувенир другому.
Первокурсники уже решили назвать самым невезучим того, кому придётся дарить наибольшее количество сувениров. Организаторы в ответ пообещали, что самый невезучий будет минимально невезучим: конечно, ему придётся дарить наибольшее количество сувениров по сравнению с остальными, но это количество будет минимально возможным.
Организаторам очень некогда, и они обратились к вам с просьбой определить для каждой пары знакомых первокурсников, кто кому должен подарить сувенир.
Выходные данные
В первой строке выведите единственное целое число — минимальное количество сувениров, которые подарит самый невезучий первокурсник.
В каждой из следующих m строк выведите по одной паре номеров знакомых между собой первокурсников. Первым в паре выводите номер того первокурсника, который будет дарить сувенир.
Пары можно выводить в любом порядке. Если существует несколько решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
2 1
1 3
2 3
2 5
|
1
1 2
2 3
3 1
5 2
|
|
2
|
4 3
1 2
1 3
1 4
|
1
1 4
2 1
3 1
|
|
3
|
4 6
1 2
4 1
4 2
3 2
4 3
1 3
|
2
1 3
2 1
2 4
3 2
4 1
4 3
|