[AdditionalFile6729.zip](file://AdditionalFile6729.zip?type=additional_file)

#6729. 点双连通生成子图计数

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

一个无向图是点双连通的，当且仅当它删去任意一个节点后，剩下的子图都是连通的。

给你一个简单无向图，要你求出它有多少个生成子图（边的子集）是点双连通的。 你只需要输出它对 $998244353$ 取模后的值。

输入格式

第一行两个非负整数 $n, m$，分别表示无向图的点数和边数。

接下来 $m$ 行每行两个正整数 $u, v$，表示一条无向边。保证没有重边和自环。

输出格式

一行一个非负整数表示方案数模 $998244353$ 的值。

样例 1

输入

3 3
1 2
2 3
3 1

输出

1

样例 2

输入

7 13
3 2
7 6
7 2
4 6
6 1
5 7
1 5
5 4
7 1
3 5
4 3
6 5
3 1

输出

420

数据范围与提示

• $1\leq n\leq 18$
• $0\leq m \leq \frac{n(n-1)}{2}$
• $1 \leq u,v \leq n$，输入的全体 $(u,v)$，$(v,u)$ 互不相同

子任务：

• （$16$ 分） $n\leq 5$
• （$20$ 分） $n \leq 7$
• （$14$ 分） $n \leq 10$
• （$20$ 分） $n \leq 13$
• （$10$ 分） $n\leq 16$
• （$20$ 分） 没有附加限制