正题
想出来也写不出来。
其实题解说上去还挺简单的，看上去写也是十分方便的，可是万万没想到出题人卡空间，对于一条树边，我原先的方案就是构造一个新的多项式"1,1"，塞进里面，结果空间爆炸，换成组合数方法来乘起来，所用空间就还不到18MB。
题解大概就是考虑这样的一个图一定是一个仙人掌，至于为什么，可以考虑一条边同时被两个环覆盖的情况，然后剩下的就很简单了，很容易就可以想到分治NTT，启发式合并还是不启发式合并完全看你心情，理论时间复杂度没有什么差别，都是两个log。
然后做一个树上差分就可以判仙人掌和判一条边是否为树边。
最后乘上往黑白格子填数的方案数就可以了。
#include<bits/stdc++.h>
using namespace std;const int N=100010;
int T,n,m;
struct edge{int y,next;
}s[N<<1];
int first[N],len,dep[N];
int t[N],op=0;
bool we=true;
int where[N<<2],l=0,limit;
int fac[N],inv[N];
const int mod=998244353;
vector<int> V;
vector<int> a[N];void ins(int x,int y){s[++len]=(edge){y,first[x]};first[x]=len;
}long long ksm(long long x,long long t){long long tot=1;while(t){if(t&1) (tot*=x)%=mod;(x*=x)%=mod;t/=2; } return tot;
}void dfs(int x,int ex){for(int i=first[x];i!=0;i=s[i].next) if(i!=ex && i!=(ex^1)){if(dep[s[i].y] && dep[s[i].y]<dep[x]) V.push_back(dep[x]-dep[s[i].y]+1),t[x]++,t[s[i].y]--;else if(!dep[s[i].y]) dep[s[i].y]=dep[x]+1,dfs(s[i].y,i),t[x]+=t[s[i].y];}if(t[x]>=2) we=false;if(t[x]==0 && x!=1) op++;
}int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}void dft(vector<int>&now,int idft){for(int i=0;i<limit;i++) if(i<where[i]) swap(now[i],now[where[i]]);int a,b,w,wn;for(int l=2;l<=limit;l<<=1){wn=ksm(3,1ll*(mod-1)/l*idft%(mod-1));for(int i=0;i<limit;i+=l){w=1;for(int x=i,y=i+l/2;y<i+l;x++,y++,w=1ll*w*wn%mod){a=now[x],b=1ll*now[y]*w%mod;now[x]=a+b,now[x]>=mod?now[x]-=mod:0;now[y]=a+mod-b,now[y]>=mod?now[y]-=mod:0;}}}
}void get_sum(int x,int y){int tot=a[x].size()-1+a[y].size();l=0;limit=1;while(limit<=a[x].size()-1+a[y].size()-1) limit*=2,l++;for(int i=0;i<limit;i++) where[i]=((where[i>>1]>>1)|((i&1)<<(l-1)));for(int i=a[x].size();i<limit;i++) a[x].push_back(0);for(int i=a[y].size();i<limit;i++) a[y].push_back(0);dft(a[x],1);dft(a[y],1);for(int i=0;i<limit;i++) a[x][i]=1ll*a[x][i]*a[y][i]%mod;dft(a[x],mod-2);long long tmp=ksm(limit,mod-2);for(int i=0;i<limit;i++) a[x][i]=1ll*a[x][i]*tmp%mod;a[x].resize(tot);a[y].resize(0);
}void solve(int l,int r){if(l==r) return ;int mid=(l+r)/2;solve(l,mid);solve(mid+1,r);get_sum(l,mid+1);
}int main(){scanf("%d",&T);fac[0]=1;for(int i=1;i<=100000;i++) fac[i]=1ll*fac[i-1]*i%mod;inv[100000]=ksm(fac[100000],mod-2);for(int i=99999;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;while(T--){scanf("%d %d",&n,&m);op=0;memset(first,0,sizeof(first));len=1;memset(dep,0,sizeof(dep));V.resize(0);memset(t,0,sizeof(t));we=true;int x,y;for(int i=1;i<=m;i++) scanf("%d %d",&x,&y),ins(x,y),ins(y,x);dep[1]=1;dfs(1,0);if(we==false){printf("0\n");continue;}for(int i=0;i<V.size();i++){a[i].resize(V[i]+1);for(int j=1;j<=V[i];j+=2) a[i][j]=C(V[i],j);for(int j=0;j<=V[i];j+=2) a[i][j]=0;}solve(0,V.size()-1);long long ans=0;for(int i=(m+1)/2-op;i<=(m+1)/2;i++) ans+=1ll*a[0][i]*C(op,(m+1)/2-i)%mod;ans%=mod;printf("%lld\n",1ll*ans*fac[(m+1)/2]%mod*fac[m/2]%mod);a[0].resize(0);}
}