Недостающие мосты
Недостающие мосты
На Рис.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.
Giriş verilənləri
Первая строка стандартного ввода содержит натуральные числа n и m (n ≤ 1000, m ≤ 10000). На последующих m строках даны мосты, задающиеся парами номеров островов.
Çıxış verilənləri
В первой строке вывести число k необходимых новых мостов. Следующие k строк должны содержать новые мосты, задающиеся двумя номерами островов, которые данные мосты соединяют. Если оптимальных решений несколько, то выведите любое из них. Если новые мосты не нужны, вывести 0.
Nümunə
4 7 1 2 2 3 3 2 2 1 1 4 2 4 3 4
2 1 4 2 3
4 5 1 2 2 3 3 1 3 4 3 4
0