Description：

给一个无向连通图，问有几种加边的方案最后形成了一棵仙人掌。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

首先随便求出来一个生成树，然后把生成树上环上的边都删掉，那么最后会形成一个森林，那么思考一下就会发现树之间不会有边，那么可以对每棵树分别计算最后乘起来，对于一棵树的情况，我们可以把一条非树边还是看成树上的一段路径，那么问题就转换成了给一棵树，要求在树上选一些边不相交的链的方案数，考虑树形 $DP$ ：

$f[i]$ 表示子树 $i$ 不向上扩展的方案数， $g[i]$ 表示向上扩展，发现这样不好转移于是再设一个 $h[i]$ 表示把 $i$ 个点两两配对的方案数，先预处理 $h$ ： $$ h[i]=h[i-1]+(i-1)\times h[i-2] $$ 然后是 $f$ ： $$ f[k]=h[|ch|]\times \prod_{i\in ch}g[i] $$ 最后是 $g$ ： $$ g[k]=f[k]+ch\times h[|ch|-1]\times \prod_{i\in ch}g[i] $$ 妙妙妙。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 1000010

struct edges

{

	int u,v;

}es[MAXN];

struct edge

{

	int to,nxt,id;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int id)

{

	e[++edgenum] = (edge){b,lin[a],id};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],id};lin[b] = edgenum;

	return;

}

bool vis[MAXN];

int fa[MAXN];

bool tagp[MAXN],tage[MAXN];

vector<int> t[MAXN];

int ind[MAXN];

void addt(int a,int b)

{//cout << a << " => " << b << endl;

	++ind[b];

	t[a].push_back(b);

	return;

}

bool prework(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		if(tage[e[i].id])continue;

		if(vis[e[i].to])

		{

			for(int cur = k;cur != e[i].to;cur = fa[cur])

			{

				if(tagp[cur])return false;

				tagp[cur] = true;

			}

			tage[e[i].id] = true;

			continue;

		}//cout << k << " -> " << e[i].to << endl;

		fa[e[i].to] = k;

		if(!prework(e[i].to))return false;

	}

	return true;

}

#define MOD 998244353

int f[MAXN],h[MAXN],g[MAXN];

int dp(int k,int fa)

{

	vis[k] = true;

	int sum = 1,cnt = 0;

	for(vector<int>::iterator it = t[k].begin();it != t[k].end();++it)

	{

		if(*it == fa)continue;

		dp(*it,k);

		sum = 1ll * sum * g[*it] % MOD;

		++cnt;

	}

	f[k] = 1ll * h[cnt] * sum % MOD;

	g[k] = (f[k] + 1ll * cnt * h[cnt - 1] % MOD * sum % MOD) % MOD;

	return f[k];

}

void work()

{

	edgenum = 0;

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)ind[i] = lin[i] = fa[i] = 0;

	for(int i = 1;i <= n;++i)vis[i] = tagp[i] = false;

	for(int i = 1;i <= m;++i)tage[i] = false;

	for(int i = 1;i <= m;++i)add(es[i].u = rd(),es[i].v = rd(),i);

	for(int i = 1;i <= n;++i)t[i].clear();

	h[0] = 1;h[1] = 1;

	for(int i = 2;i <= n;++i)h[i] = (h[i - 1] + 1ll * (i - 1) * h[i - 2] % MOD) % MOD;

	if(!prework(1))

	{

		puts("0");

		return;

	}

	for(int k = 2;k <= n;++k)if(tagp[k])

	{

		for(int i = lin[k];i != 0;i = e[i].nxt)if(e[i].to == fa[k])tage[e[i].id] = true;

	}

	for(int i = 1;i <= n;++i)if(fa[i] != 0 && !tagp[i])addt(fa[i],i);

	int ans = 1;

	for(int i = 1;i <= n;++i)vis[i] = false;

	for(int i = 1;i <= n;++i)if(!vis[i] && ind[i] == 0)ans = 1ll * ans * dp(i,0) % MOD;

	printf("%d\n",ans);

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}