I. Избыточные маршруты
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$n$$$ вершин, пронумерованных числами $$$1, 2, \ldots, n$$$. Длина простого пути в дереве равна числу вершин в нём.

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

Формально, множество вершин $$$S$$$ называется маршрутом, если в нём по крайней мере две вершины, при этом оно является множеством вершин некоторого простого пути в дереве. Набор попарно различных маршрутов называется расписанием. Маршрут $$$S$$$ в расписании $$$T$$$ называется избыточным, если есть какой-то другой маршрут $$$S' \in T$$$, такой что $$$S \subset S'$$$. Расписание называется эффективным, если в нём нет избыточных маршрутов. Найдите наибольшее возможное количество маршрутов в эффективном расписании.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 3000$$$).

Далее следуют $$$n - 1$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — номера вершин, соединённых $$$i$$$-м ребром.

Гарантируется, что заданные ребра образуют дерево.

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

Выведите единственное число — ответ на задачу.

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

В первом примере возможными эффективными расписаниями являются $$$\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$$$ и $$$\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$$$.

Во втором примере можно выбрать $$$\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$$$.