前言

賽時(shí)吃了四發(fā)罰（_{我還是太菜了}），但這題真的好玩。

思路

首先考慮答案為 \(0\) 的情況：如果圖不是二分圖或出現(xiàn)了環(huán)，那么必然答案為 \(0\)。為什么出現(xiàn)了環(huán)就是 \(0\) 呢？因?yàn)檫@樣必然會(huì)有交叉的邊，手玩一下就可以搞明白。

此時(shí)，得到第一個(gè)結(jié)論：

• 原圖必然為二分圖且不能有環(huán)。

接下來考慮每一個(gè)與 \(u\) 相連的點(diǎn) \(v\) 可以怎樣排列。首先，注意到如果 \(v\) 的度數(shù)都為 \(1\)，那么怎樣排列都不會(huì)有交叉的邊，設(shè)與 \(u\) 相連的點(diǎn)有 \(sz_u\) 個(gè)，那么點(diǎn) \(u\) 對(duì)答案的貢獻(xiàn)肯定有 \(A^{sz_u}_{sz_u}\) 那么多，這可以預(yù)處理階乘得出。那如果有 \(v\) 的度數(shù) \(d_v \ge 2\) 呢？此時(shí)假設(shè)我們把 \(d_v\ge 2\) 的點(diǎn)放在其它 \(d_v=1\) 的點(diǎn)的中間那么因?yàn)?\(v\) 需要向外面連其它邊，所以就會(huì)和 \(d_v=1\) 的點(diǎn)所連的邊有交叉，不符合題意。所以所有 \(d_v\ge 2\) 的 \(v\) 我們都需要把它放在兩邊，這樣就限定了 \(d_v\ge 2\) 點(diǎn)必然只能有 \(0\)、\(1\) 或 \(2\) 個(gè)。設(shè)這樣的點(diǎn)有 \(x\) 個(gè)且 \(x\in \{0,1,2\}\)，那么剩余點(diǎn)的貢獻(xiàn)便是 \(A^{sz_u-x}_{sz_u-x}\)，因?yàn)樵趦蛇叺狞c(diǎn)可以互換，所以整個(gè) \(u\) 的貢獻(xiàn)便是：\(2\times A^{sz_u-x}_{sz_u-x}\)。于是我們又得出一個(gè)結(jié)論：

• 每個(gè)與 \(u\) 相連的點(diǎn) \(v\)，如果 \(d_v\ge 2\)，那么必須將這個(gè)點(diǎn)放在兩邊，如果這樣點(diǎn)的個(gè)數(shù)超過 \(2\) 個(gè)那么答案就等于 \(0\)。否則，\(u\) 對(duì)答案的貢獻(xiàn)便是 \(2\times A^{sz_u-x}_{sz_u-x}\)。

知道了這兩個(gè)結(jié)論之后，便離正解不遠(yuǎn)了。此時(shí)，可以知道答案便是 \(2\times \prod_{i=1}^{n} val_u\)，其中 \(val_u\) 表示點(diǎn) \(u\) 的貢獻(xiàn)，\(2\) 的存在是因?yàn)榭梢越粨Q河兩岸的點(diǎn)。考慮在 dfs 一次后求出答案。設(shè) \(cnt_u\) 表示在 dfs 遍歷過程中與 \(u\) 相連的點(diǎn)中度數(shù)大于等于 \(2\) 的點(diǎn)的個(gè)數(shù)。則在代碼實(shí)現(xiàn)過程中因?yàn)?dfs 計(jì)算答案時(shí)不會(huì)往回遍歷，所以如果一個(gè)點(diǎn) \(u\) 滿足 \(d_u \ge 2\)，那與其相鄰的節(jié)點(diǎn) \(v\) 就必須滿足 \(cnt_v\le 1\)。同時(shí)，因?yàn)槿绻雅c點(diǎn) \(u\) 相鄰的滿足 \(d_v\ge 2\) 的點(diǎn)左右調(diào)換后所有的類似的結(jié)構(gòu)都會(huì)調(diào)換，所以那個(gè)互換兩邊所得到的 \(2\) 便只需要乘一次了。

代碼

不妨從度數(shù)最大的點(diǎn)開始 dfs，如果該點(diǎn)的度數(shù)仍為 \(1\)，那答案就直接是 \(2\) 了。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define inf (1ll << 62)
#define PII pair<int, int>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5 + 10, mod = 1e9 + 7;
int n, m;
bool flag;
vector<int>G[MAXN], color(MAXN, -1), d(MAXN);
vector<ll>jc(MAXN);
vector<bool>vis(MAXN);

inline void Init() {
	flag = false;
	for(int i = 1; i <= n; i++) {
		G[i].clear();
		d[i] = 0;
		color[i] = -1;
		vis[i] = false;
	}
	return;
}

void dfs(int u, int c, int last) {
	if(flag) return;
	color[u] = c;
	for(auto v : G[u]) {
		if(color[v] == color[u]) {
			flag = true;
			return;
		}
		if(v != last && color[v] != -1) {
			flag = true;
			return;
		}
		if(color[v] != -1) continue;
		dfs(v, c ^ 1, u);
	}
	return;
}

ll dfs1(int u, int f) {
	if(flag) return 0;
	ll res = 1;
	vis[u] = true;
	int cnt = 0, son = 0;
	for(auto v : G[u]) {
		if(vis[v]) continue;
		son++;
		cnt += (d[v] >= 2);
	}
	if(cnt > f) {
		flag = true;
		return 0;
	}
	for(auto v : G[u]) {
		if(vis[v]) continue;
		ll x = dfs1(v, min(f, 1));
		res = (res * x) % mod;
	}
	res = (res * jc[son - cnt]) % mod;
	if(cnt && f == 2) res = (res * 2) % mod;
	return res;
}

inline void solve() {
	cin >> n >> m;
	Init();
	while(m--) {
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
		d[u]++;
		d[v]++;
	}
	dfs(1, 0, 0);
	if(flag) {
		cout << "0\n";
		return;
	}
	int maxn = 0, id;
	for(int i = 1; i <= n; i++) {
		if(maxn < d[i]) {
			maxn = d[i];
			id = i;
		}
	}
	if(maxn == 1) {
		cout << "2\n";
		return;
	}
	cout << dfs1(id, 2) * 2 % mod << "\n";
	return;
}

int main() {
	jc[0] = 1;
	for(int i = 1; i <= 200000; i++) {
		jc[i] = (jc[i - 1] * i) % mod;
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}