Добрый день сообщество Codeforces!

Сегодня услышал такую задачу. Вы работаете полицейским в стране, где N городов и M дорог между ними (могут быть петли и кратные ребра). С тюрьмы, которая находиться в городе 1, сбежал преступник и известно, что если он попадет в город N, то там он сможет скрыться. За один день преступник может попасть в любой город, соседний с тем, где он находиться. В начале каждого дня Вы можете перекрыть одну дорогу, и она будет недоступна для преступника в все последующие дни. Преступник будет пойман в скором времени, если не доберется до города N. Определите, сможете ли Вы поймать преступника или он все же скроется?

2≤N≤100, 1≤М≤100