分数: 8 点
问题陈述
给你一个简单的无向图 G 与 N 顶点和 M 边,其中顶点编号 1 通过 N.
的 i第一条边连接顶点 A_i 和顶点 B_i.
在所有跨越子图中 G(即覆盖所有顶点的子图 G),统计满足以下条件的个数,并输出结果模 998244353:
- 存在一个包含两个顶点的循环 1 和顶点 N.
约束
- 3 \leq N \leq 16
- 3 \leq M \leq \binom{N}{2}
- 1 \leq A_i < B_i \leq N
- If i \neq j,然后 (A_i, B_i) \neq (A_j, B_j)
- 所有输入值均为整数
部分分数
该问题有部分评分:
- 如果您使用以下方法求解所有数据集 N \leq 10,您将获得 4 点。
输入
输入由标准输入给出,格式如下:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
打印 的跨越子图的数量 G 满足条件,取模 998244353.
示例输入 1
4 5 1 2 1 3 1 4 2 4 3 4
示例输出 1
8
例如,由边组成的生成子图 1, 2, 3,和 5 满足条件,因为边 2, 3,和 5 形成一个包含两个顶点的循环 1 和顶点 4.
示例输入 2
6 15 1 2 1 3 2 3 1 4 2 4 3 4 1 5 2 5 3 5 4 5 1 6 2 6 3 6 4 6 5 6
示例输出 2
20448