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$ 取模。

## 部分分数 本题设有部分分数： - 若能解决所有 $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 翻译