EduBrick

Два непересекающихся пути

1000 мс · 256 МБ · всё или ничего

В дереве выберите два пути без общих вершин так, чтобы произведение их длин (в рёбрах) было наибольшим.

Формат ввода

В первой строке - число вершин nn (2≤n≤1052 \le n \le 10^5).

В следующих n−1n-1 строках - рёбра дерева.

Формат вывода

Выведите наибольшее произведение длин двух путей без общих вершин.

Примеры

ввод
4
1 2
2 3
3 4
вывод
1
ввод
6
1 2
2 3
2 4
5 4
6 4
вывод
4
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.