#P18816. [Croatian CPC2015] Lutrija
[Croatian CPC2015] Lutrija
[Croatian CPC2015] Lutrija
题目描述
Mirko 参加一种猜序列的彩票游戏。他在彩票上写下一个序列,开奖时从所有合法序列中抽出一个。如果两个序列完全相同,他便中奖。
给定整数 和一份允许的无序数对列表。一个序列合法,当且仅当满足以下全部条件:
- 序列非空,所有元素都是 内的整数。
- 序列中的所有元素互不相同。
- 序列中每两个相邻元素组成的无序数对,都在允许列表中。
称三个不同的合法序列组成一个“三元组”,当且仅当它们的第一个元素都是同一个数 ,最后一个元素都是同一个数 ,且除 外,没有其他数在其中两个或更多序列中出现。
保证给定列表中不存在能够组成上述“三元组”的三个合法序列。
Mirko 想购买所有合法序列对应的彩票。对于每个 ,请计算长度恰好为 的合法序列数量,答案对 取模。序列的顺序有意义,例如 和 是两个不同的序列。
输入格式
第一行包含两个整数 (,),其中 为允许列表中的数对数量。
接下来 行,每行包含两个整数 (),表示一个允许的无序数对。每个数对至多出现一次。
输出格式
输出一行 个整数,第 个数表示长度为 的合法序列数量对 取模的结果。
样例 1
输入
3 2
1 2
2 3
输出
3 4 2
样例 2
输入
3 3
1 3
2 3
1 2
输出
3 6 6
样例说明
样例 1 中,长度为 1 的序列为 ;长度为 2 的序列为 ;长度为 3 的序列为 。