B. Строим дорогу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В одной стране есть n городов. Изначально в этой стране нет дорог. Но вот, однажды король решает построить дороги, соединяющие пары городов. По дорогам можно путешествовать в любую сторону. Король хочет построить дороги так, чтобы можно было добраться из любого города в любой другой, проехав не более двух дорог. Также дано m пар городов — между этими парами городов дороги строить нельзя.

Ваша задача — построить как можно меньше дорог так, чтобы вышеперечисленные условия выполнялись. Ограничения гарантируют, что это возможно всегда.

Входные данные

Первая строка содержит два целых числа, n и m .

Затем следует m строк, каждая строка состоит из двух целых чисел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), показывающих, что нельзя строить дорогу между городами ai и bi. Считайте, что города пронумерованы от 1 до n.

Гарантируется, что каждая пара городов упоминается во входных данных ровно один раз.

Выходные данные

В первой строке выведите целое число s: наименьшее количество дорог, которые надо построить. Затем следует вывести s строк, по два целых числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) в каждой, означающих, что надо построить дорогу между городами ai и bi.

Если существует несколько решений, можно выводить любое.

Примеры
Входные данные
4 1
1 3
Выходные данные
3
1 2
4 2
2 3
Примечание

Ниже показано одно из возможных решений тестового примера:

Примеры неправильных решений:

Решение, изображенное на картинке выше, неверно из-за того, что количество построенных дорог не минимально (4 против 3). Также, здесь строится дорога между городами 1 и 3, несмотря на то, что во входных данных указан запрет на строительство дороги между этой парой.
Решение, изображенное на картинке выше, неверно, так как нужно проехать по меньшей мере 3 дороги, чтобы попасть из города 1 в город 3, а в Вашем ответе должно быть возможно добраться из любого города в любой другой, пройдя не более 2 дорог.
И наконец, это решение неверно потому, что должна быть возможность добраться от любого города до любого другого, а в этом ответе невозможно добраться от 1 до 3, от 2 до 3, и от 4 до 3.