printРабочее место участника

printЗадачи

1599. Деревни

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В тридесятом государстве есть `N` деревень. Некоторые пары деревень соединены дорогами. В целях экономии, "лишних" дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом. Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.
Ввод
Первая строка входного файла содержит два числа `N` и `P` (`1\ ≤\ P\ ≤\ N\ ≤150`). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 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
Источник: Московская городская олимпиада школьников по программированию, 2002
loading