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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>

#define pi pair<ll, int>
#define fi first
#define se second
#define mp make_pair

using namespace std;

#define ll long long

const int N = (int)2e5 + 10;

int gi(){
	char c = getchar(); int ret = 0;
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)){
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret;
}

int n, m;
int edge[N][2]; bool tree[N];
int cnt = 1, lst[N], nxt[N * 2], to[N * 2];

void add(int u, int v){
	nxt[++ cnt] = lst[u]; lst[u] = cnt; to[cnt] = v;
	nxt[++ cnt] = lst[v]; lst[v] = cnt; to[cnt] = u;
}

bool vis[N]; int indx, id[N], fa[N][20], dep[N];
void dfs(int u){
	vis[u] = 1; id[u] = ++ indx;
	for (int j = lst[u]; j; j = nxt[j]){
		int v = to[j];
		if (vis[v]) continue;
		fa[v][0] = u; dep[v] = dep[u] + 1;
		dfs(v); tree[j >> 1] = 1;
	}
}
void PreLca(){
	for (int j = 1; j < 20; j ++)
		for (int i = 1; i <= n; i ++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca(int u, int v){
	if (dep[u] < dep[v]) swap(u, v);
	for (int k = dep[u] - dep[v], j = 0; k; j ++, k >>= 1)
		if (k & 1) u = fa[u][j];
	if (u == v) return u;
	for (int j = 19; j >= 0; j --)
		if (fa[u][j] != fa[v][j]) u = fa[u][j], v = fa[v][j];
	return fa[u][0];
}

int mt, nt, E[N][2], nd[N], vfa[N]; bool key[N];
bool cmp(int i, int j){return id[i] < id[j];}

int top, stk[N];
void vadd(int u, int v){vfa[v] = u;}
void BuildVT(){
	sort(nd + 1, nd + nt + 1, cmp);
	
	int _nt = nt;
	for (int i = 1; i <= nt; i ++){
		int x = nd[i];
		if (!top){stk[++ top] = x; continue;}

		int plca = lca(stk[top], x);
		while (dep[stk[top - 1]] > dep[plca] && top > 1){
			vadd(stk[top - 1], stk[top]);
			top --;
		}
		if (dep[plca] < dep[stk[top]]){
			vadd(plca, stk[top]);
			top --;
		}
		if (!top || dep[stk[top]] < dep[plca]) stk[++ top] = plca;
		stk[++ top] = x;
		if (!key[plca]) {key[plca] = 1; nd[++ _nt] = plca;}
	}
	while (top > 1){
		vadd(stk[top - 1], stk[top]);
		top --;
	}
	
	nt = _nt;
}

bool mark[N]; int deg[N];
int _cnt, _tim, _lst[N], _nxt[N], _to[N], _flag[N], _vis[N];
void _add(int u, int v){
	deg[u] ++; deg[v] ++;
	if (_flag[u] != _tim) _lst[u] = 0, _flag[u] = _tim;
	if (_flag[v] != _tim) _lst[v] = 0, _flag[v] = _tim;
	_nxt[++ _cnt] = _lst[u]; _lst[u] = _cnt; _to[_cnt] = v;
	_nxt[++ _cnt] = _lst[v]; _lst[v] = _cnt; _to[_cnt] = u;
}

void _dfs(int u){
	if (_vis[u] == _tim) return;
	_vis[u] = _tim;

	for (int j = _lst[u]; j; j = _nxt[j]){
		int v = _to[j];
	
		_dfs(v);
	}
}

void work(){
	int ans = 0;
	
	for (int s = 1; s < (1 << mt); s ++){
		for (int i = 1; i <= nt; i ++) mark[nd[i]] = 0, deg[nd[i]] = 0;
		_cnt = 0;
		_tim ++;
		
		for (int i = 1; i <= mt; i ++)
			if ((s >> (i - 1)) & 1){
				for (int p = E[i][0]; p; p = vfa[p]) mark[p] ^= 1;
				for (int p = E[i][1]; p; p = vfa[p]) mark[p] ^= 1;
				
			}

		
		for (int i = 1; i <= mt; i ++)
			if ((s >> (i - 1)) & 1){
				_add(E[i][0], E[i][1]);
			}
		
		for (int i = 1; i <= nt; i ++)
			if (mark[nd[i]] && vfa[nd[i]]) {
				_add(nd[i], vfa[nd[i]]);
			}
				
		bool ok = 1;
		for (int i = 1; i <= nt && ok; i ++)
			if (deg[nd[i]] && deg[nd[i]] != 2) ok = 0;
		
		for (int i = 1; i <= nt && ok; i ++)
			if (deg[nd[i]]) {_dfs(nd[i]); break;}

		for (int i = 1; i <= nt && ok; i ++)
			if (deg[nd[i]] && _vis[nd[i]] != _tim) ok = 0;
		
		if (ok) ans ++;  
	}
	printf("%d\n", ans);
}

int main()
{

	n = gi(); m = gi();
	for (int i = 1; i <= m; i ++){
		edge[i][0] = gi(); edge[i][1] = gi();
		add(edge[i][0], edge[i][1]);
	}
	
	dfs(1);
	PreLca();

	for (int i = 1; i <= m; i ++)
		if (!tree[i]) {
			++ mt;
			E[mt][0] = edge[i][0], E[mt][1] = edge[i][1];
			if (!key[edge[i][0]]) key[edge[i][0]] = 1, nd[++ nt] = edge[i][0];
			if (!key[edge[i][1]]) key[edge[i][1]] = 1, nd[++ nt] = edge[i][1];
			//printf("%d %d\n", E[mt][0], E[mt][1]);
		}
	
	BuildVT();
	work();
	
	return 0;
}