Given an undirected graph, count the number of simple cycles in the graph. Here, a simple cycle is a connected subgraph all of whose vertices have degree exactly two.

The input consists of a single test case of the following format.

$n$ $m$ $u_1$ $v_1$ ... $u_m$ $v_m$

A test case represents an undirected graph $G$.

The first line shows the number of vertices $n$ ($3 \leq n \leq 100 000$) and the number of edges $m$ ($n - 1 \leq m \leq n + 15$). The vertices of the graph are numbered from $1$ to $n$.

The edges of the graph are specified in the following $m$ lines. Two integers $u_i$ and $v_i$ in the $i$-th line of these m lines mean that there is an edge between vertices $u_i$ and $v_i$. Here, you can assume that $u_i < v_i$ and thus there are no self loops.

For all pairs of $i$ and $j$ ($i \ne j$), either $u_i \ne u_j$ or $v_i \ne v_j$ holds. In other words, there are no parallel edges.

You can assume that $G$ is connected.

The output should be a line containing a single number that is the number of simple cycles in the graph.

4 5 1 2 1 3 1 4 2 3 3 4

3

7 9 1 2 1 3 2 4 2 5 3 6 3 7 2 3 4 5 6 7

3

4 6 1 2 1 3 1 4 2 3 2 4 3 4

7

Source: ACM International Collegiate Programming Contest
, Asia Regional Tsukuba, Tsukuba, Japan, 2017-12-17

http://icpc.iisf.or.jp/2017-tsukuba/

http://icpc.iisf.or.jp/2017-tsukuba/