Counting Cycles

You are given an undirected graph. Count the simple cycles in it. A simple cycle is a connected subgraph in which every vertex has degree exactly two.

The input is one test case in the following format.

n m
u_1 v_1
...
u_m v_m

The test case describes an undirected graph $G$.

The first line has the number of vertices $n$ ($3 \le n \le 100000$) and the number of edges $m$ ($n - 1 \le m \le n + 15$). The vertices are numbered 1 to $n$.

Each of the next $m$ lines describes one edge. The two integers $u_i$ and $v_i$ on the $i$-th of these lines mean that an edge joins vertex $u_i$ and vertex $v_i$. You may assume $u_i < v_i$, so no edge is a self loop.

For every pair $i \ne j$, either $u_i \ne u_j$ or $v_i \ne v_j$ holds, so the graph has no parallel edges.

You may assume that $G$ is connected.

Print one line containing the number of simple cycles in the graph.