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> P;

int n,m;
vector<int> G[100001];
vector<int> mdfG[100001];
bool useless[100001];
int cutted[100001];
bool used[100001];
vector<int> route;
int cmp[100001];
int all=0;
int ans=0;

set<deque<int> > se;

void dfs(int v,int p){
	used[v]=true;
	route.push_back(v);
	for(int i=0;i<mdfG[v].size();i++){
		int next=mdfG[v][i];
		if(p!=next){
			if(!used[next]){
				dfs(next,v);
			}else{
				deque<int> tmp;
				int si=route.size()-1;
				while(route[si]!=next){
					tmp.push_back(route[si]);
					si--;
				}
				tmp.push_back(next);
				int best=next;
				for(int j=0;j<tmp.size();j++){
					best=min(best,tmp[j]);
				}
				while(best!=tmp[0]){
					int tp=tmp.front();
					tmp.pop_front();
					tmp.push_back(tp);
				}
				se.insert(tmp);
			}
		}
	}
	used[v]=false;
	route.pop_back();
}

int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	if(m==n-1){
		printf("0\n");
	}else if(m==n){
		printf("1\n");
	}else{
		queue<int> que;
		memset(cmp,-1,sizeof(cmp));
		for(int i=0;i<n;i++){
			if(G[i].size()==1){
				que.push(i);
				useless[i]=true;
			}
		}
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				int next=G[v][i];
				cutted[next]++;
				if(!useless[next] && G[next].size()==cutted[next]+1){
					useless[next]=true;
					que.push(next);
				}
			}
		}
		for(int i=0;i<n;i++){
			if(G[i].size()-cutted[i]>=3){
				cmp[i]=all++;
				for(int j=0;j<G[i].size();j++){
					int next=G[i][j];
					if(useless[next])continue;
					if(G[next].size()-cutted[next]<=2){
						if(cmp[next]==-1){
							cmp[next]=all++;
							que.push(next);
						}
					}
				}
			}
		}
		if(que.size()==0){
			for(int i=0;i<n;i++){
				if(!useless[i]){
					que.push(i);
					cmp[i]=0;
					all++;
					break;
				}
			}
		}
		while(que.size()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				if(cmp[G[v][i]]==-1 && !useless[G[v][i]]){
					cmp[G[v][i]]=cmp[v];
					que.push(G[v][i]);
				}
			}
		}
		for(int i=0;i<n;i++){
			if(useless[i])continue;
			for(int j=0;j<G[i].size();j++){
				if(cmp[i]!=cmp[G[i][j]] && !useless[G[i][j]])mdfG[cmp[i]].push_back(cmp[G[i][j]]);
			}
		}
		for(int i=0;i<all;i++){
			sort(mdfG[i].begin(),mdfG[i].end());
			mdfG[i].erase(unique(mdfG[i].begin(),mdfG[i].end()),mdfG[i].end());
		}
		dfs(0,-1);
		printf("%d\n",se.size()/2);
	}
	return 0;
}