仙人掌[ZJOI2017]

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;

template <typename T>
inline void read(T &num) {
	T x = 0, ff = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') ff = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	num = x * ff;
}

const ll mod = 998244353;
int ttt, n, m;
int head[N], pre[N<<1], to[N<<1], sz;
int dfn[N], low[N], stk[N], top, c[N], tot, tme;
ll f[N], g[N], p[N];
bool tmp[N], flag;

inline void addedge(int u, int v) {
	pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
	pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

void init() {
    for (int i = 1; i <= n; i++) head[i] = 0; sz = 0;
    for (int i = 1; i <= n; i++) dfn[i] = low[i] = 0, f[i] = 0;
    tme = top = 0; flag = 0;
}


void solve(int X) {
    //判断是否是仙人掌
    for (int i = 1; i <= tot; i++) tmp[c[i]] = 1;
    int cnt = 0;
    for (int i = 1; i <= tot; i++) {
        int x = c[i];
        for (int j = head[x]; j; j = pre[j]) if (tmp[to[j]]) cnt++;
    }
    if (cnt != tot * 2) flag = 1;
    for (int i = 1; i <= tot; i++) tmp[c[i]] = 0;
    //
    
    //维护DP值
    for (int i = 1; i < tot; i++) f[X] = f[X] * g[c[i]] % mod; //c[1]~c[tot-1]为环上除x之外的其它点
    //
}

void tarjan(int x) {
    dfn[x] = low[x] = ++tme; stk[++top] = x;
    f[x] = 1;
    int cnt = 0;
    for (int i = head[x]; i; i = pre[i]) {
        int y = to[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (dfn[x] == low[y]) {
                int z = 0; tot = 0;
                do {
                    z = stk[top--];
                    c[++tot] = z;
                } while (z != y);
                c[++tot] = x;
                if (tot > 2) solve(x); //找到环
                else {
                    cnt++;
                    f[x] = f[x] * f[y] % mod;
                }
            } 
        } else low[x] = min(low[x], dfn[y]);
    }
    g[x] = f[x] * p[cnt] % mod;
    f[x] = f[x] * p[cnt+(x!=1)] % mod;
}

int main() {
    read(ttt);
    p[0] = p[1] = 1;
    for (int i = 2; i <= 500000; i++) p[i] = (p[i-1] + p[i-2] * (i-1) % mod) % mod;
    while (ttt--) {
        read(n); read(m);
        for (int i = 1, u, v; i <= m; i++) {
            read(u); read(v);
            addedge(u, v);
        }
        tarjan(1); 
        if (flag) puts("0");
        else printf("%lld\n", f[1]);
        init();
    }
    return 0;
}