分数: 600 点
问题陈述
有一个无向图 G 与 N 顶点和 M 边缘。 G 不包含自环,但可能包含多边。 顶点编号从 1 to N,边的编号从 1 to M,有边缘 i 连接顶点 U_i,V_i.
求模数 998244353,包含在 G.
更正式地说,求模数 998244353,子集 满足以下条件的给定边集的 \lbrace e_1,e_2,\dots,e_k\rbrace \subseteq \lbrace 1,2,\dots,M\rbrace\ (k\geq 2) 。
- 存在一个排列 (e_1',e_2',\dots,e_k') of (e_1,e_2,\dots,e_k) 和顶点序列 (v_1,v_2,\dots,v_k) 使得以下所有条件成立:
- v_1,v_2,\dots,v_k 两两不同;
- 对于所有人 j\ (1\leq j\leq k),边缘 e_j' 连接顶点 v_j,v_{(j\bmod k) + 1}.
约束
- 2\leq N \leq 20
- 2\leq M \leq 2\times 10^5
- 1\leq U_i < V_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
输出答案。
示例输入 1
3 4 1 3 1 2 2 3 1 3
示例输出 1
3
如下图所示,一共有 3 循环。 圆圈内的数字和线旁边的数字分别表示顶点数和边数。 红线代表循环中包含的边缘,黑线代表其他边缘。

从左到右,这些对应于选择边缘集 \lbrace 1,2,3 \rbrace,\lbrace 2,3,4 \rbrace,\lbrace 1,4 \rbrace。
示例输入 2
4 2 1 4 2 3
示例输出 2
0
示例输入 3
5 15 1 5 3 4 2 3 2 4 3 5 4 5 2 5 2 3 1 3 4 5 2 5 4 5 1 2 3 4 1 5
示例输出 3
166