Open autumn training |
Start: Nov.03.2021 at 12:00:00 PM
Finish: Nov.03.2021 at 04:00:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Bridges
Предположим, в ПсевдоПетрограде происходит псевдопереворот. Вожди
восстания понимают: архиважно захватить мосты, чтобы предотвратить
переброску юнкеров в ПсевдоЗимний дворец. События разворачиваются
на N островах, причём Псевдозимний на острове 1, а юнкера – на
острове N (N больше 1). В городе M мостов, про каждый известно,
с какого острова на какой он идёт (естественно, движение по мостам
осуществляется в обе стороны). Островов не более полусотни, мостов - ну, максимум штук сто.
Какое минимальное количество мостов нужно захватить, чтобы с N-го острова на 1-й невозможно было попасть ни напрямую, ни через другие острова?
Входные данные: в первой строке числа N и M через пробел, далее M строк, содержащие пары чисел, разделённых пробелом – номера островов, которые соединяет мост.
Выходные данные: одно целое число - минимальное количество мостов, которые нужно захватить.
Для отправки решений необходимо выполнить вход.
|