#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> using namespace std; #define rep(i,l,r) for(register int i=(l);i<=(r);++i) #define repdo(i,l,r) for(register int i=(l);i>=(r);--i) #define il inline typedef double db; typedef long long ll; //--------------------------------------- const int nsz=5e5+50,msz=1e6+50; const ll nmod=998244353; int t,n,m; struct te{int t,pr,del;}edge[msz*2]; int hd[nsz],pe=1; #define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t) void adde(int f,int t){edge[++pe]=(te){t,hd[f],0};hd[f]=pe;} void adddb(int f,int t){adde(f,t);adde(t,f);} ll g[nsz]; void init(int bnd){ g[0]=1,g[1]=1; rep(i,2,bnd)g[i]=(g[i-1]+g[i-2]*(i-1))%nmod; } int vis[nsz],stkp[nsz],stk[nsz],top=0; bool solcactus(int p,int e0){ stk[++top]=e0^1,stkp[p]=top,vis[p]=1; forg(p,i,v){ if(i==e0)continue; if(vis[v]){//cir if(stkp[v]>stkp[p])continue; edge[i].del=edge[i^1].del=1; rep(j,stkp[v]+1,stkp[p]){ if(edge[stk[j]].del)return 0; edge[stk[j]].del=edge[stk[j]^1].del=1; } continue; } if(solcactus(v,i^1)==0)return 0; } --top; return 1; } ll dp[nsz]; void dfs(int p,int fa){ dp[p]=1,vis[p]=1; int cnt=0; forg(p,i,v){ if(v==fa||edge[i].del)continue; dfs(v,p); dp[p]=dp[p]*dp[v]%nmod; ++cnt; } dp[p]=dp[p]*(fa==0?g[cnt]:g[cnt+1])%nmod; } ll sol(){ memset(vis,0,(n+10)*sizeof(int)); top=0; if(solcactus(1,0)==0)return 0; memset(vis,0,(n+10)*sizeof(int)); ll res=1; rep(i,1,n){ if(vis[i]==0)dfs(i,0),res=res*dp[i]%nmod; } return res; } void init1(int n){ memset(hd,0,(n+10)*sizeof(int)); pe=1; } int main(){ ios::sync_with_stdio(0),cin.tie(0); init(5e5+50); cin>>t; rep(cs,1,t){ cin>>n>>m; init1(n); int a,b; rep(i,1,m)cin>>a>>b,adddb(a,b); cout<<sol()<<'\n'; } return 0; }