09. Дороги не только в Берляндии#

📝 Условие#

В стране n городов и n - 1 дорога, но граф может быть несвязным. За день можно закрыть одну дорогу и построить одну новую. Составьте план минимальной длины, после которого из любого города можно доехать в любой.

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

В первой строке число n (2 ≤ n ≤ 1000). Далее n − 1 строк a b — дороги (без петель и кратных дорог).

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

Число t — минимальное количество дней. Далее t строк i j u v: закрыть дорогу i–j и построить дорогу u–v.

Заметка

Если ответов несколько, можно вывести любой.

🧪 Тесты#

Тест 1#

Ввод:

2
1 2

Вывод:

0

Тест 2#

Ввод:

7
1 2
2 3
3 1
4 5
5 6
6 7

Вывод:

1
3 1 3 7

Тест 3#

Ввод:

6
1 2
2 3
1 3
4 5
5 6

Вывод:

1
1 3 3 6

Заметка

Оригинальное условие и проверка решения на всех тестах — по ссылке на источник.

💡 Подсказка#

⬅️ К списку задач уровня