AT_fps_24_w 閉路

题目描述

给定一个简单无向图 $G$，包含 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$。
第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。
在所有 $G$ 的生成子图（即包含所有顶点的子图）中，统计有多少个子图满足以下条件，并将结果对 $998244353$ 取模后输出：

• 存在一个包含顶点 $1$ 和顶点 $N$ 的环。

输入格式

输入从标准输入读取，格式如下：

$N\ M$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_M\ B_M$

输出格式

输出满足条件的生成子图的数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

4 5
1 2
1 3
1 4
2 4
3 4

输出 #1

8

输入输出样例 #2

输入 #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

说明/提示

部分分数

本题设有部分分数：

• 若能解决所有 $N \leq 10$ 的数据，将获得 $4$ 分。

样例解释 1

例如，由第 $1$、$2$、$3$、$5$ 条边构成的生成子图满足条件，因为第 $2$、$3$、$5$ 条边构成了一个包含顶点 $1$ 和 $4$ 的环。

约束条件

• $3 \leq N \leq 16$
• $3 \leq M \leq \binom{N}{2}$
• $1 \leq A_i < B_i \leq N$
• 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$
• 所有输入均为整数。

由 ChatGPT 5 翻译