Всеобъемлющая Галактическая Магистральная Сеть
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Всей Галактике известна Всеобъемлющая Галактическая Магистральная Сеть, соединяющая многие звёздные системы между собой. Эта транспортная сеть объединяет $$$n$$$ звёздных систем посредством $$$n-1$$$ магистралей — скоростных путей, соединяющих некоторые две звёздные системы между собой.

Главной особенностью этой магистральной сети является существование между любыми двумя звёздными системами ровно одного маршрута по этой сети.

У Галактической Федерации появилась возможность добавить в сеть одну дополнительную магистраль, соединяющую две разные звёздные системы, между которыми ещё не существует магистрали и, тем самым, разгрузить магистральную сеть.

Сложность постройки такой магистрали вызвано наличием развилок. Чтобы разгрузить транспортную сеть по максимуму, в любой звёздной системе существуют развилки. Развилки соединяют уникальным туннелем каждую пару магистралей, входящих в звёздную систему.

Таким образом, Федерация решила оценить, какое максимальное количество развилок может получиться во Всеобъемлющей Галактической Магистральной Сети после добавления одной магистрали, и поручила эту задачу Вам.

Входные данные

В первой строчке записано целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — количество звёздных систем в сети.

Далее идёт $$$n - 1$$$ строчка, описывающая пары звёздных систем $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), соединённые магистралями.

Выходные данные

В первой строчке выведите максимальное количество развилок, которое можно получить после добавления одной магистрали.

Во второй строчке выведите пару звёздных систем, соединив которые можно добиться максимального количества развилок.

Примеры

Входные данные
4
1 2
2 3
3 4
Выходные данные
5
1 3
Входные данные
6
1 2
1 3
1 4
4 5
4 6
Выходные данные
10
1 5