//Δ_1008
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1<<17;
const int MO = 998244353;
int ad(int x,int y){
    x+=y;
    if(x>=MO)
        x-=MO;
    if(x<0)
        x+=MO;
    return x;
}
int mul(int x,int y){
    return (LL)x*y%MO;
}
int fpow(int x,int y=MO-2){
    if(!y)
        return 1;
    int z=fpow(x,y>>1);
    z=mul(z,z);
    if(y&1)
        return mul(z,x);
    return z;
}
void DFT(int C[],int n,int fl){
    int i,j,k,l;
    int u,v,w,cur;
    i=n>>1;
    for(j=1;j<n;j=j+1){
        if(i<j)
            swap(C[i],C[j]);
        for(k=n>>1;i&k;k>>=1)
            i^=k;
        i^=k;
    }
    for(l=2;l<=n;l<<=1){
        w=fpow(3,(MO-1)/l);
        if(fl==-1)
            w=fpow(w);
        for(i=0;i<n;i=i+l){
            cur=1;
            for(j=i;j<i+(l>>1);j=j+1){
                u=C[j],v=mul(C[j+(l>>1)],cur);
                C[j]=ad(u,v),C[j+(l>>1)]=ad(u,-v);
                cur=mul(cur,w);
            }
        }
    }
}
int fac[N],ifac[N];
int o,c[N],e[N];
int n,m,l,a[N],b[N],d[N],f[N][18];
vector<int> v[N];
void dfs1(int u,int fa){
    f[u][0]=fa;
    d[u]=d[fa]+1;
    int i=v[u].size(),x;
    while(i--){
        x=v[u][i];
        if(d[x])
            continue;
        dfs1(x,u);
    }
}
int lca(int x,int y){
    int j;
    if(d[x]<d[y])
        swap(x,y);
    for(j=17;d[x]>d[y];j=j-1)
        if(d[f[x][j]]>=d[y])
            x=f[x][j];
    if(x==y)
        return x;
    for(j=17;f[x][0]!=f[y][0];j=j-1)
        if(f[x][j]!=f[y][j])
            x=f[x][j],y=f[y][j];
    return f[x][0];
}
void go(int x,int y){
    if(x>y)
        return;
    if(f[x][0]==y||f[y][0]==x)
        return;
    int z=lca(x,y);
    a[x]++,a[y]++,a[z]-=2;
    b[1+d[x]+d[y]-d[z]*2]++;
}
void dfs2(int u){
    int i=v[u].size(),x;
    while(i--){
        x=v[u][i];
        if(f[x][0]!=u)
            continue;
        dfs2(x);
        a[u]+=a[x];
    }
}
void clr(){
    int i;
    for(i=0;i<=n+1;i=i+1)
        v[i].clear(),a[i]=0,b[i]=0,f[i][0]=0,d[i]=0;
}
int main()
{
    int T,i,j,x,y;
    scanf("%d",&T);
    fac[0]=1;
    for(i=1;i<N;i=i+1)
        fac[i]=mul(fac[i-1],i);
    for(i=0;i<N;i=i+1)
        ifac[i]=fpow(fac[i]);
    while(T--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i=i+1){
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs1(1,0);
        for(j=1;j<=17;j=j+1)
            for(i=1;i<=n;i=i+1)
                f[i][j]=f[f[i][j-1]][j-1];
        for(i=1;i<=n;i=i+1)
            for(j=v[i].size();j--;)
                go(i,v[i][j]);
        dfs2(1);
        x=0;
        for(i=1;i<=n;i=i+1)
            if(a[i]>=2)
                x=1;
        if(x){
            printf("0\n");
            clr();
            continue;
        }
        for(l=1;l<=m;l<<=1);
        for(i=0;i<N;i=i+1)
            e[i]=1;
        for(i=3;i<=n;i=i+1){
            if(!b[i])
                continue;
            for(j=1;j<=i;j=j+2)
                c[j]=mul(fac[i],mul(ifac[j],ifac[i-j]));
            DFT(c,l,1);
            for(j=0;j<l;j=j+1)
                e[j]=mul(e[j],fpow(c[j],b[i])),c[j]=0;
        }
        x=0;
        for(i=2;i<=n;i=i+1)
            if(!a[i])
                x++;
        c[0]=1,c[1]=1;
        DFT(c,l,1);
        for(j=0;j<l;j=j+1)
            e[j]=mul(e[j],fpow(c[j],x)),c[j]=0;
        DFT(e,l,-1);
        printf("%d\n",mul(mul(e[(m+1)/2],fpow(l)),mul(fac[(m+1)/2],fac[m/2])));
        //for(i=0;i<=m;i=i+1)
        //    cout<<mul(e[i],fpow(l))<<' ';cout<<endl;
        clr();
    }
    return 0;
}