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>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

void bridge(const vector<vi> &g, vector<pi> &hasi){
	int n = g.size(), cnt = 0;
	vi num(n, -1), low(n, inf);
	/*
	function<void(int,int)> rec = [&](int c, int p){
		num[c] = low[c] = cnt++;
		for(int i : g[c]) if(p != i){
			if(num[i] >= 0) low[c] = min(low[c], num[i]);
			else{
				rec(i, c);
				low[c] = min(low[c], low[i]);
				if(low[i] > num[c]) hasi.emplace_back(c, i);
			}
		}
	};
	rec(0, 0);
	*/
	//stackに書き換え。やりたくねーーーー
	
	stack<tuple<int,int,int>> stk;
	stk.emplace(0, 0, -1);
	while(stk.size()){
		int c, p, i;
		LABEL1:
		tie(c, p, i) = stk.top(); stk.pop();
		if(i >= 0) goto LABEL2;
		
		num[c] = low[c] = cnt++;
		for(i = 0; i < g[c].size(); i++) if(p != g[c][i]){
			if(num[g[c][i]] >= 0) low[c] = min(low[c], num[g[c][i]]);
			else{
				stk.emplace(c, p, i);
				stk.emplace(g[c][i], c, -1);
				goto LABEL1;
				LABEL2:
				
				low[c] = min(low[c], low[g[c][i]]);
				if(low[g[c][i]] > num[c]) hasi.emplace_back(c, g[c][i]);
			}
		}
	}
}

vector<vector<pi>> in(vector<pi> &es){
	int n, m; cin >> n >> m;
	vi p(n, -1);
	
	function<int(int)> root = [&](int x){
		if(p[x] < 0) return x;
		return p[x] = root(p[x]);
	};
	auto merge = [&](int a, int b){
		a = root(a); b = root(b);
		if(a == b) return 0;
		p[b] = a;
		return 1;
	};
	vector<vi> e(n + 1);
	vector<bool> mark(n + 1);
	rep(i, m){
		int a, b; cin >> a >> b; a--; b--;
		int loop_edge = !merge(a, b);
		if(loop_edge){
			es.emplace_back(a, b);
			mark[a] = mark[b] = 1;
		}
		else{
			e[a].pb(b);
			e[b].pb(a);
		}
	}
	//まず橋は全部消してよい
	{
		vector<vi> e2 = e;
		vector<pi> hasi;
		for(pi p : es){
			e2[p.first].pb(p.second);
			e2[p.second].pb(p.first);
		}
		bridge(e2, hasi);
		set<pi> hasis;
		for(auto p : hasi){
			hasis.insert(p);
			hasis.emplace(p.second, p.first);
		}
		//dbg(hasis.size());
		rep(i, n){
			vi ee;
			for(int j : e[i]) if(!hasis.count(pi(i, j))) ee.pb(j);
			e[i] = ee;
		}
	}
	
	rep(i, n) if(e[i].size() > 2) mark[i] = 1;
	
	//縮約
	//ここもgotoで再帰書き直しかよ！！ふざけんな！！！
	vector<bool> vis(n);
	rep(i, n) if(!vis[n] && mark[i]){
		vi v;
		stack<tuple<int,int,int,int>> stk;
		stk.emplace(i, i, 0, -1);
		while(stk.size()){
			int c, p, cnt, i;
			LABEL1:
			tie(c, p, cnt, i) = stk.top(); stk.pop();
			if(i >= 0) goto LABEL2;
			
			if(!mark[c]) cnt++;
			else cnt = 0;
			
			v.pb(c);
			vis[c] = 1;
			for(i = 0; i < e[c].size(); i++) if(e[c][i] != p){
				
				if(mark[e[c][i]] && cnt > 1){
					//dbg(v.size());
					
					int x = v[v.size() - cnt];
					for(vi::iterator j = e[x].begin(); j != e[x].end(); ++j) if(*j == v[v.size() - cnt + 1]){
						e[x].erase(j);
						break;
					}
					for(vi::iterator j = e[e[c][i]].begin(); j != e[e[c][i]].end(); ++j) if(*j == c){
						e[e[c][i]].erase(j);
						break;
					}
					e[x].pb(e[c][i]);
					e[e[c][i]].pb(x);
				}
				if(!vis[e[c][i]]){
					stk.emplace(c, p, cnt, i);
					stk.emplace(e[c][i], c, cnt, -1);
					goto LABEL1;
					LABEL2:;
				}
				if(!mark[c]) break;
			}
			v.pop_back();
		}
	}
	
	//rep(i, n) dbg(i, e[i]);
	
	//n番の頂点からたどれる頂点だけ取り出して番号を圧縮
	int N = 0;
	vi to(n, -1);
	function<void(int)> dfs = [&](int c){
		to[c] = N++;
		for(auto i : e[c]) if(to[i] < 0) dfs(i);
	};
	rep(i, n) if(to[i] < 0 && mark[i]) dfs(i);
	
	vector<vector<pi>> g(N);
	vector<pi> es2;
	rep(i, n) if(to[i] >= 0) for(int j : e[i]) if(to[j] >= 0){
		g[to[i]].emplace_back(to[j], 0);
	}
	for(const auto &i : es){
		assert(to[i.first] >= 0 && to[i.second] >= 0);
		//while(!(to[i.first] >= 0 && to[i.second] >= 0));
		//i = pi(to[i.first], to[i.second]);
		es2.emplace_back(to[i.first], to[i.second]);
	}
	es = es2;
	//dbg(N);dbg(es);
	
	return g;
}

