Вася играет во FreeDiv. В этой игре он управляет огромным государством, в котором имеется n городов и m двусторонних дорог между ними. К сожалению, не из каждого города можно добраться до любого другого по этим дорогам. Поэтому Вася решил разделить государство на провинции так, что в каждой провинции из каждого города можно добраться до всех городов этой провинции, но между провинциями дорог нет.

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

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