E2. Три дерева
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задача состоит из двух подзадач: за решение подзадачи E1 вы получите 11 баллов, за решение подзадачи E2 вы получите 13 баллов.

Деревом называется неориентированный связный граф, не содержащий циклов. Расстояние между двумя вершинами в дереве определяется как наименьшее количество ребер, которые надо пройти, чтобы попасть из одной из этих вершин в другую.

Вам дано 3 дерева, которые нужно объединить в одно посредством добавления двух ребер между данными деревьями. Каждое из этих ребер может соединять любую пару вершин из двух деревьев. После соединения деревьев, будут вычислены расстояния между всеми парами вершин в едином дереве. Найдите максимальное возможное значение суммы этих расстояний.

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

В первой строке через пробел записаны три целых числа n1, n2 и n3 — количества вершин в первом, втором и третьем дереве соответственно. Следующие n1 - 1 строк описывают первое дерево. Каждая из этих строк содержит два разделенных пробелом целых числа — номера вершин, соединенных ребром. Следующие n2 - 1 строк описывают второе дерево в том же формате. Далее следуют n3 - 1 строк, описывающие третье дерево в том же формате. Вершины в каждом из деревьев пронумерованы от 1 до количества вершин в соответствующем дереве.

Задача состоит из двух подзадач, которые отличаются друг от друга ограничениями на входные данные. За решение каждой подзадачи вы получите определенное количество баллов. Описание подзадач следует ниже.

  • В подзадаче E1 (11 баллов), количество вершин в каждом дереве будет между 1 и 1000, включительно.
  • В подзадаче E2 (13 баллов), количество вершин в каждом дереве будет между 1 и 100000, включительно.
Выходные данные

Выведите единственное целое число — наибольшую возможную сумму расстояний между всеми неупорядоченными парами вершин в объединенном дереве.

Примеры
Входные данные
2 2 3
1 2
1 2
1 2
2 3
Выходные данные
56
Входные данные
5 1 4
1 2
2 5
3 4
4 2
1 2
1 3
1 4
Выходные данные
151
Примечание

Рассмотрим первый пример. Есть два дерева, состоящих из двух вершин, и одно дерево с тремя вершинами. Наибольший ответ получается, когда все деревья соединены в одну цепочку из 7 вершин.

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

  • Соединить вершину 3 первого дерева с вершиной 1 второго;
  • Соединить вершину 2 третьего дерева с вершиной 1 второго;