#include<bits/stdc++.h> #define N 1000005 usingnamespacestd; typedeflonglong ll;
template <typename T> inlinevoidread(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;
voidinit(){ 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; }
voidsolve(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之外的其它点 // }
voidtarjan(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; }
intmain(){ 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"); elseprintf("%lld\n", f[1]); init(); } return0; }