形式化题意:给定一张 $n$ 个点,$m$ 条边的简单无向图,对每个 $i\in [0,m]$,计算它只保留 $i$ 条边,使得剩下的图是一个可环覆盖图的方案数。可环覆盖的定义是,可以将边集划分成若干个子集,使得每个子集都形成一个环。
答案对 $10^9+7$ 取模。
输入格式
第一行两个整数 $n,m$。
接下来 $m$ 行,每行两个数 $u,v$,代表一条边。
输出格式
一行 $m+1$ 个整数,第 $k$ 个表示题面中 $i=k-1$ 时的答案。
样例输入1
3 3 1 2 1 3 2 3
样例输出1
1 0 0 1
样例1解释
只有保留 0 条边和保留 3 条边的两个方案是合法的。
样例输入2
6 10 1 2 1 3 1 4 1 5 1 6 2 4 3 4 3 5 4 5 4 6
样例输出2
1 0 0 6 8 4 4 6 3 0 0
数据范围
对于所有数据,$1\le n\le 25,0\le m\le \dfrac{n(n-1)}{2}$。
Subtask 1(5pts):$n,m\le 20$。
Subtask 2(15pts):$n\le 20,m\le 40$。依赖 Sub 1。
Subtask 3(15pts):$n=25,m=45$,图连通。
Subtask 4(30pts):$n\le 20$。依赖 Sub 2。
Subtask 5(35pts):无特殊限制。依赖 Sub 4。