2018 Asia Singapore Preliminary Contest


2018-09-14 18:00 AKDT

2018 Asia Singapore Preliminary Contest


2018-09-14 23:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1352 days 6:36:41

Time elapsed


Time remaining


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}


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 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
Sample Input 2 Sample Output 2
4 2
1 2
3 4