| Автор: | Владимир Ульянцев, Михаил Дворкин | Ограничение времени: | 2 сек | |
| Входной файл: | collider.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | collider.out |
Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере — только представить себе гигантских размеров кольцо, зарытое под землей!
Вдохновленный рассказом мага, Бильбо решил смастерить собственный коллайдер прямо у себя в норе. До начала строительства нора представляет собой множество комнат, причем некоторые пары комнат соединены коридорами. Как это принято у хоббитов, из любой комнаты в любую другую можно добраться по коридорам ровно одним способом.
Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!), есть возможность прокопать только один или два новых коридора.
После этого последовательность из нескольких комнат будет названа коллайдером. При этом должны быть выполнены следующие условия: первая комната в этой последовательности соединена коридором со второй, вторая — с третьей, и так далее, наконец, последняя комната последовательности должна быть соединена с первой. Кроме того, каждая комната может входить в эту последовательность не более одного раза.
Помогите Бильбо выбрать такие один или два новых коридора, чтобы коллайдер имел максимальную возможную длину, то есть состоял из максимального возможного числа комнат.
В первой строке входного файла содержится целое число n (3 ≤ n ≤ 105) — число комнат в норе Бильбо.
В следующих n − 1 строках содержатся по два целых числа — номера комнат, соединенных коридорами. Комнаты нумеруются от 1 до n.
В первую строку выходного файла выведите максимально возможное число комнат в коллайдере.
На следующих одной или двух строках выведите пары номеров комнат, между которыми следует прокопать новые коридоры.
Если существует несколько возможных планов строительства коллайдера максимальной длины, выведите любой из них.
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере — 1, 3, 2, 4.
| № | Входной файл (collider.in) |
Выходной файл (collider.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|