시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере --- только представить себе гигантских размеров кольцо, зарытое под землей!
Вдохновленный рассказом мага, Бильбо решил смастерить собственный коллайдер прямо у себя в норе. До начала строительства нора представляет собой множество комнат, причем некоторые пары комнат соединены коридорами. Как это принято у хоббитов, из любой комнаты в любую другую можно добраться по коридорам ровно одним способом.
Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо% (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.
После этого последовательность из нескольких комнат будет названа коллайдером. При этом должны быть выполнены следующие условия: первая комната в этой последовательности соединена коридором со второй, вторая --- с третьей, и так далее, наконец, последняя комната последовательности должна быть соединена с первой. Кроме того, каждая комната может входить в эту последовательность не более одного раза.
Помогите Бильбо выбрать такие один или два новых коридора, чтобы коллайдер имел максимальную возможную длину, то есть состоял из максимального возможного числа комнат.
В первой строке входного файла содержится целое число $n$ ($3 \le n \le 100\,000$) --- число комнат в норе Бильбо.
В следующих $n - 1$ строках содержатся по два целых числа --- номера комнат, соединенных коридорами. Комнаты нумеруются от $1$ до $n$.
В первую строку выходного файла выведите максимально возможное число комнат в коллайдере.
На следующих одной или двух строках выведите пары номеров комнат, между которыми следует прокопать новые коридоры.
Если существует несколько возможных планов строительства коллайдера максимальной длины, выведите любой из них.
4 1 2 2 3 3 4
4 1 4
4 1 2 1 3 1 4
4 2 3 2 4
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере --- 1, 3, 2, 4.