Прямоугольное поле состоит из N строк и M столбцов. Игровая фишка за один ход может
переместиться с клетки одного столбца на одну из клеток следующего столбца. Для каждой клетки
поля известны номера строк клеток следующего столбца на которые фишка может сделать ход.
Фишка не может пойти на клетку, которую она уже посещала раньше.
В начале игры фишку устанавливают на произвольную клетку первого столбца. После этого фишка начинает
двигаться в сторону последнего столбца. Когда фишка достигает последнего столбца, ее снова устанавливают на любую
клетку первого столбца, которая не была посещена раньше, и возобновляют ее движение.
Игра завершается когда фишка не может сделать ход.
Задача
Напишите программу WAYS, которая по числам N, M
(1£N£50, 2£M£10),
и таблице переходов между клетками определяет какое наибольшее количество раз можно провести фишку от первого
до последнего столбца игрового поля.
Входные данные
В первой строке входного файла WAYS.DAT находятся числа N и M.
Далее следует M-1 блок
по N строк в каждом — описание возможных переходов для каждой клетки поля.
Каждая i–ая строка j–го блока описывает возможные переходы из клетки в i–ой строке и j–ом
столбце игрового поля.
Первое число в строке задает количество возможных переходов из клетки, после чего следуют номера
строк следующего столбца по возрастанию и без повторений.
Пример входных данных
4 3
2 1 3
3 1 2 4
0
2 2 3
1 2
1 2
1 3
2 2 4
Выходные данные
В единственной строке выходного файла WAYS.SOL должно находиться целое число, которое соответствует искомому
количеству путей. (Ответ может быть 0, если ни из одной клетки первого столбца нельзя достичь ни одной клетки последнего).
Для приведенного примера входных данных фишку можно провести
3 раза, например, по таким маршрутам:
(1®3®3), (2®4®4) и (4®2®2).
Пример выходных данных
