CF331E2.Deja Vu

Everybody knows that we have been living in the Matrix for a long time. And in the new seventh Matrix the world is ruled by beavers.

So let's take beaver Neo. Neo has so-called "deja vu" outbursts when he gets visions of events in some places he's been at or is going to be at. Let's examine the phenomenon in more detail.

We can say that Neo's city is represented by a directed graph, consisting of n shops and m streets that connect the shops. No two streets connect the same pair of shops (besides, there can't be one street from A to B and one street from B to A). No street connects a shop with itself. As Neo passes some streets, he gets visions. No matter how many times he passes street k, every time he will get the same visions in the same order. A vision is a sequence of shops.

We know that Neo is going to get really shocked if he passes the way from some shop a to some shop b, possible coinciding with a, such that the list of visited shops in the real life and in the visions coincide.

Suggest beaver Neo such path of non-zero length. Or maybe you can even count the number of such paths modulo 1000000007 (109 + 7)?..

众所周知，我们早已长期生活在“矩阵”之中。而在全新的第七代矩阵中，世界由海狸统治。

让我们来认识一下海狸尼奥（Neo）。尼奥会经历一种名为“既视感”（déjà vu）的突发状态——此时他会预见到自己曾经到过或即将前往的某些地点所发生的事件。下面我们来更详细地考察这一现象。

我们可以将尼奥所在的城市建模为一个有向图，该图包含 $n$ 家商店和 $m$ 条连接这些商店的街道。任意两条街道不会连接完全相同的商店对（此外，不可能同时存在一条从 $A$ 到 $B$ 的街道和一条从 $B$ 到 $A$ 的街道）。不存在连接某家商店与其自身的街道。当尼奥经过某些街道时，他会产生幻视（visions）。无论他经过第 $k$ 条街道多少次，每次产生的幻视序列都完全相同，且顺序一致。每一段幻视本身即为一个商店序列。

我们已知：若尼奥沿某条从商店 $a$ 到商店 $b$（$a$ 与 $b$ 可能相同）的路径行进，且该路径在现实生活中所访问的商店序列，与他在幻视中所见的商店序列完全一致，则他将受到极大的惊吓。

请为海狸尼奥构造一条长度非零的满足上述条件的路径；或者，你甚至可以计算出所有此类路径的总数（对 $1000000007$（即 $10^9 + 7$）取模）？

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_1 _v_2 ... v__k, where x__i and y__i (1 ≤ x__i, y__i ≤ n, x__i ≠ y__i) are numbers 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_1, _v_2, ..., 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 105.

• 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).

第一行包含两个整数 $n$ 和 $m$ —— 分别表示商店的数量和街道的数量，其中 $1 \leq n \leq 50$，。接下来的 $m$ 行描述各条街道，每行格式为：$x_i\ y_i\ k_i\ v_1\ v_2\ \dots\ v_k$，其中 $x_i$ 和 $y_i$（满足 $1 \leq x_i, y_i \leq n$ 且 $x_i \ne y_i$）是该街道所连接的两家商店编号；$k_i$（满足 $0 \leq k_i \leq n$）表示从 $x_i$ 到 $y_i$ 的路径上所见“幻象”（visions）的数量；$v_1, v_2, \dots, v_k$（满足 $1 \leq v_i \leq n$）描述这些幻象：即尼奥（Neo）沿途所见到的商店编号。注意，幻象出现的顺序是重要的。

保证所有街道上的幻象总数不超过 $10^5$。

• 若要获得 50 分，你需要找出任意一条（不一定是简单路径）长度至多为 $2 \cdot n$ 的路径，使其满足上述属性（子问题 E1）；
• 若要再获得 50 分，你需要对每个长度 $1$ 至 $2 \cdot n$，分别计算满足上述属性的路径数量（子问题 E2）。

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 (109 + 7).

子问题 E1：第一行输出一个整数 $k$（$1 \leq k \leq 2\cdot n$）—— 表示 Neo 路径上的商店数量。下一行输出 $k$ 个整数，表示 Neo 经过的商店编号顺序。若图中不存在满足条件的路径，或最短路径所包含的商店数量超过 $2\cdot n$，则在单独一行输出 0。

子问题 E2：输出 $2\cdot n$ 行。第 $i$ 行必须包含一个整数——表示长度为 $i$ 的所需路径的数量对 $1000000007$（即 $10^9 + 7$）取模的结果。

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.

两个样例的输入相同。第一个样例包含第一个子问题的答案，第二个样例包含第二个子问题的答案。