Bridges

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

Входные данные: в первой строке числа N и M через пробел, далее M строк, содержащие пары чисел, разделённых пробелом – номера островов, которые соединяет мост.

Выходные данные: одно целое число - минимальное количество мостов, которые нужно захватить.