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;

using ll = long long;
using pii = pair<int, int>;
using graph = vector<set<pii>>;

void compress_graph(graph& g, int& uid) {
    const int n = g.size();
    queue<int> que;

    // remove leaves
    for(int v = 0; v < n; ++v) {
        if(g[v].size() == 1u) {
            que.push(v);
        }
    }
    while(!que.empty()) {
        const int v = que.front();
        que.pop();
        if(g[v].size() != 1u) continue;
        const auto e = *g[v].begin();
        g[v].clear();
        g[e.first].erase(make_pair(v, e.second));
        if(g[e.first].size() == 1u) {
            que.push(e.first);
        }
    }

    // constraction
    for(int v = 0; v < n; ++v) {
        if(g[v].size() == 2u) {
            que.push(v);
        }
    }
    while(!que.empty()) {
        const int v = que.front();
        que.pop();
        if(g[v].size() != 2u) continue;
        const int a = g[v].begin()->first, a_uid = g[v].begin()->second;
        const int b = next(g[v].begin())->first, b_uid = next(g[v].begin())->second;
        if(a == b) continue; // self-loop
        g[v].clear();
        g[a].erase(make_pair(v, a_uid));
        g[b].erase(make_pair(v, b_uid));
        ++uid;
        g[a].emplace(b, uid);
        g[b].emplace(a, uid);
        if(g[a].size() == 2u) {
            que.push(a);
        }
        if(g[b].size() == 2u) {
            que.push(b);
        }
    }

    map<int, int> eidx;
    graph tg(n);
    for(int v = 0; v < n; ++v) {
        for(auto& e : g[v]) {
            if(eidx.count(e.second) == 0) {
                const int id = eidx.size();
                eidx[e.second] = id;
            }
            tg[v].emplace(e.first, eidx[e.second]);
        }
    }
    g = move(tg);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin >> n >> m;
    graph g(n);
    int uid = 0;
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        g[a].emplace(b, uid);
        g[b].emplace(a, uid);
        uid += 1;
    }
    compress_graph(g, uid);

    set<ll> cycles;
    for(int s = 0; s < n; ++s) {
        if(g[s].empty()) continue;
        vector<bool> used_v(n);
        function<void(int, ll)> dfs = [&] (int v, ll used_edge) {
            used_v[v] = true;
            for(auto const& e : g[v]) {
                if(used_edge & (1LL << e.second)) continue;
                used_edge ^= 1LL << e.second;
                if(e.first == s) {
                    cycles.insert(used_edge);
                    used_edge ^= 1LL << e.second;
                    continue;
                }
                if(!used_v[e.first]) {
                    dfs(e.first, used_edge);
                }
                used_edge ^= 1LL << e.second;
            }
            used_v[v] = false;
        };
        dfs(s, 0);
    }

    cout << cycles.size() << endl;
}