题意简述

给定$n$点$m$边的简单无向连通图。

现在要在图上加若干边，要求加边后还是一个简单无向连通图，且每条边至多属于一个简单环。

求加边方案数对$998244353$取模的值。

$1 \le n \le 5 \times 10 ^ 5, 1 \le m \le 10 ^ 6$

算法讨论

考后再写一遍的时候发现写的好快啊QAQ

先判一下原图是不是仙人掌。具体可以先DFS一棵生成树，就有许多返祖边，树上差分一下就可以求出每个点连向父亲的边被覆盖了多少次，大于一次就无解。特殊地，等于一次的边就是环边。

首先发现加的边不可能经过某个环。也就是说，环把仙人掌分成若干棵树。树与树之间是相互独立的。所以我们可以对每棵树统计加边方案数再相乘。

问题就转化成在一棵树上加边变成仙人掌的方案数。这个问题还是有点难求。不妨考虑判定仙人掌的过程，每条边至多被覆盖一次。那么连一个环就相当于覆盖一条路径。于是问题等价于树上每条边至多被覆盖一次的路径覆盖方案数。我们发现有个至多的条件很讨厌，什么时候某条边没有被覆盖呢？就是这条边在最终方案中是一条树边。那我们可以把它强行考虑成一个两元环。就可以把问题等价成每条边恰好被覆盖一次的路径覆盖方案数了。

这个问题一看就是DP。设$f_i$为$i$子树的答案。首先$i$的所有儿子内部的覆盖方案是相互独立的，于是可以先把儿子的答案先相乘。接下来我们可以发现如果这个点不是根，至多有一个儿子的路径可以经过$i$继续向上延伸，我们就以这个标准分一下类。

如果没有这样的儿子，那么一定有一些儿子两两配对成一些路径，其余的儿子连到根到就终止了。设$i$个儿子时的方案数是$C_i$，考虑枚举配对的儿子对数$j$，有

$$C_i = \sum_{2j \le i} {{i \choose 2j} G_j}$$

$G_i$就是$2i$个点两两配对的方案数，推一推可以发现

$$G_i = \frac{1} {2 ^ i} i! {2i \choose i}$$

如果有这样的儿子，考虑枚举是哪一个，对系数的贡献是$i C_{i-1}$。

把系数计算出来乘上去就转移完了。整个过程特别小清新，给出题人点个赞！

时间复杂度$O(n)$。