写这篇博客的起因是校内模拟赛出重了。。然后 chenkuowen 用集合幂级数通过了，大为震撼。

首先对原图进行收缩，具体的，我们给每条边设置两个边权 $c, d$ 分别表示使这条边联通的方案数和使这条边断开的方案数，初始有边即为 $(1,1)$。

收缩含有三部分：缩一度点，缩二度点，叠合重边。

1. 缩一度点：删去这个点，并在答案上乘上 $c$。

2. 缩二度点：删去这个点，并合并两条边，具体的，$(c,d)=(c_ac_b,c_ad_b+d_ac_b)$。

3. 叠合重边：合并两条边，具体的，$(c,d)=(c_ac_b+c_ad_b+d_ac_b,d_ad_b)$。

做完以上操作后，每个点至少是三度点，并且 $m-n$ 不会增大。于是我们有 $m\geq \frac{3n}{2},m\leq n+k-1$，那么 $n\leq 2k-2$。

接下来考虑如何计算使这张图联通的方案数。

设 $f_S$ 表示点集 $S$ 的导出子图的联通生成子图个数，$g_S$ 表示点集 $S$ 的导出子图的生成子图个数。

那么

$$g_S=\sum_{\{P_k\}\in \text{part}(S)}\prod_{i=1}^k f_{P_i}\prod_{u\in P_i,v\in P_j,i\lt j} d_{u,v}$$

其中 $\{P_k\}\in \text{part}(S)$ 表示 $\{P_k\}$ 是 $S$ 的一个无序划分。

再设 $D_S=\prod_{u,v\in S} d_{u,v}$，那么有

$$\frac{g_S}{D_S}=\sum_{\{P_k\}\in \text{part}(S)}\prod_{i=1}^k \frac{f_{P_i}}{D_{P_i}}$$

注意如果有 $d_{u,v}=0$ 需要特殊处理（直接合并两个点）。

令 $G_S=\frac{g_S}{D_S},F_S=\frac{f_S}{D_S}$，上述式子实际上就是 $G=\sum_{i=0}\frac{F^i}{i!}=\exp(F)$。

所以 $F=\ln(G)$，注意到 $g_S=\prod_{u,v\in S} (c_{u,v}+d_{u,v})$，于是可以快速计算出 $F$。

时间复杂度 $\Theta(n+k^24^k)$。