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;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<ll> Size;
    UnionFind(int n = 1) {
        init(n);
    }

    void init(int n = 1) {
        par.resize(n + 1); rank.resize(n + 1); Size.resize(n + 1);
        for (int i = 0; i <= n; ++i) par[i] = i, rank[i] = 0, Size[i] = 1;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        Size[x] += Size[y];
        return true;
    }

    ll size(int x){
        return Size[root(x)];
    }
};

ll N, M;
set<int> paths[100050];
vector<int> DFSTree[100050];
bool visiting[100050];
bool visited[100050];
vector<i_i> Rest;
vector<i_i> RestPath[20];
queue<int> que;
ll ans;
vector<int> points;
int degree[100050];
int inv[100050];

void dfs(int now, int from) {
    visited[now] = true;
    for(auto to : paths[now]) {
        if(to == from) continue;
        if(visited[to]) {
            if(to > now) {
                Rest.emplace_back(now, to);
            }
        } else {
            DFSTree[now].push_back(to);
            DFSTree[to].push_back(now);
            dfs(to, now);
        }
    }
}

void f(int now) {
    int to = *paths[now].begin();
    auto itr = paths[now].lower_bound(to);
    paths[now].erase(itr);
    itr = paths[to].lower_bound(now);
    paths[to].erase(itr);
    if(paths[to].size() <= 2) que.push(to);
}

void g(int now) {
    auto itr = paths[now].begin();
    int to1 = *itr;
    itr++;
    int to2 = *itr;
    itr = paths[to1].lower_bound(to2);
    if(*itr == to2) return;
    paths[now].clear();
    itr = paths[to1].lower_bound(now);
    paths[to1].erase(itr);
    paths[to1].insert(to2);
    itr = paths[to2].lower_bound(now);
    paths[to2].erase(itr);
    paths[to2].insert(to1);
}

bool search(int now, int from, int destination, int index) {
    RestPath[index].emplace_back(now, from);
    if(now == destination) return true;
    for(auto to : DFSTree[now]) {
        if(to == from) continue;
        if(search(to, now, destination, index)) return true;
    }
    RestPath[index].pop_back();
    return false;
}

void print() {
    for(int i = 1; i <= N; i++) {
        if(paths[i].empty()) continue;
        cerr << "---" << i << "---" << endl;
        for(auto itr = paths[i].begin(); itr != paths[i].end(); itr++) {
            cerr << *itr << " ";
        }
        cerr << endl;
    }
}

void print2() {
    for(int i = 1; i <= N; i++) {
        if(DFSTree[i].empty()) continue;
        cerr << "---" << i << "---" << endl;
        for(auto itr = DFSTree[i].begin(); itr != DFSTree[i].end(); itr++) {
            cerr << *itr << " ";
        }
        cerr << endl;
    }
    cerr << "Rest" << endl;
    for(auto v : Rest) {
        cerr << v.first << " " << v.second << endl;
    }
}

void print3() {
    for(int i = 0; i < Rest.size(); i++) {
        cerr << "---" << i << "---" << endl;
        for(auto v : RestPath[i]) {
            cerr << v.first << " " << v.second << endl;
        }
    }
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    if(M == N - 1) {
        cout << 0 << endl;
        return 0;
    }
    for(int i = 1; i <= M; i++) {
        int u, v;
        cin >> u >> v;
        paths[u].insert(v);
        paths[v].insert(u);
    }
    for(int i = 1; i <= N; i++) {
        if(paths[i].size() <= 2) que.push(i);
    }
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        if(paths[now].size() == 0) continue;
        else if(paths[now].size() == 1) f(now);
        else if(paths[now].size() == 2) g(now);
    }
    //print();
    int root = 1;
    for(int i = 1; i <= N; i++) {
        if(paths[i].size()) {
            root = i;
            inv[i] = points.size();
            points.push_back(i);
        }
    }
    dfs(root, -1);
    //print2();
    for(int i = 0; i < Rest.size(); i++) {
        search(Rest[i].first, Rest[i].second, Rest[i].second, i);
    }
    //print3();
    for(int bits = 1; bits < (1 << (Rest.size())); bits++) {
        for(auto v : points) {
            degree[v] = 0;
        }
        set<i_i> st;
        for(int i = 0; i < Rest.size(); i++) {
            if(!((1 << i) & bits)) continue;
            for(auto v : RestPath[i]) {
                if(v.first > v.second) swap(v.first, v.second);
                auto itr = st.find(v);
                if(itr == st.end()) {
                    st.insert(v);
                } else {
                    st.erase(itr);
                }
            }
        }
        UnionFind uni(points.size());
        for(auto v : st) {
            degree[v.first]++;
            degree[v.second]++;
            uni.merge(inv[v.first], inv[v.second]);
        }
        int num = 0;
        int root = -1;
        for(auto v : points) {
            if(degree[v]) {
                num++;
                root = inv[v];
            }
        }
        if(root != -1) {
            if(uni.size(root) == num) {
                bool ok = true;
                for(auto v : points) {
                    if(degree[v] != 0 && degree[v] != 2) ok = false;
                }
                if(ok) {
                    ans++;
                    //cerr << bits << endl;
                }
            }
        }
    } 
    cout << ans << endl;
    return 0;
}