3885. [300iq Contest 2] 数仙人掌 加强版

【题目描述】

题面参考 Codeforces Gym 102331 C. Counting Cactus。

仙人掌是一种无向连通图，其中每条边最多在一个简单环内。

Dreamoon 现在有一个无向图，他想知道这个无向图有多少子图（边的子集）是一个仙人掌？请你找到方案数取模 $998244353$。

【输入格式】

第一行输入两个整数 $n, m$ 表示图的点数和边数。

接下来 $m$ 行，每行两个数 $u, v$，表示一条边的两个端点，保证输入没有重边和自环。

【输出格式】

输出一个整数表示生成仙人掌的数量，对 $998244353$ 取模。

【样例1输入】

3 3
1 2
2 3
3 1

【样例1输出】

4

【样例2输入】

5 0

【样例2输出】

0

【样例3输入】

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

【样例3输出】

35

【数据规模与约定】

测试点$1 \sim 9$：$n \leq 5$;

测试点$10 \sim 14$：$n \leq 7$;

测试点$15 \sim 19$：$n \leq 10$;

测试点$20 \sim 22$：$n \leq 13$;

测试点$23 \sim 25$：$n \leq 16$;

对于全部数据，$1\le n\le \mathbf{18}，0\le m\le \frac{n(n-1)}2$，

$u\neq v, 1\le u, v\le n$, 输入的全体 $(u, v), (v, u)$ 互不相同

【来源】

https://loj.ac/p/6719