思路是记录每条边

• 选 $u$，选 $v$
• 不选 $u$，不选 $v$
• 选 $u$，不选 $v$
• 不选 $u$，选 $v$

的方案数，依次记为 $w_{e,1/2/3/4}$；同时为了支持删一度点操作，需要维护每个点当前选/不选的共线 $f_u,g_u$。

更新串联边是枚举中间点的选/不选情况按意思转移。

更新并联重边是直接边的对应边权相乘。

删一度点是按意思把当前点的 $f,g$ 和这条边的 $w$ 转移到下一个点的 $f,g$ 上。

根据广义串并联图经典结论，最后只会剩下 $\le 20$ 个点和 $\le 30$ 条边。去 $2^n$ 暴力枚举选点情况，对应计算其方案数乘积累加到答案中。

WA 5pts 只对了 #13，选 $n=6,m=8$ 的小数据拍不太出来，求调。/kel

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map

using namespace std;

typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int mod = 998244353;

struct edge {
	int u, v;
	int w[5] = {};
	edge() = default;
	edge(int u, int v, int a, int b, int c, int d): u(u), v(v) { w[1] = a, w[2] = b, w[3] = c, w[4] = d; }
	int& operator[] (int x) { return w[x]; }
};

int n, m, ans;
umap<int, edge> e[maxn]; 
edge ed[maxn];
int tot;
int deg[maxn];
int f[maxn], g[maxn];
int del[maxn];
int que[maxn], hd = 1, tl;
int id[maxn], cnt;
int pos[maxn];

void add_edge(int u, int v, int a, int b, int c, int d) {
	if (e[u].count(v)) {
		(e[u][v][1] *= a) %= mod;
		(e[u][v][2] *= b) %= mod;
		(e[u][v][3] *= c) %= mod;
		(e[u][v][4] *= d) %= mod;
	} else {
		edge cur = edge(u, v, a, b, c, d);
		e[u][v] = cur;
		deg[u]++;
	}
}

void del_edge(int u, int v) {
	e[u].erase(v);
	deg[u]--;
}

void debug() {
	for (int u = 1; u <= n; u++) {
		for (pair<int, edge> i : e[u]) {
			cout << u << " " << i.second.v << " " << i.second[1] << i.second[2] << i.second[3] << i.second[4] << endl;
		}
	}
}

signed main() {
//	freopen("P4426.in", "r", stdin);
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		add_edge(u, v, 0, 1, 1, 1);
		add_edge(v, u, 0, 1, 1, 1);
	}
	for (int i = 1; i <= n; i++) f[i] = g[i] = 1;
	for (int i = 1; i <= n; i++) if (deg[i] <= 2) que[++tl] = i;
	while (hd <= tl) {
		int u = que[hd++]; 
		if (!deg[u]) continue;
		if (deg[u] == 1) {
			edge i = e[u].begin()->second;
			int v = i.v;
//			cout << u << "->" << v << endl;
			(f[v] *= (f[u] * i[1] % mod + g[u] * i[4] % mod) % mod) %= mod;
			(g[v] *= (f[u] * i[3] % mod + g[u] * i[2] % mod) % mod) %= mod;
			del[u] = true;
			del_edge(u, v), del_edge(v, u);
			if (deg[v] <= 2) que[++tl] = v;
		} else {
			edge i = e[u].begin()->second;
			edge j = next(e[u].begin())->second; 
			int v1 = i.v, v2 = j.v;
//			cout << v1 << "-" << u << "-" << v2 << endl;
			swap(i[3], i[4]);
			edge cur = edge(v1, v2, 
				(i[1] * j[1] % mod * f[u] % mod + i[3] * j[4] % mod * g[u] % mod) % mod,
				(i[3] * j[4] % mod * f[u] % mod + i[2] * j[2] % mod * g[u] % mod) % mod,
				(i[1] * j[3] % mod * f[u] % mod + i[3] * j[2] % mod * g[u] % mod) % mod,
				(i[4] * j[1] % mod * f[u] % mod + i[2] * j[4] % mod * g[u] % mod) % mod
			);
			del[u] = true;
			del_edge(u, v1), del_edge(v1, u);
			del_edge(u, v2), del_edge(v2, u);
			add_edge(cur.u, cur.v, cur[1], cur[2], cur[3], cur[4]);
			add_edge(cur.v, cur.u, cur[1], cur[2], cur[4], cur[3]);
			if (deg[v1] <= 2) que[++tl] = v1;
			if (deg[v2] <= 2) que[++tl] = v2;
		}
//		debug();
	}
	for (int i = 1; i <= n; i++) {
		if (!del[i]) {
			id[++cnt] = i;
			pos[i] = cnt;
		}
	}
	for (int u = 1; u <= n; u++) {
		for (pair<int, edge> i : e[u]) if (u < i.second.v) ed[++tot] = i.second;
	}
	for (int S = 0; S < (1ll << cnt); S++) {
		int mul = 1;
		for (int i = 1; i <= cnt; i++) {
			if (S >> i - 1 & 1) (mul *= f[id[i]]) %= mod;
			else (mul *= g[id[i]]) %= mod;
		}
		for (int i = 1; i <= tot; i++) {
			int u = pos[ed[i].u], v = pos[ed[i].v];
			int p = S >> u - 1 & 1, q = S >> v - 1 & 1;
			if (p && q) (mul *= ed[i][1]) %= mod;
			else if (!p && !q) (mul *= ed[i][2]) %= mod;
			else if (p && !q) (mul *= ed[i][3]) %= mod;
			else (mul *= ed[i][4]) %= mod;
		}
		(ans += mul) %= mod;
	}
	cout << ans << endl;
	return 0;
}