Codeforces Round 527 (Div. 3) |
---|
Закончено |
Задан лес — неориентированный граф из $$$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.
Название |
---|