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