【仙人掌图性质与乘法原理生成树计数】GESP八级 / CSP-S 题解：luogu-P17461 [GESP202609 八级] 生成树计数

7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4

12

/**
 * Problem: luogu-P17461
 * Standard: C++11 (CCF GESP 官方大纲规范)
 * Author: OneCoder
 */

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;
const int MOD = 998244353;

vector<int> adj[MAXN];
int depth_arr[MAXN];
bool visited[MAXN];
long long ans = 1;

void dfs(int u, int p, int d) {
    depth_arr[u] = d;
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (visited[v]) {
            if (depth_arr[v] < depth_arr[u]) {
                // 返祖边：找到一个简单环
                int cycle_len = depth_arr[u] - depth_arr[v] + 1;
                ans = (ans * cycle_len) % MOD;
            }
        } else {
            dfs(v, u, d + 1);
        }
    }
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

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

    dfs(1, 0, 1);

    cout << ans << "\n";

    return 0;
}