Hide

Problem J
Unicyclic 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$.

\includegraphics[width=0.9\textwidth ]{sampleio1.png}

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

Please log in to submit a solution to this problem

Log in