406253: GYM102331 C Counting Cactus
Description
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.
![](https://espresso.codeforces.com/ef5ac8b21009d1ab642a2cc10032bc06e3abac4b.png)
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$$$?
InputThe 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.
OutputOutput one integer: the number of cactus subgraphs of Dreamoon's graph, modulo $$$998\,244\,353$$$.
ExamplesInput3 3 1 2 2 3 3 1Output
4Input
5 0Output
0Input
8 9 1 5 1 8 2 4 2 8 3 4 3 6 4 7 5 7 6 8Output
35Note
Sorry, Dreamoon.