Егор и его друг Арсений в этом году заканчивают учиться в школе и уже скоро поступят университет. И так как они очень ответственные ребята, они начали готовиться к поступлению уже сейчас.
Прежде всего они решили позаботиться о том, где будут жить долгие четыре года обучения, и зайдя на сайт университета, выяснили, что общежитие университета можно представить в виде корневого дерева из \(n\) вершин с корнем в вершине \(1\). В дереве каждая вершина представляет собой рекреацию с некоторым видом активности \(a_i\). Друзьям нужно выбрать \(2\) рекреации (не обязательно различные), в которых они поселятся. Ребята убеждены, что тем будет веселее их жизнь, чем больше значение следующей функции \(f(u, v) = diff(u, lca(u, v)) \cdot diff(v, lca(u, v))\). Помогите Егору и Арсению и найдите максимальное значение \(f(u, v)\) среди всех пар рекреаций!
\(^{\dagger} diff(u, v)\) — количество различных активностей, выписанных на простом пути от вершины \(u\) до вершины \(v\).
\(^{\dagger} lca(u, v)\) — такая вершина \(p\), что она находится на максимальном расстоянии от корня и является предком и вершины \(u\), и вершины \(v\).
Выходные данные
Для каждого набора входных данных выведите максимальное значение \(f(u, v)\), по всем парам рекреаций \((u, v)\).
Примечание
Рассмотрим четвертый набор входных данных. Дерево имеет такой вид:
Все рекреации раскрашены в цвета. Одинаковые цвета означает что активности в рекреациях совпадают. Рассмотрим пару вершин
\((11, 12)\),
\(lca(11, 12) = 1\). Выпишем все активности на пути от
\(11\) до
\(1\) —
\([11, 5, 1, 11]\), среди них различных активностей
\(3\), то есть
\(diff(11, 1) = 3\). Также выпишем все активности на пути от
\(12\) до
\(1\) —
\([7, 8, 2, 11]\), среди них различных активностей
\(4\), то есть
\(diff(12, 1) = 4\). Получаем что
\(f(11, 12) = diff(12, 1) \cdot diff(11, 1) = 4 \cdot 3 = 12\), что и является ответом для данного дерева. Можно показать, что ответ лучше получить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1
1 2
7
1 1 2 2 3 3
6 5 2 3 6 5 6
13
1 1 1 2 2 2 3 3 4 5 6 6
2 2 2 1 4 9 7 2 5 2 1 11 2
12
1 1 1 2 2 3 4 4 7 7 6
11 2 1 11 12 8 5 8 8 5 11 7
|
2
9
9
12
|