void run(){
	cin.tie(0); cin.sync_with_stdio(0);
	vector<pi> es;
	vector<vector<pi>> g = in(es);
	
	//ループ列挙
	vector<bool> vis(g.size());
	vector<pi*> stk;
	function<int(int,int,int,int)> find_loop = [&](int c, int s, int t, int id){
		vis[c] = 1;
		if(c == t){
			for(int i = (int)stk.size() - 1; i >= 0; i--) stk[i]->second |= 1 << id;
			return 1;
		}
		for(auto &i : g[c]){
			if(vis[i.first]) continue;
			stk.pb(&i);
			if(find_loop(i.first, s, t, id)) return 1;
			stk.pop_back();
		}
		return 0;
	};
	int m = es.size();
	rep(i, m){
		fill(all(vis), 0);
		stk.clear();
		int a = es[i].first, b = es[i].second;
		int res = find_loop(a, a, b, i);
		while(!res);
	}
	rep(i, m){
		int a = es[i].first, b = es[i].second;
		g[a].emplace_back(b, 1 << i);
		g[b].emplace_back(a, 1 << i);
	}
	//rep(i, g.size()) dbg(i, g[i]);
	
	//逆辺にフラグ立てるの忘れてた
	map<pi, pi*> tbl;
	rep(i, g.size()) for(auto &j : g[i]) tbl[pi(i, j.first)] = &j;
	rep(i, g.size()) for(auto &j : g[i]){
		int b = j.second | tbl[pi(j.first, i)]->second;
		//dbg(i, j.first, b, j.second, *tbl[pi(j.first, i)]);
		j.second = tbl[pi(j.first, i)]->second = b;
		
	}
	//rep(i, g.size()) dbg(i, g[i]);
	
	//数える
	//dfsして連結かつループで誘導されるグラフの頂点が全て次数が2
	function<int(int,int)> dfs = [&](int c, int bit){
		vis[c] = 1;
		int deg = 0, res = 1;
		for(auto i : g[c]){
			if(__builtin_popcount(i.second & bit) % 2 == 0) continue;
			if(!vis[i.first]) res &= dfs(i.first, bit);
			deg++;
		}
		if(deg != 2) return 0;
		return res;
	};
	int ans = 0;
	rep(i, 1 << m){
		fill(all(vis), 0);
		int v = -1;
		rep(j, g.size()) for(pi k : g[j]) if(__builtin_popcount(k.second & i) % 2){
			v = j;
			break;
		}
		//dbg(v);
		
		if(v < 0 || !dfs(v, i)) continue;
		rep(j, g.size()){
			bool f = 0;
			for(pi k : g[j]) if(__builtin_popcount(k.second & i) % 2){
				f = 1;
				break;
			}
			if(f != vis[j]) goto FAIL;
		}
		ans++;
		FAIL:;
	}
	cout << ans << endl;
}

int main(){
	run();
	return 0;
}