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 <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

const int MN = 100100;
using P = pair<int, int>;

V<int> g[MN];

int dps[MN];
bool imp[MN], vis[MN];
int ic[MN];
void dfs(int p, int b, int ndp = 0) {
//    cout << "dfs " << p << endl;
    vis[p] = true;
    dps[p] = ndp;
    for (int d: g[p]) {
        if (d == b) continue;
        if (vis[d]) {
            if (dps[p] > dps[d]) {
//                cout << "WOW! " << p << " " << d << endl;                
                imp[p] = true;
                imp[d] = true;
            }
        } else {
            dfs(d, p, ndp+1);
            if (ic[d]) ic[p]++;
        }
    }
    if (imp[p]) ic[p]++;
}

int nv = 0;
int id[MN];
V<P> ed, rv;

void dfs2(int p, int b, int c) {
//    cout << "d2 " << p << " " << b << " " << c << endl;
    if (imp[p] || ic[p] >= 2) {
//        cout << "imp " << p << endl;
        id[p] = nv++;
        if (c != -1) ed.push_back(P(id[p], id[c]));
        c = p;
    }

    vis[p] = true;
    for (int d: g[p]) {
        if (d == b) continue;
        if (vis[d]) {
            if (dps[p] < dps[d]) rv.push_back(P(id[p], id[d]));
        } else {
            dfs2(d, p, c);
        }
    }
}


V<int> ng[MN];

int deg[MN];

int dfs3(int p, int b) {
    int sm = 0;
    for (int d: g[p]) {
        if (d == b) continue;
        sm += dfs3(d, p);
    }
    sm += deg[p];
    if (sm % 2) {
        ng[p].push_back(b);
        ng[b].push_back(p);
        deg[p]++;
        deg[b]++;
        sm++;
    }
    return sm;
}

void dfs4(int p) {
    vis[p] = true;
    for (int d: ng[p]) {
        if (vis[d]) continue;
        dfs4(d);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, -1);
/*    cout << "imp" << endl;
    for (int i = 0; i < n; i++) {
        cout << imp[i] << ", ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << ic[i] << endl;
    }*/
    fill_n(vis, MN, false);
    dfs2(0, -1, -1);
/*    cout << nv << endl;
    cout << "start tr" << endl;
    for (auto p: ed) {
        cout << p.first << ", " << p.second << endl;
    }
    cout << "start rv" << endl;
    for (auto p: rv) {
        cout << p.first << ", " << p.second << endl;
    }*/

    for (int i = 0; i < n; i++) {
        g[i].clear();
    }
    for (auto p: ed) {
        int u, v;
        tie(u, v) = p;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int ans = 0;
    int F = int(rv.size());
    for (int f = 0; f < (1<<F); f++) {
        for (int i = 0; i < nv; i++) {
            ng[i].clear();
        }
        fill_n(deg, nv, 0);
        fill_n(vis, nv, 0);
        for (int i = 0; i < F; i++) {
            if (!(f & (1<<i))) continue;
            int u, v;
            tie(u, v) = rv[i];
            ng[u].push_back(v);
            ng[v].push_back(u);
            deg[u]++; deg[v]++;
        }
        dfs3(0, -1);        
        bool ok = true;
        bool once = false;
        for (int i = 0; i < nv; i++) {
//            cout << "deg " << i << " " << deg[i] << endl;
            if (deg[i] != 0 && deg[i] != 2) {
                ok = false;
                break;
            }
            if (deg[i] == 0) continue;
            if (vis[i]) continue;
            if (once) {
                ok = false;
                break;
            }
            once = true;
            dfs4(i);
        }
        if (once && ok) {
//            cout << "ok! " << f << endl;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}