Prisoner of Benda
Даня любит сериалы. Один из его любимых сериалов — "Футурама". В одной серии происходят следующие события. С помощью изобретённой профессором Фарнсвортом машины он и Эми меняются телами с целью осуществить свои мечты: профессор жаждет острых ощущений, а Эми мечтает есть от пуза, не опасаясь за фигуру. Впоследствии выясняется, что обмен разумом между двумя телами возможен не более одного раза, и, чтобы вернуться обратно в свои тела, нужно произвести промежуточный обмен. Бендер предлагает свою помощь, однако, заполучив тело Эми, он тут же скрывается, чтобы под чужой личиной украсть корону императора Робо-Венгрии. Эми, недовольная возможностями профессорского тела в плане обжорства, уговаривает поменяться Лилу. Фрай приходит в ужас. Лила обижена и обвиняет Фрая в том, что его заботит только ее внешность. Фрай в отместку меняется телами с Зойдбергом. Бендер оказывается пойман при попытке ограбления, однако освобождается, убедив императора в том, что он — робот в теле человека. Узнав, что император втайне мечтает пожить немного жизнью простых людей, Бендер предлагает тому на время поменяться телами. Но так как профессор уехал рисковать жизнью в теле Бендера, пришлось подсунуть императору вместо своего корпуса автоматизированное помойное ведро. Фрай в теле Зойдберга и Лила в теле профессора встречаются в ресторане, чтобы выяснить отношения. В конце концов, они понимают, что любят друг друга вовсе не за внешность. При виде сцены их бурного примирения Эми, на этот раз уже в теле Гермеса, надолго теряет аппетит. Бендер, поменявшись телами с правителем Робо-Венгрии, наслаждается жизнью на его яхте. Однако именно в этот вечер заговорщики совершают покушение на императора. Жизнь Бендеру спасает появление профессора Фарнсворта. После того, как все герои решают свои личные проблемы, профессору с помощью Бубльгума Тэйта и Сладкого Клайда из команды "Ударники" удается вернуть всех в свои тела. Необходимо промоделировать, как у них получилось вернуть всех в свои тела. Будем считать, что уже произошло некоторое количество обменов телами. Нужно определить последовательность обменов, которая возвращает всех в свои тела, используя не более двух дополнительных тел. Не забываете, что каждая пара тел может меняться разумами не более одного раза.
Входные данные
Первая строка входного файла содержит числа n (2 ≤ n ≤ 200) — количество персонажей и m (1 ≤ m ≤ n(n-1)/2) — количество обменов телами, которые уже произошли. В следующих m строках идут описания обменов. Обозначим все тела участвующие в обменах числами от 1 до n. Тогда каждый обмен задается парой чисел a, b (1 ≤a, b ≤ n) — номера тел участвующих в данном обмене. Обмены даны в хронологическом порядке.
Выходные данные
В первой строке выходного файла выведите количество обменов необходимых для возвращения всех в свои тела. Далее необходимо вывести сами обмены в том порядке, в котором они должны быть произведены, по одному в строке в таком же формате, как и во входных данных. Можно вывести любое решение поставленной задачи, однако можно использовать не более двух дополнительных тел. Дополнительные тела следует обозначать номерами n+1 и n+2. После всех осуществленных обменов дополнительные персонажи также должны находиться в своих телах. Также количество обменов в предложенном решении не должно превышать 3n.