Paths
A rectangular field is composed of N rows and M columns. In one move, a game piece can transition from a cell in one column to a cell in the next column. For each cell on the field, the possible row numbers in the next column to which the piece can move are provided. The piece cannot revisit any cell it has already occupied.
At the beginning of the game, the piece is placed on any cell in the first column. From there, it moves towards the last column. Once the piece reaches the last column, it is repositioned on any unvisited cell in the first column, and the movement continues.
The game concludes when the piece can no longer make a move.
Write a program named WAYS that, given the numbers N and M (1 ≤ N ≤ 50, 2 ≤ M ≤ 10), along with the table of cell transitions, calculates the maximum number of times the piece can travel from the first to the last column of the field.
Input
The first line of the input file contains the numbers N and M. Following this, there are M-1 blocks, each containing N rows, which describe the possible transitions for each cell on the field. Each i–th row of the j–th block details the possible transitions from the cell in the i–th row and j–th column. The first number in the row indicates the number of possible transitions from that cell, followed by the row numbers of the next column in ascending order, with no repetitions.
Output
The output file should contain a single integer representing the maximum number of paths from the first to the last column (The answer can be 0 if it is impossible to reach any cell in the last column from any cell in the first column).
For the given example input, the piece can be moved 3 times, following routes such as: (1→3→3), (2→4→4), and (4→2→2).