这题给我感觉才是day1 最简单的题，一点都不毒瘤。
先考虑保留一个生成树，对于非树边，我们可以容斥，选其中(i)条边，使得这(i)条边一定不合法，也就是这(i)条边对应的点一定选，容斥系数是((-1)^i)
暴力就容斥完之后再做个树形dp，时间复杂度(O(2^{(m-n+1)}*n))，可以10min获得85的高分。
因为每次相当于开启一个点或者关闭一个点，一种方法是直接套上ddp，时间复杂度：(O((n+2^{(n-m+1)}*(n-m+1))*log~n))，比较难写（考场上肯定就不要了）
另一种方法是建出非树边的虚树，然后只在虚树上dp。
因为虚树上两个点之间会有其他的子树，所以要预处理系数贡献。
对于每个不是虚树上的点(x)，设(to[x])为它子树到它最近的一个虚树上的点（该点为1），那么(x)的dp值一定是由(to[x])的dp值乘上系数得来，直接struct封装后去维护这个系数。
对虚树上点，只保留子树内有虚树上点的儿子，其它的都是常数贡献，
利用这些求出的系数每次再dp就好了。
时间复杂度：(O(n+2^k*k))
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 998244353;
const int N = 1e5 + 5;
int f[N];
int n, m, x, y;
int b[N][2], b0;
#define V vector<int>
#define pb push_back
#define si size()
V e[N];
int F(int x) { return f[x] == x ? x : (f[x] = F(f[x]));}
int p[N], q[N], p0;
int fa[N], siz[N], son[N], dep[N], top[N];
void dg(int x) {
p[x] = ++ p0;
dep[x] = dep[fa[x]] + 1;
siz[x] = 1;
ff(_y, 0, e[x].si) {
int y = e[x][_y]; if(y == fa[x]) continue;
fa[y] = x;
dg(y);
siz[x] += siz[y];
if(siz[y] > siz[son[x]]) son[x] = y;
}
q[x] = p0;
}
void dfs(int x) {
if(son[x]) top[son[x]] = top[x], dfs(son[x]);
ff(_y, 0, e[x].si) {
int y = e[x][_y]; if(y == son[x] || y == fa[x]) continue;
top[y] = y; dfs(y);
}
}
int lca(int x, int y) {
while(top[x] != top[y]) if(dep[top[x]] >= dep[top[y]])
x = fa[top[x]]; else y = fa[top[y]];
return dep[x] < dep[y] ? x : y;
}
int z[N], z0, bz[N];
int cmp(int x, int y) { return p[x] < p[y];}
struct P {
ll x[3];
P(ll x0 = 0, ll x1 = 0, ll x2 = 0) {
x[0] = x0, x[1] = x1, x[2] = x2;
}
};
P operator * (P a, P b) {
P c = P();
c.x[0] = a.x[0] * b.x[0] % mo;
c.x[1] = (a.x[0] * b.x[1] + a.x[1] * b.x[0]) % mo;
c.x[2] = (a.x[0] * b.x[2] + a.x[2] * b.x[0]) % mo;
return c;
}
P operator + (P a, P b) {
fo(i, 0, 2) a.x[i] = (a.x[i] + b.x[i]) % mo;
return a;
}
P g[N][2]; ll h[N][2]; int to[N];
V e2[N];
void du(int x) {
g[x][0] = g[x][1] = P(1, 0, 0);
if(!bz[x]) {
ff(_y, 0, e[x].si) {
int y = e[x][_y]; if(y == fa[x]) continue;
du(y);
g[x][0] = g[x][0] * (g[y][0] + g[y][1]);
g[x][1] = g[x][1] * g[y][0];
if(to[y]) to[x] = to[y];
}
} else {
ff(_y, 0, e[x].si) {
int y = e[x][_y]; if(y == fa[x]) continue;
du(y);
if(!to[y]) {
g[x][0] = g[x][0] * (g[y][0] + g[y][1]);
g[x][1] = g[x][1] * g[y][0];
} else {
e2[x].pb(y);
}
}
to[x] = x;
h[x][0] = g[x][0].x[0]; h[x][1] = g[x][1].x[0];
g[x][0] = P(0, 1, 0);
g[x][1] = P(0, 0, 1);
}
}
void build() {
dg(1);
top[1] = 1; dfs(1);
fo(i, 1, b0) {
z[++ z0] = b[i][0];
z[++ z0] = b[i][1];
}
sort(z + 1, z + z0 + 1, cmp);
z[++ z0] = 1;
fo(i, 2, z0) z[++ z0] = lca(z[i], z[i - 1]);
sort(z + 1, z + z0 + 1, cmp);
z0 = unique(z + 1, z + z0 + 1) - (z + 1);
fo(i, 1, z0) bz[z[i]] = 1;
du(1);
}
ll dp[N][2];
ll ans;
int cho[N];
void zy(int x) {
dp[x][0] = h[x][0], dp[x][1] = h[x][1];
ff(_y, 0, e2[x].si) {
int y = e2[x][_y];
ll v0 = dp[to[y]][0], v1 = dp[to[y]][1];
ll w0 = (g[y][0].x[0] + g[y][0].x[1] * v0 + g[y][0].x[2] * v1) % mo;
ll w1 = (g[y][1].x[0] + g[y][1].x[1] * v0 + g[y][1].x[2] * v1) % mo;
dp[x][0] = dp[x][0] * (w0 + w1) % mo;
dp[x][1] = dp[x][1] * w0 % mo;
}
if(cho[x]) dp[x][0] = 0;
}
void work(int xs) {
fd(i, z0, 1) {
int x = z[i];
zy(x);
}
ans = (ans + (dp[1][0] + dp[1][1]) * xs) % mo;
}
void dg(int x, int xs) {
if(x > b0) {
work(xs);
return;
}
cho[b[x][0]] ++; cho[b[x][1]] ++;
dg(x + 1, -xs);
cho[b[x][0]] --; cho[b[x][1]] --;
dg(x + 1, xs);
}
int main() {
scanf("%d %d", &n, &m);
fo(i, 1, n) f[i] = i;
fo(i, 1, m) {
scanf("%d %d", &x, &y);
if(F(x) == F(y)) {
b[++ b0][0] = x, b[b0][1] = y;
} else {
f[f[x]] = f[y];
e[x].pb(y); e[y].pb(x);
}
}
build();
dg(1, 1);
ans = (ans % mo + mo) % mo;
pp("%lld
", ans);
}