Проблема обміну розумом#3178
У відомій математичній задачі, натхненній епізодом серіалу «Футурама», кілька людей помінялися розумом за допомогою машини для обміну розумом. У машини є одне важливе обмеження: будь-які дві людини можуть помінятися розумом одна з одною не більше одного разу.
Після певної кількості обмінів всі хочуть повернутися до свого початкового тіла. Однак, оскільки кожна пара може помінятися лише один раз, пряме повернення неможливе. Розв'язок потребує використання не більше двох додаткових «помічників», які ще не брали участі в жодних обмінах.
Дано історію вже здійснених обмінів. Визначте послідовність додаткових обмінів, щоб повернути всіх у свої тіла.
У першому рядку задані числа (2 \leq n \leq 200) — кількість людей, і (1 \leq m \leq \frac{n(n-1)}{2}) — кількість вже здійснених обмінів. У наступних рядках наведені описи обмінів. Всі тіла пронумеровані від до . Кожен обмін задається двома числами , (1 \leq a, b \leq n) — номерами тіл, що брали участь в обміні. Обміни наведені у хронологічному порядку.
У першому рядку виведіть кількість обмінів, необхідних для повернення всіх у свої тіла. Далі виведіть самі обміни у тому порядку, у якому їх треба виконувати, по одному у рядку, у такому ж форматі, як і у вхідних даних. Можна вивести будь-яку коректну послідовність обмінів, але не більше двох додаткових тіл. Додаткові тіла мають мати номери n+1 і n+2. Після всіх обмінів додаткові тіла також мають опинитися у своєму початковому стані. Загальна кількість обмінів у вашому розв'язку не повинна перевищувати .
Приклад 1