#P18816. [Croatian CPC2015] Lutrija

[Croatian CPC2015] Lutrija

[Croatian CPC2015] Lutrija

题目描述

Mirko 参加一种猜序列的彩票游戏。他在彩票上写下一个序列,开奖时从所有合法序列中抽出一个。如果两个序列完全相同,他便中奖。

给定整数 NN 和一份允许的无序数对列表。一个序列合法,当且仅当满足以下全部条件:

  • 序列非空,所有元素都是 [1,N][1,N] 内的整数。
  • 序列中的所有元素互不相同。
  • 序列中每两个相邻元素组成的无序数对,都在允许列表中。

称三个不同的合法序列组成一个“三元组”,当且仅当它们的第一个元素都是同一个数 aa,最后一个元素都是同一个数 bb,且除 a,ba,b 外,没有其他数在其中两个或更多序列中出现。

保证给定列表中不存在能够组成上述“三元组”的三个合法序列。

Mirko 想购买所有合法序列对应的彩票。对于每个 L=1,2,…,NL=1,2,\ldots,N,请计算长度恰好为 LL 的合法序列数量,答案对 10000000071000000007 取模。序列的顺序有意义,例如 (1,2)(1,2) 和 (2,1)(2,1) 是两个不同的序列。

输入格式

第一行包含两个整数 N,PN,P(1≤N≤40001\le N\le4000,0≤P≤1000000\le P\le100000),其中 PP 为允许列表中的数对数量。

接下来 PP 行,每行包含两个整数 x,yx,y(1≤x<y≤N1\le x<y\le N),表示一个允许的无序数对。每个数对至多出现一次。

输出格式

输出一行 NN 个整数,第 LL 个数表示长度为 LL 的合法序列数量对 10000000071000000007 取模的结果。

样例 1

输入

3 2

1 2

2 3

输出

3 4 2

样例 2

输入

3 3

1 3

2 3

1 2

输出

3 6 6

样例说明

样例 1 中,长度为 1 的序列为 (1),(2),(3)(1),(2),(3);长度为 2 的序列为 (1,2),(2,3),(2,1),(3,2)(1,2),(2,3),(2,1),(3,2);长度为 3 的序列为 (1,2,3),(3,2,1)(1,2,3),(3,2,1)。