eolymp
bolt
Try our new interface for solving problems
Məsələlər

Недостающие мосты

Недостающие мосты

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

На Рис.1 изображена схема, состоящая из 4 островов, которые изображены точками и пронумерованы числами от 1 до 4, и 7 мостов, изображенных линиями, каждая из которых соединяет 2 разных острова.

prb8555.gif

По каждому мосту можно двигаться в обоих направлениях. Задача состоит в том, что стартуя с одного острова, нужно посетить каждый мост ровно один раз и вернуться в стартовую точку. Такой обход назовем 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 (n1000, m10000). На последующих m строках даны мосты, задающиеся парами номеров островов.

Çıxış verilənləri

В первой строке вывести число k необходимых новых мостов. Следующие k строк должны содержать новые мосты, задающиеся двумя номерами островов, которые данные мосты соединяют. Если оптимальных решений несколько, то выведите любое из них. Если новые мосты не нужны, вывести 0.

Nümunə

Giriş verilənləri #1
4 7
1 2
2 3
3 2
2 1
1 4
2 4
3 4
Çıxış verilənləri #1
2
1 4
2 3
Giriş verilənləri #2
4 5
1 2
2 3
3 1
3 4
3 4
Çıxış verilənləri #2
0
Mənbə 2017 IX International autumn tournament in informatics, Shumen, Junior, День 2, Задача E