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
CPU Time limit 2 seconds
Memory limit 1024 MB
Author
Syx Pek
Source ICPC SG Preliminary Contest 2018
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in