問題文

頂点に $1,2,\ldots,n$ の番号が、辺に $1,2,\ldots,m$ の番号が付いた $n$ 頂点 $m$ 辺の単純無向グラフがあります。辺 $i$ は頂点 $u _ i$ と頂点 $v _ i$ を双方向に結んでいます。

suisen 君は $m$ 本の辺のうち $0$ 本以上を 赤く 塗り、それ以外の辺を 青く 塗ります。以下では 赤い 辺のみからなる単純閉路のことを単に 赤い 閉路 と呼びます。

suisen 君の辺の塗り方のうち、以下の条件を満たすものの個数を求めてください。

• 任意の相異なる $2$ つの 赤い 閉路に対して、その両方に含まれる頂点は存在しない。

ここで、$2$ つの 赤い 閉路に対して、その一方にしか含まれない辺が存在するとき、かつそのときに限り $2$ つの 赤い 閉路は異なるものとします。

なお、本問題の制約下で、答えは $2^{63}$ 未満であることを証明できます。

入力

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

$n\ m$
$u _ 1\ v _ 1$
$u _ 2\ v _ 2$
$\vdots$
$u _ m\ v _ m$

• 入力は全て整数で与えられる。
• 与えられるグラフは単純である。
• $2\leq n\leq 13$
• $1\leq m\leq \dfrac{n(n - 1)}{2}$
• $1\leq u _ i \lt v _ i \leq n$
• $i \neq j$ ならば $(u _ i, v _ i) \neq (u _ j, v _ j)$

出力

答えを $1$ 行に出力し、改行してください。

サンプル

サンプル1

入力

6 7
1 4
1 5
2 5
3 5
3 6
4 5
5 6

出力

126

この入力は次のグラフを表しています。

例えば辺 $1,2,3,4,6,7$ を 赤く 塗り、辺 $5$ を 青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 $1,2,6$ からなるものしかありません。従って、この塗り方は条件を満たします。

他の例として、辺 $1,2,4,5,6,7$ を 赤く 塗り、辺 $3$ を 青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 $1,2,6$ からなるものと辺 $4,5,7$ からなるものの $2$ つ存在します。この $2$ つの閉路はともに頂点 $5$ を含むため、この塗り方は条件を満たしません。

辺の塗り方は全部で $2 ^ m = 128$ 通りありますが、条件を満たさない塗り方は次の $2$ 通りしかありません。

• 辺 $1,2,4,5,6,7$ を 赤く 塗り、辺 $3$ を 青く 塗った場合
• 全ての辺を 赤く 塗った場合

従って、この入力に対する答えは $128 - 2 = 126$ です。

6 10
1 2
1 3
1 4
1 5
2 3
2 4
2 6
3 5
4 6
5 6

816