Solution

首先考虑在树上怎么做。

不难想到扫描每条非树边，覆盖两点间路径，则最终图是仙人掌等价于没有一条边被覆盖两次或以上。

于是原问题可以转化成该问题：选择若干条长度至少为 $2$ 的路径，使路径上的边覆盖次数加一，求最终每条边覆盖次数都是 $0$ 或 $1$ 的方案数。

【长度至少为 $2$】很烦人，我们考虑将最终没有被覆盖的边连上一条重边，这样就转化为了：选择若干条长度至少为 $1$ 的路径，使路径上的边覆盖次数加一，求最终每条边覆盖次数都是 $1$ 的方案数。

继续转化。我们考虑先将原树连满重边，每一次操作改为：选择两条有一个端点相同的路径，并将这两条路径合并。

发现此时一个节点的操作不会影响到另一个结点，于是我们把它弱化到节点上考虑，分别求出后再乘起来：选择若干组点对，满足点对中的点均与当前节点相邻，且任意一个节点至多在一个点对内出现的方案数。

这个问题仅与度数有关，已经足够弱了。我们考虑 DP：

设 $f_n$ 为结点度数为 $n$ 时，上述问题的答案。分两种情况考虑：

• 第 $n$ 个点不与任何点配对。 方案数为 $f_{n-1}$。
• 第 $n$ 个点与其中一个点配对。 在剩下 $n-1$ 个点中任选一个配对，其他的该怎么选怎么选，方案数为 $(n-1)f_{n-2}$。

于是转移方程即为 $f_{n}=f_{n-1}+(n-1)f_{n-2}$。初值是 $f_{0}=f_{1}=1$。

我们解决了树的情况，考虑拓展到仙人掌（我们已经判掉了不是仙人掌的情况）。

容易发现，在环上的所有边都是不可被覆盖的。于是我们将环删掉，剩下一个森林，则森林的每棵树都是互相独立的，可以按照上述方法求出，分别求出后乘起来即可。

时间 / 空间复杂度均为 $O(n+m)$。

代码并不难写，就不放了。

首先给的图也必须是仙人掌，否则立刻矛盾，答案即为 $0$。

然后我们把所有环拆开，变成若干颗树的问题。

接下来考虑树怎么解决。

容易发现，把每条附加边对应于树上一条至少有 $2$ 条边的路径，则合法等价于路径的边集两两不交。

我们钦定不被选择的边就是长度为 $1$，那就是求有多少的路径覆盖数。

我们将覆盖的路径视作「在相邻边处选择连接」，对每个点直接把路径暴力枚举连接的方案，显然只和度数有关，乘起来即可。

关于度数的方案数，直接 dp 即可统计。

参考代码。