406253: GYM102331 C Counting Cactus

NEERC featured a number of problems about cactuses: connected undirected graphs in which every edge belongs to at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. An example of a cactus from NEERC 2007 problem is given on the picture below.

Dreamoon has an undirected graph. Now he is wondering, how many subgraphs (subsets of edges) of his graph are cactuses? Can you help him find this value modulo $$$998\,244\,353$$$?

The first line contains two integers $$$n$$$ and $$$m$$$: the number of vertices and edges in the Dreamoon's graph ($$$1 \le n \leq 13$$$, $$$0 \leq m \leq \frac{n(n-1)}{2}$$$).

The next $$$m$$$ lines describe edges in the graph. The $$$i$$$-th of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$), denoting an edge between vertices $$$a_i$$$ and $$$b_i$$$. It is guaranteed that there are no multiple edges.

Output one integer: the number of cactus subgraphs of Dreamoon's graph, modulo $$$998\,244\,353$$$.

3 3
1 2
2 3
3 1

4

5 0

0

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

35

Sorry, Dreamoon.