← 返回题目列表

AtCoder · fps_24_w

W. 循环

中文机器翻译题面 查看原题

分数: 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