Paths#2988
A rectangular field consists of rows and columns. In one move, a game piece can move from a cell in one column to a cell in the next column. For each cell on the field, the row numbers of the next column's cells to which the piece can move are given. The piece cannot visit any cell more than once.
At the beginning of the game, the piece is placed on any cell in the first column. Then, it starts moving toward the last column. When the piece reaches the last column, it is placed again on any unvisited cell in the first column and continues moving. The game ends when the piece cannot make a move.
Write a program WAYS that, given , (1 \leq N \leq 50, 2 \leq M \leq 10) and the table of possible transitions between the cells, determines the maximum number of times the piece can be moved from the first to the last column of the field.
The first line contains and . Then follow M-1 blocks, each consisting of rows. Each block describes possible transitions for every cell of the field. Each -th row of the -th block describes possible transitions from the cell in the -th row and -th column. The first number in a row is the number of possible transitions from that cell, followed by the row numbers in the next column in ascending order, with no repetitions.
Output a single integer that corresponds to the maximum number of ways to move the piece from the first to the last column (The answer can be 0 if it is impossible to reach the last column from any cell of the first column).
For the sample input, the piece can be moved times, for example, along the following routes: (1\to 3\to 3), (2\to 4\to 4), and (4\to 2\to 2).
Example 1