eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Связность графа

Связность графа

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Дан граф, содержащий n вершин и m рёбер (1n1000, 1m7000).

Требуется найти наименьшее число рёбер и эти самые рёбра, которые нужно добавить, чтобы гарф стал связным.

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

Сначала заданы числа n и m, затем идёт описание рёбер графа - m пар чисел, где каждая пара описывает начало и конец ребра.

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

В первой строке вывести минимальное количество рёбер k, которое нужно добавить. В следующих k строках выведите по 2 числа - начало и конец нового ребра.

Пример

Входные данные #1
3 1
2 1
Выходные данные #1
1
1 3