これは 300iq Contest 2 の Counting Cactus の高難易度版です。

NEERC では、サボテン（cactus）に関する問題がいくつか出題されてきました。サボテンとは、すべての辺が高々1つの単純サイクルにしか含まれない連結な無向グラフのことです。直感的には、サボテンは木を一般化したものであり、いくつかのサイクルを含むことが許されています。NEERC 2007 の問題におけるサボテンの例を以下の図に示します。

Dreamoon は無向グラフを持っています。彼は、そのグラフのサブグラフ（辺の集合）のうち、サボテンであるものがいくつあるのかを知りたがっています。この値を $998\,244\,353$ で割った余りを求めるのを手伝ってください。

入力

1行目には、Dreamoon のグラフの頂点数 $n$ と辺数 $m$ が与えられます ($1 \le n \leq {\color{red}{\mathbf{18}}}$, $0 \leq m \leq \frac{n(n-1)}{2}$)。

続く $m$ 行には、グラフの辺が記述されます。$i$ 番目の行には、頂点 $a_i$ と $b_i$ を結ぶ辺を表す2つの整数 $a_i$ と $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$) が与えられます。多重辺は存在しないことが保証されています。

出力

Dreamoon のグラフのサブグラフのうち、サボテンであるものの個数を $998\,244\,353$ で割った余りを1つの整数で出力してください。

入出力例

入力 1

3 3
1 2
2 3
3 1

出力 1

4

入力 2

5 0

出力 2

0

入力 3

8 9
1 5
1 8
2 4
2 8
3 4
3 6
4 7
5 7
6 8

出力 3

35

小課題

• ($16$ 点) $n\le 5$
• ($20$ 点) $n\le 7$
• ($14$ 点) $n\le 10$
• ($20$ 点) $n\le 13$
• ($10$ 点) $n\le 16$
• ($20$ 点) 追加の制約なし

注記

• $1\le n\le {\color{red}{\mathbf{18}}}$
• $0\le m\le \frac{n(n-1)}2$
• $u\neq v, 1\le u, v\le n$; 多重辺は存在しません。