Вы можете зарегистрироваться и решать эту задачу здесь.
| Ограничение времени: | 5 с |
| Ограничение реального времени: | 10 с |
| Ограничение памяти: | 256M |
Белка в колесе
Журналистка Ксюша, постоялица палаты номер 13 заведения «Покосившийся Скворечник», убеждена, что она – белка. Сейчас, стоя у окна своей палаты, она смотрит на растущее за окном дерево (как известно любой белке, это связный граф без циклов) и воображает, как резвится, перебегая по нему с ветки на ветку и обратно. Главред Аркаша, сосед Ксюши, возмущён таким бесцельным и беспорядочным расходованием энергии, поэтому он хочет соорудить из какой-то части (возможно, всего) дерева колесо, то есть, добавить в граф несколько рёбер, чтобы создать цикл, по которому и будет бегать Ксюша, вырабатывая сверхценные идеи для издания. Но, к сожалению, у Аркаши есть всего две подтяжки, которые он готов пожертвовать на это благое дело, а значит, он может добавить не более, чем два ребра в дерево, при этом, он хочет получить цикл максимальной длины, и каждая вершина должна входить в него не более одного раза, не то Ксюша запутается и выдаст что-то не передовое или социально неодобряемое. Длина цикла, как знает любой главред, считается по количеству рёбер в нём. Поскольку Аркаша не привык работать сам, он ждёт, что Вы подскажете ему максимальную длину колеса для белки и между какими вершинами вешать подтяжки, а не то он Вас закенселит.
Первая строка ввода содержит единственное целое число n (3 ≤ n ≤ 105) – количество вершин дерева, растущего за окном. Следующие n-1 строк содержат пары целых чисел – номера вершин дерева, соединённых ребрами.
Первая строка вывода должна содержать одно число – максимальную достижимую длину колеса. Следующие 1 или 2 строки должны содержать пары целых чисел – какие пары вершин нужно соединить подтяжками, чтобы получить колесо нужной длины.
Примеры
| Входные данные | Результат работы |
|
4 1 2 2 3 3 4 |
4 1 4 |
|
4 1 2 1 3 1 4 |
4 2 3 2 4 |
Видеоразбор решения задачи здесь.