Deja Vu

Description:

Input:

The first line contains integers n and m — the number of shops and the number of streets, correspondingly, 1 ≤ n ≤ 50, . Next m lines contain the descriptions of the streets in the following format: x_i y_i k_i v₁ v₂ ... v_k, where x_i and y_i (1 ≤ x_i, y_i ≤ n, x_i ≠ y_i) are indices of shops connected by a street, k_i (0 ≤ k_i ≤ n) is the number of visions on the way from x_i to y_i; v₁, v₂, ..., v_k (1 ≤ v_i ≤ n) describe the visions: the numbers of the shops Neo saw. Note that the order of the visions matters.

It is guaranteed that the total number of visions on all streets doesn't exceed 10⁵.

• to get 50 points, you need to find any (not necessarily simple) path of length at most 2·n, that meets the attributes described above (subproblem E1);
• to get 50 more points, you need to count for each length from 1 to 2·n the number of paths that have the attribute described above (subproblem E2).

Output:

Subproblem E1. In the first line print an integer k (1 ≤ k ≤ 2·n) — the numbers of shops on Neo's path. In the next line print k integers — the number of shops in the order Neo passes them. If the graph doesn't have such paths or the length of the shortest path includes more than 2·n shops, print on a single line 0.

Subproblem E2. Print 2·n lines. The i-th line must contain a single integer — the number of required paths of length i modulo 1000000007 (10⁹ + 7).

Sample Input:

6 6
1 2 2 1 2
2 3 1 3
3 4 2 4 5
4 5 0
5 3 1 3
6 1 1 6

Sample Output:

4
6 1 2 3

Sample Input:

6 6
1 2 2 1 2
2 3 1 3
3 4 2 4 5
4 5 0
5 3 1 3
6 1 1 6

Sample Output:

1
2
1
1
2
1
1
2
1
1
2
1

Note:

The input in both samples are the same. The first sample contains the answer to the first subproblem, the second sample contains the answer to the second subproblem.