Всеобъемлющая Галактическая Магистральная Сеть
(Время: 1 сек. Память: 32 Мб Сложность: 51%)
Всей Галактике известна Всеобъемлющая Галактическая Магистральная Сеть, соединяющая многие звёздные системы между собой. Эта транспортная сеть объединяет n звёздных систем посредством n−1 магистралей — скоростных путей, соединяющих некоторые две звёздные системы между собой.
Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети.
У Галактической Федерации появилась возможность добавить в сеть одну дополнительную магистраль, соединяющую две разные звёздные системы, между которыми ещё не существует магистрали и, тем самым, разгрузить магистральную сеть.
Сложность постройки такой магистрали вызвано наличием развилок. Чтобы разгрузить транспортную сеть по максимуму, в любой звёздной системе существуют развилки. Развилки соединяют уникальным туннелем каждую пару магистралей, входящих в звёздную систему.
Таким образом, Федерация решила оценить, какое максимальное количество развилок может получиться во Всеобъемлющей Галактической Магистральной Сети после добавления одной магистрали, и поручила эту задачу Вам.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (3 ≤ n ≤ 2⋅105) — количество звёздных систем в сети. Далее идёт n−1 строка, описывающая пары звёздных систем ui и vi (1 ≤ ui, vi ≤ n), соединённые магистралями.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите максимальное количество развилок, которое можно получить после добавления одной магистрали. Во второй строке выведите пару звёздных систем, соединив которые можно добиться максимального количества развилок.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 2
2 3
3 4 | 5
1 3 |
| 2 | 6
1 2
1 3
1 4
4 5
4 6 | 10
1 5 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
