Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Всеобъемлющая Галактическая Магистральная Сеть

(Время: 1 сек. Память: 32 Мб Сложность: 51%)

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

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

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

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

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

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

В первой строке входного файла INPUT.TXT записано целое число n (3 ≤ n ≤ 2⋅105) — количество звёздных систем в сети. Далее идёт n−1 строка, описывающая пары звёздных систем ui и vi (1 ≤ ui, vi ≤ n), соединённые магистралями.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
14
1 2
2 3
3 4
5
1 3
26
1 2
1 3
1 4
4 5
4 6
10
1 5

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 A. Дистанционное обучение
 B. Код от сейфа
 C. Всеобъемлющая Галактическая Магистральная Сеть
 D. ДНК-палиндром
 E. Разлад Империй
 F. Раздача Фибоначчи
 G. Карты, числа, два заклинания
 H. Гипноз
 I. Круговой марафон
 J. Пасьянс по-иркутски
 K. Shark Attack

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru