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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100025

struct Edge{
	Edge(){
		from = 0;
		to = 0;
	}
	void set(int arg_from,int arg_to){
		from = arg_from;
		to = arg_to;
	}
	int from,to;
};

int N;
int V,E;
int root,make_index,rest_node_index,rest_edge_index;
int parent_table[NUM],index_table[NUM];
int boss[NUM],height[NUM],count_table[100],in_num[100],depth[100];
Edge edge[NUM],make_cycle_path[20],rest_edge[100];
bool save[NUM],visited[NUM],check[50];
map<int,int> MAP[100];
vector<int> G[NUM],rest_G[100],rest_edge_group[20];


int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same_group(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	if(height[x] > height[y]){

		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void init(){

	for(int i = 0; i < N; i++){
		boss[i] = i;
		height[i] = 0;
	}
}

int makeTree(int node_id,int parent){

	int num_child = 0;

	for(int i = 0; i < G[node_id].size(); i++){

		if(G[node_id][i] == parent || visited[G[node_id][i]])continue;

		visited[G[node_id][i]] = true;
		num_child += makeTree(G[node_id][i],node_id);
	}
	if(num_child >= 2){
		save[node_id] = true;
	}

	if(save[node_id] == true || num_child != 0){
		return 1;
	}else{
		return 0;
	}
}

//木を圧縮する
void dfs(int node_id,int parent,int from){

	if(save[node_id]){

		index_table[node_id] = rest_node_index++;

		if(from != -1){

			parent_table[index_table[node_id]] = index_table[from];
			rest_edge[rest_edge_index].set(index_table[from],index_table[node_id]);
			rest_G[index_table[from]].push_back(index_table[node_id]);
			MAP[index_table[node_id]][index_table[from]] = rest_edge_index;
			rest_edge_index++;
		}
		from = node_id;
	}

	for(int i = 0; i < G[node_id].size(); i++){

		if(G[node_id][i] == parent)continue;
		dfs(G[node_id][i],node_id,from);
	}
}

void calcDepth(int node_id,int parent,int value){

	depth[node_id] = value;

	for(int i = 0; i < rest_G[node_id].size(); i++){
		if(rest_G[node_id][i] == parent)continue;

		calcDepth(rest_G[node_id][i],node_id,value+1);
	}
}


bool rangeCheck(int edge_id){
	if(edge_id < 0 || edge_id >= rest_edge_index){
		return false;
	}
	return true;
}

int main(){

	scanf("%d %d",&V,&E);

	for(int i = 0; i < V; i++){
		save[i] = false;
		visited[i] = false;
	}

	N = V;
	init();

	make_index = 0;

	for(int i = 0; i < E; i++){

		scanf("%d %d",&edge[i].from,&edge[i].to);
		edge[i].from--;
		edge[i].to--;

		if(is_same_group(edge[i].from,edge[i].to)){

			save[edge[i].from] = true;
			save[edge[i].to] = true;
			make_cycle_path[make_index++].set(edge[i].from,edge[i].to);

		}else{

			G[edge[i].from].push_back(edge[i].to);
			G[edge[i].to].push_back(edge[i].from);

			unite(edge[i].from,edge[i].to);
		}
	}

	root = 0;
	makeTree(root,-1);

	rest_node_index = 0;
	rest_edge_index = 0;
	parent_table[root] = -1;
	dfs(root,-1,-1);

	calcDepth(root,-1,-1);

	N = 0;
	for(int i = 0; i < V; i++){
		if(save[i]){
			N++;
		}
	}


	int left,right,left_id,right_id;

	for(int i = 0; i < make_index; i++){

		make_cycle_path[i].from = index_table[make_cycle_path[i].from];
		make_cycle_path[i].to = index_table[make_cycle_path[i].to];

		rest_edge[rest_edge_index].set(make_cycle_path[i].from,make_cycle_path[i].to);
		rest_edge_group[i].push_back(rest_edge_index++);

		left = make_cycle_path[i].from;
		right = make_cycle_path[i].to;

		while(true){

			if(left == right)break;

			if(depth[left] >= depth[right]){

				left_id = MAP[left][parent_table[left]];
				rest_edge_group[i].push_back(left_id);
				left = parent_table[left];

			}else{

				right_id = MAP[right][parent_table[right]];
				rest_edge_group[i].push_back(right_id);
				right = parent_table[right];
			}
		}
	}

	int POW[18];
	POW[0] = 1;
	for(int i = 1; i < 18; i++){
		POW[i] = POW[i-1]*2;
	}

	int ans = 0;

	vector<int> USE;
	bool FLG;

	int not_connect = 0;
	int num_zero = 0,num_one = 0,over_three = 0;

	for(int state = 1; state < POW[make_index]; state++){

		for(int i = 0; i < rest_edge_index; i++){ //奇数なら使う
			count_table[i] = 0;
		}

		for(int loop = 0; loop < make_index; loop++){
			if(state & (1 << loop)){
				for(int i = 0; i < rest_edge_group[loop].size(); i++){
					count_table[rest_edge_group[loop][i]]++;
				}
			}
		}

		for(int i = 0; i < N; i++){
			check[i] = false;
			in_num[i] = 0;
		}


		init();

		for(int i = 0; i < rest_edge_index; i++){
			if(count_table[i]%2 == 1){
				unite(rest_edge[i].from,rest_edge[i].to);
				check[rest_edge[i].from] = true;
				check[rest_edge[i].to] = true;
				in_num[rest_edge[i].from]++;
				in_num[rest_edge[i].to]++;
			}
		}

		USE.clear();
		FLG = true;

		for(int i = 0; i < N; i++){
			if(check[i]){
				if(in_num[i] != 2){
					if(in_num[i] == 0){
						num_zero++;
					}else if(in_num[i] == 1){
						num_one++;
					}else{
						over_three++;
					}
					FLG = false;
					break;
				}
				USE.push_back(i);
			}
		}
		if(!FLG)continue;

		for(int i = 1; i < USE.size(); i++){
			if(!is_same_group(USE[0],USE[i])){
				FLG = false;
				not_connect++;
				break;
			}
		}
		if(!FLG)continue;

		ans++;
	}

	printf("%d\n",ans);

	return 0;
}