分数: 900 点
问题陈述
给定的是一个无向图 G 组成 N 顶点编号 1 通过 N 和 M 边编号 1 通过 M。可以保证 G 已连通且不包含自环和多边。 边缘 i 连接顶点 a_i 和顶点 b_i 双向。 每个边缘都可以涂成红色或蓝色。最初,每个边缘都被漆成红色。
考虑制作一个新图表 G^{\prime} 通过从 G。 有 2^M 图表表明 G^{\prime} 可以。其中,求下面定义的好图的数量,取模 998244353.
G^{\prime} 据说是 好图 当满足以下两个条件时:
- G^{\prime} 已连接。
- 通过执行以下操作零次或多次,可以将所有边缘变为蓝色。
- 选择一个顶点并更改入射到该顶点的每条边的颜色,即从红色变为蓝色,反之亦然。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 17
- N-1 \leq M \leq N(N-1)/2
- G 已连通且无自环且无多边。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 \vdots a_M b_M
输出
打印以下图表中好图表的数量 G^{\prime} 可以是,模 998244353.
样本输入 1
3 2 1 2 2 3
示例输出 1
1
- 仅当两个边都没有时才满足条件 1 也不是边缘 2 已删除。
- 在这种情况下,我们可以通过例如对 Vertex 进行操作来将所有边变成蓝色 2.
- 否则,图形将断开连接,因此不满足条件。
示例输入 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
示例输出 2
19
示例输入 3
17 50 16 17 10 9 16 10 5 17 6 15 5 9 15 11 16 1 8 13 6 17 15 3 16 15 11 3 7 6 1 4 11 13 10 6 10 12 3 16 7 3 16 5 13 3 12 13 7 11 3 12 13 10 1 12 9 15 11 14 4 6 13 2 6 1 15 2 1 14 15 17 2 11 14 13 16 9 16 8 8 17 17 12 1 11 6 12 17 2 8 1 14 6 9 7 11 10 5 14 17 7
示例输出 3
90625632
- 一定要找到计数模数 998244353.