E. Лес минимального диаметра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан лес — неориентированный граф из $$$n$$$ вершин такой, что каждая его компонента связности является деревом.

Диаметр (также «длиннейший кратчайший путь») связного неориентированного графа — это максимальное число ребер на кратчайшем пути между всеми парами вершин.

Ваша задача — добавить несколько ребер (возможно ноль) в граф так, чтобы он стал деревом, а диаметр этого дерева был минимально возможным.

Если существует несколько правильных ответов, то выведите любой.

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

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 1000$$$, $$$0 \le m \le n - 1$$$) — количество вершин графа и количество ребер, соответственно.

В каждой из следующих $$$m$$$ строк записаны по два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) — описания ребер.

Гарантируется, что заданный граф — это лес.

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

В первой строке выведите диаметр полученного дерева.

В каждой из следующих $$$(n - 1) - m$$$ строк выведите по два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \ne u$$$) — описания добавленных ребер.

Полученный граф должен быть деревом, а его диаметр должен был минимально возможным.

Eсли $$$m = n - 1$$$, то, очевидно, ребра не будут добавлены и весь вывод состоит из одного числа — диаметра заданного дерева.

Если существует несколько правильных ответов, то выведите любой.

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

В первом примере добавление ребер (1, 4) или (3, 4) приведет к диаметру 3. Добавление ребра (2, 4), однако, сделает диаметр равным 2.

Ребро (1, 2) — это единственный вариант добавляемого ребра для второго примера. Диаметр равен 1.

В третьем примере нельзя добавить никаких ребер. Диаметр уже 2.