Hide

# Problem JUnicyclic Count

A unicyclic graph is a graph with exactly one cycle. A spanning subgraph of a graph $G$ is a subgraph that has one component and includes all the vertices of $G$. Given a simple graph $G$, count the number of spanning unicyclic subgraphs. The illustration below shows the visualization of Sample Input/Output $1$.

## Input

The first line of the input contains two integers, $V$ and $E$, representing the number of vertices and edges of the graph $G$ respectively. ($1 \leq V \leq 17, 0 \leq E \leq V(V-1)/2$.)

The following $E$ lines each contains two integers $A_ i$ and $B_ i$, representing an edge $(A_ i, B_ i)$. It is guaranteed that $1 \leq A_ i < B_ i \leq V$ and as the graph is simple, no two pairs represent the same edge.

## Output

Output one integer, representing the number of spanning unicylic subgraphs. As the number can be rather big, output it modulo $10^9 + 7$.

Sample Input 1 Sample Output 1
4 5
1 2
1 3
2 3
1 4
2 4

5

Sample Input 2 Sample Output 2
4 2
1 2
3 4

0

CPU Time limit 2 seconds
Memory limit 1024 MB