Məsələlər
Посёлки
Посёлки
В тридесятом государстве есть \textbf{N} деревень. Некоторые пары деревень соединены дорогами. В целях экономии, "лишних" дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом. Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение.
А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из \textbf{P} деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы). Вы должны написать программу, помогающую ему в этом.
\InputFile
Первая строка входного файла содержит два числа: \textbf{N} и \textbf{P} (\textbf{1} ≤ \textbf{P} ≤ \textbf{N} ≤ \textbf{150}). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от \textbf{1} до \textbf{N}), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.
\OutputFile
В выходной файл выведите единственное число -- искомое количество дорог.
Giriş verilənləri #1
11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11
Çıxış verilənləri #1
2
Şərh: Во втором примере группа деревень (1,2,3,6,7,8) окажется изолированной от остальных, если разрушить дороги 1-4 и 1-5.