← 返回题目列表

AtCoder · arc105_f

F. 连接图上的灯熄灭

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

分数: 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.