← 返回题目列表

Codeforces · 512/D

D. 狐狸和旅行

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

Fox Ciel 将于今年夏天前往新福克斯兰。

新福克斯兰有 n 个景点,由 m 条无向道路连接。如果两个景点通过道路相连,则称为相邻。 Fox Ciel 有 k 天时间游览这座城市,每天她只会游览一个景点。

新福克斯兰有一条重要规则:如果某个景点有多个您尚未参观过的相邻景点,您就不能参观该景点。

一开始Fox Ciel还没有参观过任何景点。在旅行期间,她可能会在景点之间任意移动。参观完景点 a 后,她可以前往尚未参观过的任何满足上述条件的景点 b,即使从 a 无法通过公路到达(夏尔在景点之间使用船只,因此这是可能的)。

她想知道她可以制定多少种不同的旅行计划。对于从 0 到 n 的每个 k,计算该数字以 109 + 9 为模,因为她尚未决定要访问新福克斯兰多少天。

输入

第一行包含两个整数:n, m (1 ≤ n ≤ 100, $$0 \leq m \leq \frac{n(n-1)}{2}$$),景点数量和无向道路数量。

接下来的 m 行每行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n 且 ai ≠ bi),描述一条道路。连接每对景点的道路不超过一条。

输出

输出 n + 1 整数:对于从 0 到 n 的所有 k,可能的旅行计划的数量以 109 + 9 为模。

示例

输入 #1

3 2
1 2
2 3

输出 #1

1
2
4
4

输入 #2

4 4
1 2
2 3
3 4
4 1

输出 #2

1
0
0
0
0

输入 #3

12 11
2 3
4 7
4 5
5 6
4 6
6 12
5 12
5 8
8 9
10 8
11 9

输出 #3

1
6
31
135
483
1380
3060
5040
5040
0
0
0
0

输入#4

13 0

输出#4

1
13
156
1716
17160
154440
1235520
8648640
51891840
259459200
37836791
113510373
227020746
227020746

注意

在 k = 3 的第一个样本测试中,有 4 个旅行计划:{1, 2, 3}、{1, 3, 2}、{3, 1, 2}、{3, 2, 1}。

在第二个样本测试中,Ciel 在第一天无法访问任何景点,因此对于 k > 0,答案为 0。

在第三个示例测试中 Foxlands 看起来像这样: