Дано дерево из \(n\) вершин, пронумерованных числами \(1, 2, \ldots, n\). Длина простого пути в дереве равна числу вершин в нём.
Вам нужно выбрать некоторое множество простых путей длины хотя бы \(2\) каждый, причём нельзя одновременно выбрать два разных пути, один из которых содержится в другом. Найдите наибольший возможный размер такого множества.
Формально, множество вершин \(S\) называется маршрутом, если в нём по крайней мере две вершины, при этом оно является множеством вершин некоторого простого пути в дереве. Набор попарно различных маршрутов называется расписанием. Маршрут \(S\) в расписании \(T\) называется избыточным, если есть какой-то другой маршрут \(S' \in T\), такой что \(S \subset S'\). Расписание называется эффективным, если в нём нет избыточных маршрутов. Найдите наибольшее возможное количество маршрутов в эффективном расписании.
Выходные данные
Выведите единственное число — ответ на задачу.
Примечание
В первом примере возможными эффективными расписаниями являются \(\{\{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\}\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
1 4
|
3
|
|
2
|
7
2 1
3 2
4 3
5 3
6 4
7 4
|
7
|