Відсутні мости
На Рис.1 зображена схема, що складається з 4 островів, позначених точками і пронумерованих від 1 до 4, та 7 мостів, зображених лініями, кожна з яких з'єднує 2 різні острови.
По кожному мосту можна рухатися в обох напрямках. Завдання полягає в тому, щоб, починаючи з одного острова, відвідати кожен міст рівно один раз і повернутися в початкову точку. Такий обхід називається all-bridges-walk.
Розв'язати таке завдання для островів і мостів, зображених на Рис.1, неможливо. Однак, якщо додати кілька мостів, all-bridges-walk стає можливим — наприклад, додавши нові мости, що з'єднують острів 4 з островом 1 і острів 2 з островом 3. На Рис.2 показана схема з чотирма островами і трьома мостами. Якщо для цієї схеми буде запропоновано завдання all-bridges-walk, то двох мостів від острова 3 до острова 4 буде достатньо для успішного виконання завдання.
У даній країні є n островів і m мостів. Напишіть програму, що знаходить мінімальну кількість мостів, які потрібно добудувати, щоб виконати all-bridges-walk.
Вхідні дані
Перша стрічка стандартного вводу містить натуральні числа n і m (n ≤ 1000, m ≤ 10000). На наступних m рядках дані мости, задані парами номерів островів.
Вихідні дані
У першому рядку виведіть число k необхідних нових мостів. Наступні k рядків повинні містити нові мости, задані двома номерами островів, які ці мости з'єднують. Якщо оптимальних рішень декілька, виведіть будь-яке з них. Якщо нові мости не потрібні, виведіть 0.