评测记录

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int N = 5e5 + 10;
const int M = 2e6 + 10;
const int Mod = 998244353;

int n,m;
struct Edge {
    int y,nxt;
} edge[M];
int li[N],tot=1;

void insert(int x,int y) {
    edge[++tot]= {y,li[x]};
    li[x]=tot;
}

bool del[M],flag;
bool vis[N];

void dfs(int x,int pre) {
	vis[x]=true;
    if(flag) return;
    for(int i=li[x]; i; i=edge[i].nxt) {
        if(flag) return;
        int y=edge[i].y;
        if(y==pre) continue;
        if(!vis[y]) dfs(y,x);
        else if(!del[i]&&!del[i^1]) {
            del[i]=del[i^1]=true;
        } else {
            printf("0\n");
            flag=true;
            return;
        }
    }
}

int h[N];
int g[N];
int vis2[N];

void DP(int x,int pre,int rt){
	vis2[x]=rt;
	int cnt=1;
	g[x]=1;
    for(int i=li[x]; i; i=edge[i].nxt) {
    	if(del[i]) continue;
        int y=edge[i].y;
		if(y==pre) continue;
		cnt++;
		DP(y,x,rt);
		g[x]=(g[x]*1ll*g[y])%Mod;
	}
	g[x]=(g[x]*1ll*h[cnt])%Mod;
}

int getans(int x){
	int cnt=0;
	int res=1;
    for(int i=li[x]; i; i=edge[i].nxt) {
    	if(del[i]) continue;
        int y=edge[i].y;
		cnt++;
		res=(res*1ll*g[y])%Mod;
	}
	res=(res*1ll*h[cnt])%Mod;
	return res;
}

void clear(){
	flag=false;
	for(int i=1;i<=n;i++){
		li[i]=g[i]=vis2[i]=0;
		vis[i]=false;
	}
	for(int i=2;i<=tot;i++){
		edge[i]={};
		del[i]=false;
	}
	tot=1;
}

int main() {
	h[0]=h[1]=1;
	for(int i=2;i<=N-10;i++){
		h[i]=(h[i-1]*1ll+1ll*(i-1)*h[i-2])%Mod;
	}
    int t;
    cin>>t;
    while(t--) {
    	clear();
        cin>>n>>m;
        for(int i=1; i<=m; i++) {
            int x,y;
            cin>>x>>y;
            insert(x,y);
            insert(y,x);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++) if(!vis2[i]) DP(i,0,i);
        int ans=1;
        for(int i=1;i<=n;i++) if(vis2[i]==i) ans=(ans*1ll*getans(i))%Mod;
        cout<<ans<<'\n';
    }
    return 0;
}