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

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

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