Problem: Problem K Counting Cycles

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.

Input

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.

Output

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

Sample Input 1


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


Sample Output 1


3


Sample Input 2


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


Sample Output 2


3


Sample Input 3


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


Sample Output 3


7






Example

Input

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


Output

3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100017;
bool cutted[maxn];
int cuts[maxn],cmp[maxn],used[maxn];
vector<int> G[maxn], sG[maxn];
set<vector<int> >S;
int route[maxn],sz;
void dfs(int v, int p) {
    used[v] = true;
    route[sz++]=v;
    for (auto i:sG[v]){
        if (i==p)continue;
        if (!used[i]) dfs(i,v);
        else{
            vector<int> va,vb;
            for(int p = sz-1;p>=0&&route[p]!=i;--p) va.push_back(route[p]);
            va.push_back(i);
            int minx = 0;
            for (int p = 1; p < va.size(); p++) if (va[p] < va[minx]) minx = p;
            for (int j = minx; j < va.size(); j++) vb.push_back(va[j]);
            for (int j = 0; j < minx; j++) vb.push_back(va[j]);
            S.insert(vb);
        }
    }
    --sz;
    used[v] = false;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 0; i < m; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        --x, --y;
        G[x].push_back(y),G[y].push_back(x);
    }
    if (m <= n) return printf("%d\n", m-n+1), 0;
    queue<int> que;
    for (int i = 0; i < n; i++) {
        if (G[i].size() == 1) cutted[i] = true,que.push(i);
    }
    while (que.size()) {
        int v = que.front(); que.pop();
        for (auto i:G[v]) {
            ++cuts[i];
            if (cuts[i] + 1 == G[i].size()) cutted[i] = true, que.push(i);
        }
    }
    int all = 0;
    memset(cmp, -1, sizeof cmp);
    for (int i = 0; i < n; i++) {
        if (G[i].size()-cuts[i]>=3){
            cmp[i] = all++;
            for (auto j:G[i]) {
                if (cmp[j]==-1 && !cutted[j] && G[j].size() - cuts[j] == 2) cmp[j] = all++, que.push(j);
            }
        }
    }
    while (que.size()) {
        int v = que.front(); que.pop();
        for (auto i:G[v]) {
            if (!cutted[i] && cmp[i] == -1) cmp[i] = cmp[v], que.push(i);
        }
    }
    for (int i = 0; i < n; i++) {
        if (cmp[i] == -1) continue;
        for (auto j:G[i]) {
            if (cmp[j] != -1 && cmp[i] != cmp[j]) sG[cmp[i]].push_back(cmp[j]);
        }
    }
    for (int i = 0; i < all; i++){
        sort(sG[i].begin(), sG[i].end());
        sG[i].erase(unique(sG[i].begin(),sG[i].end()),sG[i].end());
    }
    dfs(0,-1);
    printf("%d\n",S.size()/2);
}