Открытая осенняя тренировка "На ДНЕ" |
Старт: 03.ноя.2021 в 12:00:00
Финиш: 03.ноя.2021 в 16:00:00
Турнир завершён!
• Турнирная таблица
|
|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Bridges
Предположим, в ПсевдоПетрограде происходит псевдопереворот. Вожди
восстания понимают: архиважно захватить мосты, чтобы предотвратить
переброску юнкеров в ПсевдоЗимний дворец. События разворачиваются
на N островах, причём Псевдозимний на острове 1, а юнкера – на
острове N (N больше 1). В городе M мостов, про каждый известно,
с какого острова на какой он идёт (естественно, движение по мостам
осуществляется в обе стороны). Островов не более полусотни, мостов - ну, максимум штук сто.
Какое минимальное количество мостов нужно захватить, чтобы с N-го острова на 1-й невозможно было попасть ни напрямую, ни через другие острова?
Входные данные: в первой строке числа N и M через пробел, далее M строк, содержащие пары чисел, разделённых пробелом – номера островов, которые соединяет мост.
Выходные данные: одно целое число - минимальное количество мостов, которые нужно захватить.
Для отправки решений необходимо выполнить вход.
|