#include<bits/stdc++.h>
using namespace std;
const int maxn=100100,mod=998244353,g=3;
inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;}
inline int ksm(int a,int b)
{
    int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) res=1ll*res*a%mod;
    return res;
}
int rev[maxn<<2];
inline void ntt(int *f,int n,int opt)
{
    for(int i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
    for(int p=2;p<=n;p<<=1)
    {
        int len=p>>1,tmp=ksm(g,(mod-1)/p);
        if(opt==-1) tmp=ksm(tmp,mod-2);
        for(int k=0;k<n;k+=p)
        {
            int buf=1;
            for(int l=k;l<k+len;l++)
            {
                int tt=1ll*f[l+len]*buf%mod;
                f[l+len]=f[l]-tt+mod;if(f[l+len]>=mod) f[l+len]-=mod;
                f[l]=f[l]+tt;if(f[l]>=mod) f[l]-=mod;
                buf=1ll*buf*tmp%mod;
            }
        }
    }
    if(opt==-1) for(int i=0,t=ksm(n,mod-2);i<n;i++) f[i]=1ll*f[i]*t%mod;
}
int ntta[maxn<<2],nttb[maxn<<2];
inline vector<int> Mul(const vector<int> &a,const vector<int> &b)
{
    if(a.size()<=16||b.size()<=16)
    {
        vector<int> ans;ans.resize(a.size()+b.size()-1);
        for(int i=0;i<(int)a.size();i++) for(int j=0;j<(int)b.size();j++) Add(ans[i+j],1ll*a[i]*b[j]%mod);
        return ans;
    }
    int L=1;for(;L<=(int)a.size()+(int)b.size();L<<=1);
    for(int i=0;i<L;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(L>>1):0);
    for(int i=0;i<(int)a.size();i++) ntta[i]=a[i];
    for(int i=0;i<(int)b.size();i++) nttb[i]=b[i];
    for(int i=a.size();i<L;i++) ntta[i]=0;
    for(int i=b.size();i<L;i++) nttb[i]=0;
    ntt(ntta,L,1);ntt(nttb,L,1);
    for(int i=0;i<L;i++) ntta[i]=1ll*ntta[i]*nttb[i]%mod;
    ntt(ntta,L,-1);vector<int> ans;
    for(int i=0;i<(int)a.size()+(int)b.size()-1;i++) ans.push_back(ntta[i]);
    return ans;
}
int fac[maxn],invfac[maxn],v[maxn],cal[maxn];
inline int C(int n,int m){return (n<0||n<m)?0:1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;}
int Fa[maxn],n,m;
inline int find(int x){return x==Fa[x]?x:Fa[x]=find(Fa[x]);}
int head[maxn],nxt[maxn<<1],ver[maxn<<1],tot;
inline void addedge(int a,int b)
{
    nxt[++tot]=head[a];ver[tot]=b;head[a]=tot;
    nxt[++tot]=head[b];ver[tot]=a;head[b]=tot;
}
int ra[maxn],rb[maxn],rtot;
bool vis[maxn];
int fa[maxn],dep[maxn];
inline void dfs(int x,int fat)
{
    fa[x]=fat;dep[x]=dep[fat]+1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];if(y==fat) continue;
        dfs(y,x);
    }
}
inline int Bao(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    int ans=1;
    while(dep[x]>dep[y])
    {
        if(vis[x]) return -1;
        vis[x]=1;x=fa[x];ans++;
    }
    while(x!=y)
    {
        if(vis[x]||vis[y]) return -1;
        vis[x]=vis[y]=1;x=fa[x];y=fa[y];
        ans+=2;
    }
    return ans;
}
vector<int> poly[maxn];int ptot;
inline void myhmd(int l,int r)
{
    if(l==r) return;int mid=(l+r)>>1;
    myhmd(l,mid);myhmd(mid+1,r);
    poly[l]=Mul(poly[l],poly[mid+1]);
}
inline void solve()
{
    scanf("%d%d",&n,&m);
    tot=0;rtot=0;
    for(int i=1;i<=n;i++) Fa[i]=i,head[i]=0,vis[i]=0;
    for(int i=1;i<=m;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        if(find(a)!=find(b)) Fa[find(a)]=find(b),addedge(a,b);
        else rtot++,ra[rtot]=a,rb[rtot]=b;
    }
    dfs(1,0);
    ptot=0;
    for(int i=1;i<=rtot;i++)
    {
        int ttt=Bao(ra[i],rb[i]);if(ttt==-1) return (void)puts("0");ptot++;poly[ptot].clear();
        for(int j=0;j<=ttt;j++) if(j&1) poly[ptot].push_back(C(ttt,j));else poly[ptot].push_back(0);
    }
    for(int i=2;i<=n;i++) if(!vis[i])
    {
        ptot++;
        poly[ptot].clear();
        poly[ptot].push_back(1);
        poly[ptot].push_back(1);
    }
    myhmd(1,ptot);
    int ans=1ll*poly[1][(m+1)>>1]*fac[(m+1)>>1]%mod*fac[m>>1]%mod;
    cout<<ans<<endl;
}
int main()
{
    fac[0]=1;for(int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
    invfac[maxn-1]=ksm(fac[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
    int T;cin>>T;while(T--) solve();return 0;
}