На Рис.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.