题解

本题要求计算将 $n$ 座房屋排列在河两岸，并满足所有 $m$ 座桥（边）连接对岸且不交叉的方案数。

关键引理

引理 1：任何包含环的图都不是合法的命运之地地图。
证明：假设存在环且合法。取北岸最左侧的房屋 $v$，它在南岸有两个邻居 $L$ 和 $R$（左、右）。$L$ 必须有另一个邻居，它只能在北岸，且必须在 $v$ 的右侧。但边 $L$—该邻居会与边 $v$—$L$ 交叉，矛盾。故环不可能合法。

引理 2：下面这棵树不合法（一个顶点连接三个或以上非叶邻居）：

   1
  /|\
 2 3 4

证明：$2,3,4$ 都在顶点 $1$ 的对岸。将它们从左到右排列为 $u_1,u_2,u_3$，则 $u_2$ 的邻居必然与边 $1$—$u_1$ 或 $1$—$u_3$ 产生交叉。故这种结构不合法。

由引理 1 和引理 2 可得：

• 图 $G$ 必须是一棵树。
• 任何顶点的非叶邻居数量不能超过 $2$。

图的简化

删除所有叶子节点。由于叶子不是割点（删除后不影响连通性），剩下的图如果非空，仍然是连通的。剩下顶点的度数至多为 $2$（因为非叶邻居 $\le 2$，且所有叶子已删除），故剩余结构必为一条路径。

设剩余路径上的顶点集合为 $S$。

四种情况

情况 1：删除叶子后图为空。
说明原图只有一条边（$n=2, m=1$）。答案为 $2$（两房屋各在河一侧）。

情况 2：只剩下一个顶点。
原图为星形（一个中心顶点连接 $n-1$ 个叶子）。

• 中心顶点可选北岸或南岸：$2$ 种。
• 所有叶子排在中心对岸，顺序任意：$(n-1)!$ 种。
  答案为：

情况 3：剩下两个相连的非叶顶点 $u$ 和 $v$。

• $u$ 和 $v$ 各自连接一些叶子，且分别位于河两岸。
• 合法排列有 $4$ 种（取决于 $u$ 在北/南，以及叶子的相对排列方向）。
• $u$ 的叶子排列方式有 $(d_u - 1)!$ 种，$v$ 的叶子有 $(d_v - 1)!$ 种（除去与对方相连的那条边）。
  答案为：

情况 4：剩余结构是一条长度至少为 $3$ 的路径。

• 该路径的合法排列同样只有 $4$ 种基本方式。
• 对于路径上每个顶点 $r$，设它连接的叶子数为 $S_r$，这些叶子可以任意排列：$S_r!$ 种。
  答案为：

算法步骤

1. 检查输入图是否为树（$m = n-1$ 且连通）。若不然，答案为 $0$。
2. 统计每个顶点的度数，并区分叶子和非叶子。
3. 检查是否存在顶点的非叶邻居数量 $> 2$，若有则直接输出 $0$。
4. 删除所有叶子，得到剩余顶点集合 $S$。
5. 根据 $|S|$ 判断属于哪种情况：
   • $|S| = 0$：情况 $1$，答案 $2$。
   • $|S| = 1$：情况 $2$，答案 $2 \times (n-1)!$。
   • $|S| = 2$：情况 $3$，答案 $4 \times (d_u-1)! \times (d_v-1)!$。
   • $|S| \ge 3$：情况 $4$，答案 $4 \times \prod_{r \in S} (S_r!)$。
6. 所有阶乘和乘法均对 $10^9+7$ 取模。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

代码参考

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
const int MAXN = 200005;

vector<int> adj[MAXN];
int deg[MAXN];
ll fact[MAXN];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        deg[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++; deg[v]++;
    }

    // 不是树
    if (m != n - 1) {
        cout << "0\n";
        return;
    }

    // 检查非叶邻居数量
    for (int u = 1; u <= n; u++) {
        int cnt = 0;
        for (int v : adj[u]) {
            if (deg[v] > 1) cnt++;
        }
        if (cnt > 2) {
            cout << "0\n";
            return;
        }
    }

    // 收集非叶顶点
    vector<int> nonleaf;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 1) nonleaf.push_back(i);
    }

    if (nonleaf.empty()) {
        // 情况 1: 只有一条边
        cout << "2\n";
        return;
    } else if (nonleaf.size() == 1) {
        // 情况 2: 星形
        cout << 2 * fact[n - 1] % MOD << "\n";
        return;
    }

    // 构建非叶子之间的诱导子图
    vector<int> nonleaf_deg(n + 1, 0);
    for (int u : nonleaf) {
        for (int v : adj[u]) {
            if (deg[v] > 1) nonleaf_deg[u]++;
        }
    }

    // 检查非叶子子图是否为路径
    int endpoints = 0;
    for (int u : nonleaf) {
        if (nonleaf_deg[u] == 1) endpoints++;
        else if (nonleaf_deg[u] != 2) {
            cout << "0\n";
            return;
        }
    }
    if (endpoints != 2 && endpoints != 0) {
        cout << "0\n";
        return;
    }

    // 情况 3: 两个非叶子
    if (nonleaf.size() == 2) {
        int u = nonleaf[0], v = nonleaf[1];
        cout << 4 * fact[deg[u] - 1] % MOD * fact[deg[v] - 1] % MOD << "\n";
        return;
    }

    // 情况 4: 非叶子路径长度 >= 3
    ll ans = 4;
    for (int u : nonleaf) {
        int leaf_cnt = deg[u] - nonleaf_deg[u];
        ans = ans * fact[leaf_cnt] % MOD;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}