题解

（请在此补充题目的中文题解与思路描述。）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<bitset>
#include<queue>
#include<ctime>
#include<cmath>
#include<set>
#include<map>
#define infile(filename) freopen(filename".in","r",stdin)
#define outfile(filename) freopen(filename".out","w",stdout)
#define usefile(filename) infile(filename),outfile(filename)
using namespace std; typedef long long ll; typedef unsigned long long ull; typedef __int128 I;
namespace IO {
	const int BUF=1<<20; static char ch[BUF]={},out[BUF]={},*l=ch,*r=ch,*o=out;
#define FASTIO
#ifdef FASTIO
	inline char gc() { return (l==r&&(r=(l=ch)+fread(ch,1,BUF,stdin),l==r))?EOF:*l++; }
#else
	inline char gc() { return getchar(); }
#endif
	inline void flush() { fwrite(out,1,o-out,stdout),o=out; }
	inline void putc(char ch) { if(o==out+BUF) flush(); *o++=ch; }
	struct flusher{~flusher(){flush();}}_;
}; using IO::gc; using IO::putc;
template <typename T> void read(T &a) { static char fushu,ch; a=fushu=0; do ch=gc(); while(ch!='-'&&(ch<48||ch>57)); if(ch=='-') ch=gc(),fushu=1; do a=(a<<1)+(a<<3)+(ch^48),ch=gc(); while(ch>47&&ch<58); if(fushu) a=-a; }
template <typename T,typename ...Args> void read(T &a,Args &...args) { read(a),read(args...); }
template <typename T> void write(T a) { static char que[114]={},*p=que; if(!a) putc(48); if(a<0) putc('-'),a=-a; while(a) *p++=(a%10)^48,a/=10; while(p!=que) putc(*--p); putc(32); }
template <typename T,typename ...Args> void write(T a,Args ...args) { write(a),write(args...); }
template <typename T> void ckmax(T &a,T b) { if(a<b) a=b; }
template <typename T> void ckmin(T &a,T b) { if(b<a) a=b; }
const int N=100099,moder=998244353;
int add(int x,int y) { return x+y>=moder?x+y-moder:x+y; }
int Add(int &x,int y) { return x=x+y>=moder?x+y-moder:x+y; }
int n,m,f[N][2][2]={},tmp[2][2]={},tmp2[2][2]={},w[N]={}; map<int,int> mp[N]; bool ind[N]={};
int yu[N]={},tyu,id[N]={};
struct edge { int x,y; } e[N];
int main()
{
	// usefile("reject");
	int i,j,k,x,y,z,l,r,e1,e2,e3,S,ans; bool rv1,rv2,rv3;
	read(n,m);
	for(i=1;i<=m;++i)
		read(e[i].x,e[i].y),
		mp[e[i].x][e[i].y]=i,
		mp[e[i].y][e[i].x]=i,
		f[i][0][0]=f[i][1][0]=f[i][0][1]=1;
	for(i=1,l=1,r=0;i<=n;++i)
		if(mp[i].size()<=2)
			ind[i]=true,w[++r]=i;
	while(l<=r) { x=w[l++];
		if(mp[x].size()==0) ;
		else if(mp[x].size()==1) {
			y=mp[x].begin()->first,e1=mp[x].begin()->second;
			if(mp[y].size()==1) {
				printf("%d\n",add(add(f[e1][0][0],f[e1][0][1]),add(f[e1][1][0],f[e1][1][1])));
				return 0;
			}
			if(mp[y].begin()->first==x)
				z=mp[y].rbegin()->first,e2=mp[y].rbegin()->second;
			else z=mp[y].begin()->first,e2=mp[y].begin()->second;
			memset(tmp,0,sizeof(tmp));
			rv1=e[e1].x==x,rv2=e[e2].x==z;
			for(i=0;i<2;++i) for(j=0;j<2;++j) for(k=0;k<2;++k)
				Add(tmp[k][j],(ull)(rv1?f[e1][i][j]:f[e1][j][i])*(rv2?f[e2][k][j]:f[e2][j][k])%moder);
			if(rv2) { for(i=0;i<2;++i) for(j=0;j<2;++j) f[e2][i][j]=tmp[i][j]; }
			else { for(i=0;i<2;++i) for(j=0;j<2;++j) f[e2][j][i]=tmp[i][j]; }
			mp[y].erase(x),mp[x].erase(y);
			if(!ind[y]&&mp[y].size()<=2) ind[y]=true,w[++r]=y;
		} else {
			y=mp[x].begin()->first,e1=mp[x].begin()->second;
			z=mp[x].rbegin()->first,e2=mp[x].rbegin()->second;
			memset(tmp,0,sizeof(tmp));
			rv1=e[e1].x==x,rv2=e[e2].x==x;
			for(i=0;i<2;++i) for(j=0;j<2;++j) for(k=0;k<2;++k)
				Add(tmp[j][k],(ull)(rv1?f[e1][i][j]:f[e1][j][i])*(rv2?f[e2][i][k]:f[e2][k][i])%moder);
			if(mp[y].count(z)) {
				e3=mp[y][z],rv3=e[e3].x==y,memset(tmp2,0,sizeof(tmp2));
				for(i=0;i<2;++i) for(j=0;j<2;++j)
					Add(tmp2[i][j],(ull)tmp[i][j]*(rv3?f[e3][i][j]:f[e3][j][i])%moder);
				if(rv3) { for(i=0;i<2;++i) for(j=0;j<2;++j) f[e3][i][j]=tmp2[i][j]; }
				else { for(i=0;i<2;++i) for(j=0;j<2;++j) f[e3][j][i]=tmp2[i][j]; }
			} else {
				mp[y][z]=mp[z][y]=e1,e[e1]=(edge){y,z};
				for(i=0;i<2;++i) for(j=0;j<2;++j) f[e1][i][j]=tmp[i][j];
			}
			mp[y].erase(x),mp[x].erase(y);
			mp[z].erase(x),mp[x].erase(z);
			if(!ind[y]&&mp[y].size()<=2) ind[y]=true,w[++r]=y;
			if(!ind[z]&&mp[z].size()<=2) ind[z]=true,w[++r]=z;
		}
	}
	for(i=1;i<=n;++i) if(!ind[i]) yu[id[i]=tyu++]=i;
	for(S=ans=0;S<(1<<tyu);++S) {
		for(i=0,x=1;i<tyu;++i)
			for(auto j:mp[yu[i]])
				if(e[j.second].x==yu[i])
					x=(ull)x*f[j.second][S>>i&1][S>>id[j.first]&1]%moder;
		Add(ans,x);
	}
	printf("%d\n",ans);
	return 0;
}