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

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

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

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

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