eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Деревни

Деревни

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из p деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).

Вы должны написать программу, помогающую ему в этом.

Входные данные

Первая строка содержит два числа n и p (1pn150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до n), которые эта дорога соединяет. Все входные числа разделены пробелами и/или переводами строки.

Выходные данные

Выведите единственное число – искомое количество дорог.

Пример

Входные данные #1
3 2
1 2
3 2
Выходные данные #1
1
Входные данные #2
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
Выходные данные #2
2