Задан лес — неориентированный граф из \(n\) вершин такой, что каждая его компонента связности является деревом.
Диаметр (также «длиннейший кратчайший путь») связного неориентированного графа — это максимальное число ребер на кратчайшем пути между всеми парами вершин.
Ваша задача — добавить несколько ребер (возможно ноль) в граф так, чтобы он стал деревом, а диаметр этого дерева был минимально возможным.
Если существует несколько правильных ответов, то выведите любой.
Выходные данные
В первой строке выведите диаметр полученного дерева.
В каждой из следующих \((n - 1) - m\) строк выведите по два целых числа \(v\) и \(u\) (\(1 \le v, u \le n\), \(v \ne u\)) — описания добавленных ребер.
Полученный граф должен быть деревом, а его диаметр должен был минимально возможным.
Eсли \(m = n - 1\), то, очевидно, ребра не будут добавлены и весь вывод состоит из одного числа — диаметра заданного дерева.
Если существует несколько правильных ответов, то выведите любой.
Примечание
В первом примере добавление ребер (1, 4) или (3, 4) приведет к диаметру 3. Добавление ребра (2, 4), однако, сделает диаметр равным 2.
Ребро (1, 2) — это единственный вариант добавляемого ребра для второго примера. Диаметр равен 1.
В третьем примере нельзя добавить никаких ребер. Диаметр уже 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
2 3
|
2
4 2
|
|
2
|
2 0
|
1
1 2
|
|
3
|
3 2
1 3
2 3
|
2
|