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 pair<int,int> P;
#define fi first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
int n,m;
vector<int>edge[100005];
vector<P>add;
struct uf{
	int par[100005];
	void init(int sz){ rep(i,sz) par[i]=i;}
	int find(int x){ if(x == par[x]) return x;
	else return par[x] = find(par[x]);}
	void unite(int x,int y){
		x = find(x); y = find(y); if(x == y) return;
		par[x] = y;
	}
}kaede,comp;
int up[100005][20],dep[100005],id[100005],Q;
void dfs(int v,int u){
	up[v][0] = u; id[v] = Q++;
	if(u == -1) dep[v] = 0; else dep[v] = dep[u]+1;
	rep(i,edge[v].size()){
		if(edge[v][i]==u) continue;
		dfs(edge[v][i],v);
	}
}
int lca(int a,int b){
	if(dep[a] > dep[b]) swap(a,b);
	int D = dep[b]-dep[a];
	rep(i,19) if(((D>>i)&1)) b = up[b][i];
	if(a == b) return a;
	for(int i=18;i>=0;i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}
bool cmp(const int&a,const int&b){
	return id[a] < id[b];
}
vector<int>vt;
vector<int>G[75];
int N;
int val[75];
int cnt[75][75];
int dist[75][75];
void dfs2(int v,int u,int ori,int len){
	dist[ori][v] = len;
	rep(i,G[v].size()){
		if(G[v][i] == u) continue;
		dfs2(G[v][i],v,ori,len+1);
	}
}
int rev[100005];
int main(){
	scanf("%d%d",&n,&m);
	kaede.init(100005);
	rep(i,m){
		int a,b; scanf("%d%d",&a,&b);
		if(kaede.find(a) == kaede.find(b)){
			add.pb(P(a,b));
			vt.pb(a); vt.pb(b);
		}
		else {
			kaede.unite(a,b); edge[a].pb(b); edge[b].pb(a);
		}
	}
	dfs(1,-1);
	rep(j,18) repn(i,n){
		if(up[i][j] == -1) up[i][j+1] = -1;
		else up[i][j+1] = up[up[i][j]][j];
	}
	sort(vt.begin(),vt.end(),cmp);
	vt.erase(unique(vt.begin(),vt.end()),vt.end());
	int sz = vt.size();
	for(int i=1;i<sz;i++){
		int x = vt[i-1], y = vt[i];
		vt.pb(lca(x,y));
	}
	sort(vt.begin(),vt.end(),cmp);
	vt.erase(unique(vt.begin(),vt.end()),vt.end());
	rep(i,vt.size()) rev[vt[i]] = i;
	N = vt.size();
	for(int i=1;i<N;i++){
		int a = vt[i-1], b = vt[i];
		int c = lca(a,b);
		c = rev[c];
		G[c].pb(i); G[i].pb(c);
	}
	rep(i,add.size()){
		add[i].fi = rev[add[i].fi];
		add[i].sc = rev[add[i].sc];
	}
	rep(i,N) dfs2(i,-1,i,0);
	int M = add.size();
	int ans = 0;
	for(int mask=1;mask<(1<<M);mask++){
		memset(val,0,sizeof(val));
		memset(cnt,0,sizeof(cnt));
		comp.init(75);
		int deg[75] = {};
		rep(i,M){
			if(((mask>>i)&1)){
				int a = add[i].fi, b = add[i].sc;
				deg[a]++; deg[b]++; comp.unite(a,b);
				while(a != b){
					int to;
					rep(i,G[a].size()){
						if(dist[b][a] == dist[b][G[a][i]]+1){
							cnt[min(a,G[a][i])][max(a,G[a][i])] ^= 1;
							//cout << a << G[a][i] << endl;
							a = G[a][i]; break;
						}
					}
				}
			}
		}
		set<int>S;
		rep(i,N) rep(j,G[i].size()) if(i < G[i][j]){
			if(cnt[i][G[i][j]]){
				deg[i]++; deg[G[i][j]]++;
				comp.unite(i,G[i][j]);
			}
		}
		rep(i,N) if(deg[i]) S.insert(i);
		int fail = 0;
		rep(i,N){
			if(deg[i] != 0 && deg[i] != 2) fail = 1;
		}
		if(S.empty()) fail = 1;
		else{
			int B = comp.find(*S.begin());
			for(auto A:S){
				if(comp.find(A) != B) fail = 1;
			}
		}
		if(!fail) ans++;
	}
	cout << ans << endl;
}