Задача №113695. Большой огромный коллайдер
Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!
Вдохновленный рассказом мага, Бильбо решил смастерить собственный коллайдер прямо у себя в норе. До начала строительства нора представляет собой множество комнат, причем некоторые пары комнат соединены коридорами. Как это принято у хоббитов, из любой комнаты в любую другую можно добраться по коридорам ровно одним способом.
Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.
После этого последовательность из нескольких комнат будет названа коллайдером. При этом должны быть выполнены следующие условия: первая комната в этой последовательности соединена коридором со второй, вторая - с третьей, и так далее, наконец, последняя комната последовательности должна быть соединена с первой. Кроме того, каждая комната может входить в эту последовательность не более одного раза.
Помогите Бильбо выбрать такие один или два новых коридора, чтобы коллайдер имел максимальную возможную длину, то есть состоял из максимального возможного числа комнат.
В первой строке входного файла содержится целое число \(n\) (\(3 \le n \le 100\,000\)) - число комнат в норе Бильбо.
В следующих \(n - 1\) строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от \(1\) до \(n\).
В первую строку выходного файла выведите максимально возможное число комнат в коллайдере.
На следующих одной или двух строках выведите пары номеров комнат, между которыми следует прокопать новые коридоры.
Если существует несколько возможных планов строительства коллайдера максимальной длины, выведите любой из них.
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.
4 1 2 2 3 3 4
4 4 1
4 1 2 1 3 1 4
4 2 3 2 4