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 <set>
#include <queue>
#include <map>
using namespace std;

class UnionFind{
private:
    vector<int> p,s;
	int cnt;
public:
	UnionFind(int N){
        init(N);
    }
	void init(int N){
		cnt = N;
		p = s = vector<int>(N+1,0);
		for(int i=0;i<=N;i++){
			p[i] = i; s[i] = 1;
		}
	}
	int find(int x){
		if(p[x]==x) return x;
		else return p[x] = find(p[x]);
	}
	void unite(int x,int y){
		x = find(x); y = find(y);
		if(x==y) return;
		if(s[x]>s[y]) swap(x,y);
		p[x] = y;
		s[y] += s[x];
		cnt--;
	}
	bool is_same_set(int x,int y) {return find(x)==find(y);}
	int size(int x) {return s[find(x)];}
	int compnents_number(){return cnt;}
};

struct edge{
    int to,id,s,t;
    bool operator<(const edge& r)const{
        return id<r.id;
    }
};

int main(){
    int N,M;
    cin >> N >> M;
//    vector<set<edge>> g(N);
    vector<set<int>> g2(N);
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        a--,b--;
//       g[a].insert({b,i,a,b});
//        g[b].insert({a,i,a,b});
        g2[a].insert(b);
        g2[b].insert(a);
    }
    
    auto deg = [&](int n){
        if(g2[n].empty()) return 0;
        return (int) g2[n].size();
    };
    
    //縮約
    auto compress = [&](){
        queue<int> Q;
        vector<int> vis(N,0);
        for(int i=0;i<N;i++) if(deg(i)==1) Q.push(i);

        //葉を順次削除
        while(!Q.empty()){
            int now = Q.front(); Q.pop();
            for(auto e:g2[now]){
                g2[e].erase(now);
                if(deg(e)==1) Q.push(e);
            }
            g2[now].clear();
        }

        //次数2の頂点をqueueに入れる
        for(int i=0;i<N;i++){
            if(deg(i)==2){
                Q.push(i);
            }
        }
        //縮約本編
        while(!Q.empty()){
            int now = Q.front(); Q.pop();
            if(deg(now)==2){
                int a = *g2[now].begin();
                g2[now].erase(a);
                int b = *g2[now].begin();
                g2[now].erase(b);
                if(!g2[a].count(b)){
                    g2[a].insert(b),g2[b].insert(a);
                    g2[a].erase(now),g2[b].erase(now);
                }else{
                    g2[now].insert(a);
                    g2[now].insert(b);
                    continue;
                }
                if(deg(a)==2){
                    vis[a] = 1;
                    Q.push(a);
                }
                if(deg(b)==2){
                    vis[b] = 1;
                    Q.push(b);
                }
            }
        }

        //グラフを再構成
        int n = 0,m = 0;
        map<int,int> nid;
        map<pair<int,int>,int> mid;
        set<pair<int,int>> exist;
        for(int i=0;i<N;i++) if(!g2[i].empty()){
            for(auto e:g2[i]){
                int a = min(e,i),b = max(e,i);
                if(a>b) swap(a,b);
                if(!nid.count(a)){
                    nid[a] = n;
                    n++;
                }
                if(!nid.count(b)){
                    nid[b] = n;
                    n++;
                }
                if(exist.count({a,b})) continue;
                exist.insert({a,b});             
            }
        }
        if(n==0) return vector<set<edge>> {};
        vector<set<edge>> res(n);
        for(auto& e:exist){
            int a = e.first,b = e.second;
            int ida = nid[a],idb = nid[b];
            res[ida].insert({idb,m,ida,idb});
            res[idb].insert({ida,m,ida,idb});
            m++;
        }
        return res;
    };

    auto calc = [](vector<set<edge>>& g){
        if(g.empty()) return 0;
        int n = g.size();
        set<edge> edges;
        for(int i=0;i<n;i++) for(auto& x:g[i]) edges.insert(x);
        set<int> tree;
        vector<int> dep(n,-1),par(n,-1),pare(n,-1);
        queue<int> Q;
        Q.push(0);
        dep[0] = 0;

        //全域木をとる
        while(!Q.empty()){
            int now = Q.front(); Q.pop();
            for(auto& x:g[now]){
                if(dep[x.to]==-1){
                    tree.insert(x.id);
                    dep[x.to] = dep[now]+1;
                    par[x.to] = now;
                    pare[x.to] = x.id;
                    Q.push(x.to);
                }
            }
        }
        
        //基本サイクルを作る
        vector<vector<edge>> base_cycles;
        int num = 0;
        for(auto& e:edges) if(!tree.count(e.id)){
            vector<edge> res;
            int a = e.s,b = e.t;
            res.push_back({0,e.id,a,b});
            if(dep[a]>dep[b]) swap(a,b);
            while(dep[a]!=dep[b]){
                res.push_back({0,pare[b],par[b],b});
                b = par[b];
            }
            while(a!=b){
                res.push_back({0,pare[a],par[a],a});
                res.push_back({0,pare[b],par[b],b});
                a = par[a],b = par[b];
            }
            num++;
            base_cycles.push_back(res);
        }

        // 基本サイクルの集合について全探索
        UnionFind uf(n);
        int ans = 0;
        for(int S=1;S<(1<<num);S++){
            uf.init(n);
            set<int> node;
            vector<int> deg(n);
            vector<int> cnt(n+20);
            for(int i=0;i<num;i++) if(S&(1<<i)){
                for(auto& e:base_cycles[i]) cnt[e.id]++;
            }
            set<int> used;
            for(int i=0;i<num;i++) if(S&(1<<i)){
                for(auto& e:base_cycles[i]) if(cnt[e.id]%2 && !used.count(e.id)){
                    uf.unite(e.s,e.t);
                    used.insert(e.id);
                    node.insert(e.s),node.insert(e.t);
                    deg[e.s]++,deg[e.t]++;
                }
            }
            
            //出てくる頂点が連結
            bool ok = (uf.size(*node.begin())==(int) node.size());
            //出てくる頂点の次数がすべて2
            for(int i=0;i<n;i++) if(node.count(i)) ok &= (deg[i]==2);
            ans += ok;
        }
        return ans;
    };
    vector<set<edge>> res = compress();
    cout << calc(res) << endl;
}