← 返回题目列表

Codeforces · 331/E1

E1. 似曾相识

中文机器翻译题面 查看原题

每个人都知道我们已经在矩阵中生活了很长时间。在新的第七部《黑客帝国》中,世界由海狸统治。

让我们以海狸 Neo 为例。当尼奥看到他曾经去过或即将去的某些地方发生的事件时,他会出现所谓的“似曾相识”的爆发。让我们更详细地研究一下这个现象。

我们可以说Neo的城市是用一个有向图来表示的,由n个商店和连接商店的m条街道组成。没有两条街道连接同一对商店(此外,不可能有一条从 A 到 B 的街道和一条从 B 到 A 的街道)。没有一条街道将商店与其自身连接起来。当尼奥经过一些街道时,他看到了幻象。无论他经过k街多少次,每次他都会以相同的顺序看到相同的景象。愿景是一系列商店。

我们知道,如果尼奥从某家商店a经过某家商店b,并且可能与a重合,那么他会感到非常震惊,这样现实生活中和幻象中访问过的商店列表就会重合。

建议beaver Neo这样的非零长度路径。或者您甚至可以计算此类路径的数量以 1000000007 (109 + 7) 为模?..

输入

第一行包含整数n和m——商店数量和街道数量,相应地,1 ≤ n ≤ 50,$$0 \leq m \leq \frac{n(n-1)}{2}$$。接下来的 m 行包含以下格式的街道描述:xi yi ki v1 v2 ... vk,其中 xi 和 yi (1 ≤ xi, yi ≤ n, xi ≠ yi) 是由街道连接的商店的索引,ki (0 ≤ ki ≤ n) 是从 xi 到 yi 途中的视觉数量; v1, v2, ..., vk (1 ≤ vi ≤ n) 描述愿景:Neo 看到的商店数量。请注意,愿景的顺序很重要。

保证所有街道上的愿景总数不超过105个。

- 要获得 50 分,您需要找到长度最多为 2·n 的任何(不一定简单)路径,满足上述属性(子问题 E1);
- 要再获得 50 个点,您需要计算从 1 到 2·n 的每个长度具有上述属性的路径数量(子问题 E2)。

输出

子问题E1。在第一行中打印一个整数 k (1 ≤ k ≤ 2·n) — Neo 路径上的商店数量。在下一行中打印 k 个整数——按照 Neo 经过的顺序排列的商店数量。如果图中没有这样的路径或者最短路径的长度包含超过 2·n 个商店,则在单行上打印 0。

子问题E2。打印 2·n 行。第 i 行必须包含一个整数 — 长度为 i 的所需路径数模 1000000007 (109 + 7)。

示例

输入 #1

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

输出 #1

4
6 1 2 3

输入 #2

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

输出 #2

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

注意

两个样本中的输入相同。第一个样本包含第一个子问题的答案,第二个样本包含第二个子问题的答案。