To jest trudniejsza wersja zadania Counting Cactus z zawodów 300iq Contest 2.

Podczas zawodów NEERC pojawiło się wiele zadań dotyczących kaktusów: spójnych grafów nieskierowanych, w których każda krawędź należy do co najwyżej jednego cyklu prostego. Intuicyjnie, kaktus jest uogólnieniem drzewa, w którym dozwolone są pewne cykle. Przykład kaktusa z zadania NEERC 2007 przedstawiono na poniższym rysunku.

Dreamoon posiada graf nieskierowany. Zastanawia się teraz, ile podgrafów (podzbiorów krawędzi) jego grafu to kaktusy? Czy możesz pomóc mu wyznaczyć tę wartość modulo $998\,244\,353$?

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n$ oraz $m$: liczba wierzchołków i krawędzi w grafie Dreamoona ($1 \le n \leq {\color{red}{\mathbf{18}}}$, $0 \leq m \leq \frac{n(n-1)}{2}$).

Kolejne $m$ linii opisuje krawędzie grafu. $i$-ta z tych linii zawiera dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$), oznaczające krawędź między wierzchołkami $a_i$ oraz $b_i$. Gwarantuje się, że w grafie nie ma krawędzi wielokrotnych.

Wyjście

Wypisz jedną liczbę całkowitą: liczbę podgrafów będących kaktusami w grafie Dreamoona, modulo $998\,244\,353$.

Przykład

Wejście 1

3 3
1 2
2 3
3 1

Wyjście 1

4

Wejście 2

5 0

Wyjście 2

0

Wejście 3

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

Wyjście 3

35

Uwagi

• $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$; brak krawędzi wielokrotnych.

Podzadania:

• ($16$ punktów) $n\le 5$
• ($20$ punktów) $n\le 7$
• ($14$ punktów) $n\le 10$
• ($20$ punktów) $n\le 13$
• ($10$ punktów) $n\le 16$
• ($20$ punktów) Brak dodatkowych ograniczeń