7. Рандомный Дрюня

Игрушечный робот Дрюня представляет собой недетерминированный (ужасно недетерминированный!) конечный автомат. При включении он всегда находится в состоянии 1. А далее вне зависимости от управляющих команд (Дрюня на них чихать хотел) случайным образом совершает один из возможных переходов в другое состояние, потом в следующее и так далее, пока его не выключат. Всего у Дрюни N состояний, N не больше сотни. Все его состояния, кроме одного, N-го, в общем-то терпимые и даже забавные. А вот N-е просто кошмарное: в этом состоянии Дрюня громко поёт математические примеры, спрягает и склоняет попавшие под руку предметы, при этом вонюче дымится и хаотично перемещается (поэтому даже не выключить его, заразу).

Программа для Дрюни — список из М возможных переходов между состояниями (любой переход возможен в обоих направлениях). И в магазине, где продают Дрюнь, могут изменить программу, убрав из неё сколько-то возможных переходов, — разумеется, не бесплатно.

Разработайте программу, определяющую минимальное количество переходов, которые надо удалить из программы Дрюни, чтобы он не смог перейти в кошмарное состояние N.

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

Может быть несколько переходов из одного состояния в другое (строки могут повторяться).

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

Пример: при таких вот входных данных
7 9
1 2
1 3
4 7
5 7
6 7
2 3
4 2
4 5
4 6
ответом будет 1: достаточно удалить переход 4 2.