В одной стране есть n городов. Изначально в этой стране нет дорог. Но вот, однажды король решает построить дороги, соединяющие пары городов. По дорогам можно путешествовать в любую сторону. Король хочет построить дороги так, чтобы можно было добраться из любого города в любой другой, проехав не более двух дорог. Также дано m пар городов — между этими парами городов дороги строить нельзя.
Ваша задача — построить как можно меньше дорог так, чтобы вышеперечисленные условия выполнялись. Ограничения гарантируют, что это возможно всегда.
Выходные данные
В первой строке выведите целое число s: наименьшее количество дорог, которые надо построить. Затем следует вывести s строк, по два целых числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) в каждой, означающих, что надо построить дорогу между городами ai и bi.
Если существует несколько решений, можно выводить любое.
Примечание
Ниже показано одно из возможных решений тестового примера:
Примеры неправильных решений:
Решение, изображенное на картинке выше, неверно из-за того, что количество построенных дорог не минимально (
4 против
3). Также, здесь строится дорога между городами
1 и
3, несмотря на то, что во входных данных указан запрет на строительство дороги между этой парой.
Решение, изображенное на картинке выше, неверно, так как нужно проехать по меньшей мере
3 дороги, чтобы попасть из города
1 в город
3, а в Вашем ответе должно быть возможно добраться из любого города в любой другой, пройдя не более
2 дорог.
И наконец, это решение неверно потому, что должна быть возможность добраться от любого города до любого другого, а в этом ответе невозможно добраться от
1 до
3, от
2 до
3, и от
4 до
3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
1 3
|
3
1 2
4 2
2 3
|