Задача . G. Приватизация дорог в Древляндии

Древляндия состоит из \(n\) городов и \(n-1\) дороги. Все дороги являются двусторонними и соединяют пару различных городов. Из любого города по дорогам можно добраться до любого другого. Всё верно, топология страны — это именно неориентированное дерево.

В Древляндии есть несколько частных дорожных компаний. Правительство решило передать дороги в собственность компаний. После приватизации каждая дорога будет принадлежать какой-то одной компании, одна компания может владеть несколькими дорогами.

Правительство обеспокоено возможными обвинениями в пристрастности. В правительстве полагают, что люди города могут посчитать несправедливой ситуацию, если две или более дороги, входящие в этот город, принадлежат одной компании. Правительство планирует такую приватизацию, что количество таких городов не будет превосходить \(k\), а количество частных компаний (которые участвуют в приватизации) — минимально.

Выберите такое минимальное количество компаний \(r\), что возможно распределить все дороги по этим компаниям так, что количество городов с двумя или более дорогами одной компании не превосходит \(k\). Другими словами, назовём город хорошим, если все его дороги принадлежат различным компаниям. Ваша задача найти минимальное \(r\), что существует распределение всех дорог по компаниям от \(1\) до \(r\), что количество не являющимися хорошими городов не превосходит \(k\).

Картинка иллюстрирует первый пример (\(n=6, k=2\)). Ответ на этот тест содержит \(r=2\) компании. Числа на рёбрах соответствуют номерам дорог. Цвета рёбер соответствуют компаниям: красный цвет обозначает первую компанию, синий цвет обозначает вторую компанию. Серая вершина (с номером \(3\)) соответвует городу, который не является хорошим. Количество таких вершин (в данном случае, только одна) не превосходит \(k=2\). Невозможно получить не более \(k=2\) таких вершин, если ответ содержит только одну компанию.