← 返回题目列表

AtCoder · abc411_g

G. 计数周期

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

分数: 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 循环。 圆圈内的数字和线旁边的数字分别表示顶点数和边数。 红线代表循环中包含的边缘,黑线代表其他边缘。

Three figures representing the graphs are arranged from left to right. Painted red are edges 1,2,3, edges 2,3,4, and edges 1,4 from left to right.

从左到右,这些对应于选择边缘集 \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