Выведите план обменов для возвращения разумов героев в свои телав виде пар различных чисел

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

Во входном файле записаны целые числа N (4N20) и M(1M100) - количество героев Футурамы и количество произведенных обменов разумами.Герои занумерованы числами от 1 до N, изначально разум каждого из героев находится в своем теле. В последующих M строчках записана последовательность совершенных обменов разумами. Каждый обмен описывается двумя различными числами - номерами тел, которые, в этом обмене меняются разумами. Бубльгум Тэйт и Сладкий Клайд, как наиболее разумные герои, имеют номера N−1 и N, и гарантируется, что в исходных обменах они не участвовали.

Решения, верно работающие в случаях, когда каждое тело участвовало в обмене не больше одного раза будут набирать не менее 40 баллов.

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

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

Вернуть разумы героев в свои тела всегда возможно.
Помогите героям Футурамы вернуться в свои тела.
Примечание

Приведем таблицу положения героев в телах после каждого из обменов:



Примеры
Входные данные

4 1
1 2

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

1 3
2 4
1 4
2 3
3 4

0

0

Ну и такое бывает...
Новичок в программировании (

0

Вернуть героев Футурамы в свои тела

0