Counting Cactus

Time limit2sMemory limit512 MB

Summary

Count the edge subsets of a graph with at most 13 vertices that form a connected cactus, modulo 998244353.

Level: Hard8 of 10
Topics: Bit manipulation, Dynamic programming, Graph
Solved: No attempts yet

Problem

NEERC has featured several 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. The picture below shows a cactus from a NEERC 2007 problem.

Dreamoon has an undirected graph. He wants to know how many subgraphs (subsets of edges) of his graph are cactuses. Can you find this value modulo 998 244 353?

Input

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

The next $m$ lines describe the edges. The $i$ -th line contains two integers $a_i$ and $b_i$ , denoting an edge between vertices $a_i$ and $b_i$ . ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ ) No edge appears more than once.

Output

Output one integer: the number of cactus subgraphs, modulo 998 244 353.

Hint

Sorry, Dreamoon.

Examples3

Example 1
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
4
```
Example 2
Input
```
5 0
```
Expected output
```
0
```

Example 3

Input

Expected output