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.