W - Cycle Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 8 点

問題文

頂点に 1 から N までの番号がついた N 頂点 M 辺の単純無向グラフ G が与えられます。i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。
G の全域部分グラフ(全ての頂点を含む部分グラフ)のうち、次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 頂点 1 と頂点 N がともに含まれる閉路が存在する。

制約

  • 3 \leq N \leq 16
  • 3 \leq M \leq \binom{N}{2}
  • 1 \leq A_i \lt B_i \leq N
  • i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
  • 入力される値は全て整数

部分点

この問題には部分点が設定されている。

  • N \leq 10 を満たすデータセットに正解した場合、4 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

G の全域部分グラフのうち、条件を満たすものの個数を 998244353 で割った余りを出力せよ。

入力例 1

4 5
1 2
1 3
1 4
2 4
3 4

出力例 1

8

例えば辺集合が 1 番目の辺、2 番目の辺、3 番目の辺、5 番目の辺からなる全域部分グラフは条件を満たします。なぜならば、2 番目の辺、3 番目の辺、5 番目の辺が頂点 1 と頂点 4 がともに含まれる閉路をなすからです。

入力例 2

6 15
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6

出力例 2

20448

Score: 8 points

Problem Statement

You are given a simple undirected graph G with N vertices and M edges, where the vertices are numbered 1 through N.
The i-th edge connects vertex A_i and vertex B_i.
Among all spanning subgraphs of G(that is, subgraphs covering all vertices of G), count how many satisfy the following condition, and output the result modulo 998244353:

  • There exists a cycle that contains both vertex 1 and vertex N.

Constraints

  • 3 \leq N \leq 16
  • 3 \leq M \leq \binom{N}{2}
  • 1 \leq A_i < B_i \leq N
  • If i \neq j, then (A_i, B_i) \neq (A_j, B_j)
  • All input values are integers

Partial Score

This problem has partial scoring:

  • If you solve all datasets with N \leq 10, you will earn 4 points.

Input

The input is given from standard input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the number of spanning subgraphs of G that satisfy the condition, modulo 998244353.

Sample Input 1

4 5
1 2
1 3
1 4
2 4
3 4

Sample Output 1

8

For example, the spanning subgraph consisting of edges 1, 2, 3, and 5 satisfies the condition, because edges 2, 3, and 5 form a cycle that contains both vertex 1 and vertex 4.

Sample Input 2

6 15
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6

Sample Output 2

20448