08. Prorva

Всем горнолыжным курортам Вася предпочитает Красный Борщ: там невысоко и некруто, зато вкусно. Подъёмник доставляет лыжника на вершину (пункт 0), откуда он, предварительно покушав в ресторане, начинает спуск. Трасса представляет собой совокупность расположенных на склоне кафе, соединённых лыжнями, ехать по которым можно только в одном направлении – вниз (в этом месте особо умные участники сказали «Ага, ориентированный граф!» - и они таки правы).

Цель Васи – выбрать такой маршрут спуска от пункта 0 до пункта N, на котором он сможет покушать наибольшее количество раз. А ваша цель – написать программу, определяющую, сколько раз Вася покушает на оптимальном маршруте.

Входные данные: ов первой строке – два натуральных числа через пробел, N и M, количество кафе (ресторан в пункте 0 в их число не входит) и количество лыжней между кафе. Далее M строк, описывающих лыжни, в каждой пара разделённых пробелом чисел («Ага, список рёбер!» - сказали особо умные участники, и эти зануды опять правы). Гарантируется, что N и M не превышают 100 и что данные корректны (нет циклов и тупиков).

Выходные данные: одно натуральное число, количество перекусов Васи.

Так уж и быть, приведём пример.
При вот таких входных данных –
4 7
0 1
2 4
0 2
1 4
2 1
0 3
3 4
– Вася при верном выборе пути покушает 4 раза: в пунктах 0, 2, 1 и 4.