Однажды Сеня прогуливался по Калининграду и обнаружил магазин интересных графов «Остовок». Этот магазин выделялся из многих обыденных магазинов графов тем, что в нём торговали только остовами (см. определение). Зайдя в магазин, Сеня обнаружил единственный оставшийся на прилавке граф — полный граф на $$$n$$$ вершинах (обозначается $$$K_n$$$), Сеня решил купить как можно больше остовов, полная дама Люси Декарт — продавщица магазина готова отрезать от графа любой остов, который ей укажет Сеня, стоимость остова равна его диаметру (см. определение). При вырезании остова из графа вершины в последнем остаются, но пропадают рёбра, содержащиеся в этом остове.

Необходимо найти максимальное количество остовов, которые может вырезать из $$$K_n$$$ Сеня, причём их общая стоимость должна быть минимальной возможной и предъявить эти остовы. То есть нужно найти как можно больше непересекающихся остовов, а из всех таких наборов, тот в котором сумма диаметров остовов будет минимальна.

Остов или остовное дерево графа — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа.

Дерево — это связный граф без циклов. Связность означает наличие маршрута между любой парой вершин.

Подграф — это часть графа, в которой мы берём некоторые его вершины и ребра. Другими словами, граф $$$H$$$ является подграфом графа $$$G$$$, если вершины и рёбра $$$H$$$ являются подмножеством вершин и рёбер $$$G$$$.

Диаметр графа — это число, равное расстоянию между наиболее удаленными друг от друга вершинами графа.