QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5089. 环覆盖

统计

形式化题意:给定一张 $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。