Задача состоит из двух подзадач: за решение подзадачи E1 вы получите 11 баллов, за решение подзадачи E2 вы получите 13 баллов.
Деревом называется неориентированный связный граф, не содержащий циклов. Расстояние между двумя вершинами в дереве определяется как наименьшее количество ребер, которые надо пройти, чтобы попасть из одной из этих вершин в другую.
Вам дано 3 дерева, которые нужно объединить в одно посредством добавления двух ребер между данными деревьями. Каждое из этих ребер может соединять любую пару вершин из двух деревьев. После соединения деревьев, будут вычислены расстояния между всеми парами вершин в едином дереве. Найдите максимальное возможное значение суммы этих расстояний.
Выходные данные
Выведите единственное целое число — наибольшую возможную сумму расстояний между всеми неупорядоченными парами вершин в объединенном дереве.
Примечание
Рассмотрим первый пример. Есть два дерева, состоящих из двух вершин, и одно дерево с тремя вершинами. Наибольший ответ получается, когда все деревья соединены в одну цепочку из 7 вершин.
Во втором примере для получения максимального ответа можно вставить новые ребра следующим образом:
- Соединить вершину 3 первого дерева с вершиной 1 второго;
- Соединить вершину 2 третьего дерева с вершиной 1 второго;
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 3
1 2
1 2
1 2
2 3
|
56
|
|
2
|
5 1 4
1 2
2 5
3 4
4 2
1 2
1 3
1 4
|
151
|