前言
赛时吃了四发罚（我还是太菜了），但这题真的好玩。
思路
首先考虑答案为 000 的情况：如果图不是二分图或出现了环，那么必然答案为 000。为什么出现了环就是 000 呢？因为这样必然会有交叉的边，手玩一下就可以搞明白。
此时，得到第一个结论：
- 原图必然为二分图且不能有环。
接下来考虑每一个与 uuu 相连的点 vvv 可以怎样排列。首先，注意到如果 vvv 的度数都为 111，那么怎样排列都不会有交叉的边，设与 uuu 相连的点有 szusz_uszu 个，那么点 uuu 对答案的贡献肯定有 AszuszuA^{sz_u}_{sz_u}Aszuszu 那么多，这可以预处理阶乘得出。那如果有 vvv 的度数 dv≥2d_v \ge 2dv≥2 呢？此时假设我们把 dv≥2d_v\ge 2dv≥2 的点放在其它 dv=1d_v=1dv=1 的点的中间那么因为 vvv 需要向外面连其它边，所以就会和 dv=1d_v=1dv=1 的点所连的边有交叉，不符合题意。所以所有 dv≥2d_v\ge 2dv≥2 的 vvv 我们都需要把它放在两边，这样就限定了 dv≥2d_v\ge 2dv≥2 点必然只能有 000、111 或 222 个。设这样的点有 xxx 个且 x∈{0,1,2}x\in \{0,1,2\}x∈{0,1,2}，那么剩余点的贡献便是 Aszu−xszu−xA^{sz_u-x}_{sz_u-x}Aszu−xszu−x，因为在两边的点可以互换，所以整个 uuu 的贡献便是：2×Aszu−xszu−x2\times A^{sz_u-x}_{sz_u-x}2×Aszu−xszu−x。于是我们又得出一个结论：
- 每个与 uuu 相连的点 vvv，如果 dv≥2d_v\ge 2dv≥2，那么必须将这个点放在两边，如果这样点的个数超过 222 个那么答案就等于 000。否则，uuu 对答案的贡献便是 2×Aszu−xszu−x2\times A^{sz_u-x}_{sz_u-x}2×Aszu−xszu−x。
知道了这两个结论之后，便离正解不远了。此时，可以知道答案便是 2×∏i=1nvalu2\times \prod_{i=1}^{n} val_u2×∏i=1nvalu，其中 valuval_uvalu 表示点 uuu 的贡献，222 的存在是因为可以交换河两岸的点。考虑在 dfs 一次后求出答案。设 cntucnt_ucntu 表示在 dfs 遍历过程中与 uuu 相连的点中度数大于等于 222 的点的个数。则在代码实现过程中因为 dfs 计算答案时不会往回遍历，所以如果一个点 uuu 满足 du≥2d_u \ge 2du≥2，那与其相邻的节点 vvv 就必须满足 cntv≤1cnt_v\le 1cntv≤1。同时，因为如果把与点 uuu 相邻的满足 dv≥2d_v\ge 2dv≥2 的点左右调换后所有的类似的结构都会调换，所以那个互换两边所得到的 222 便只需要乘一次了。
代码
不妨从度数最大的点开始 dfs，如果该点的度数仍为 111，那答案就直接是 222 了。
#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;
}