201055: [AtCoder]ARC105 F - Lights Out on Connected Graph

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $900$ points

Problem Statement

Given is an undirected graph $G$ consisting of $N$ vertices numbered $1$ through $N$ and $M$ edges numbered $1$ through $M$. It is guaranteed that $G$ is connected and contains no self-loops and no multi-edges. Edge $i$ connects Vertex $a_i$ and Vertex $b_i$ bidirectionally. Each edge can be painted red or blue. Initially, every edge is painted red.

Consider making a new graph $G^{\prime}$ by removing zero or more edges from $G$. There are $2^M$ graphs that $G^{\prime}$ can be. Among them, find the number of good graphs defined below, modulo $998244353$.

$G^{\prime}$ is said to be a good graph when both of the following conditions are satisfied:

  • $G^{\prime}$ is connected.
  • It is possible to make all edges blue by doing the following operation zero or more times.
    • Choose one vertex and change the color of every edge incident to that vertex, that is, red to blue and vice versa.

Constraints

  • All values in input are integers.
  • $1 \leq N \leq 17$
  • $N-1 \leq M \leq N(N-1)/2$
  • $G$ is connected and has no self-loops and no multi-edges.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

Output

Print the number of good graphs among the ones that $G^{\prime}$ can be, modulo $998244353$.


Sample Input 1

3 2
1 2
2 3

Sample Output 1

1
  • The conditions are satisfied only if neither Edge $1$ nor Edge $2$ is removed.
    • In this case, we can make all edges blue by, for example, doing the operation for Vertex $2$.
  • Otherwise, the graph gets disconnected and thus does not satisfy the condition.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

19

Sample Input 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

Sample Output 3

90625632
  • Be sure to find the count modulo $998244353$.

Input

题意翻译

### 题意 有一张 $n$ 个点 $m$ 条边的简单无向图,问选出一个边集,使得 $n$ 个点与这些边构成的图连通,并且图是二分图的方案数。 对 $998244353$ 取模。 $1\leq n\leq 17,n-1\leq m\leq \frac{n(n-1)}{2}$。

加入题单

上一题 下一题 算法标签: