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 <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100020

/* UnionFind */

struct UnionFind{
  vector<int> data, tree_size;
  UnionFind(int s):data(s,-1),tree_size(s,1) {}
  
  int root(int x){
    if(data[x]==-1) return x;
    return data[x]=root(data[x]);
  }
  
  bool set(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y) return false;
    data[y]=x;
    tree_size[x] += tree_size[y];
    tree_size[y] = 0;
    return true;
  }
  
  bool check(int x,int y){
    x=root(x);
    y=root(y);
    return x==y;
  }
  
  int size(int x){
    return tree_size[root(x)];
  }
  
};


vector<pair<int,int> > G[SIZE];
bool tree[SIZE];
int u[SIZE], v[SIZE];
int visited[SIZE];
int depth[SIZE];

bool dfs(int now, int back = -1, int d = 0){
  
  if(visited[now]) return false;
  visited[now] = true;

  depth[now] = d;

  for(int i=0;i<G[now].size();i++){
    if(G[now][i].first != back)
      tree[G[now][i].second] = dfs(G[now][i].first, now, d+1);
  }

  return true;
}

vector<int> cprG[SIZE];

int cprID[SIZE];
int cprSize = 0;

int compress(int now, int back = -1){
  bool need = false;
  int res = -1;
  vector<int> child;
  
  for(int i=0;i<G[now].size();i++){
    if(G[now][i].first != back && tree[G[now][i].second]){
      int p = compress(G[now][i].first, now);

      if(p != -1){
        child.push_back(p);
      }
    }

    need |= !tree[G[now][i].second];
  }

  need |= back == -1;
  need |= child.size() >= 2;
  
  if(need){
    for(int i=0;i<child.size();i++){
      int p = now;
      int q = child[i];
      cprG[p].push_back(q);
      cprG[q].push_back(p);
      cprSize++;
    }
    res = now;

    cprID[now] = cprSize++;
  }

  if(!need && child.size() == 1){
    res = child[0];
  }
  
  return res;
}

void cprdfs(int *sum, vector<pair<int,int> > &vec, int now, int back = -1){

  for(int i=0;i<cprG[now].size();i++){
    if(cprG[now][i] == back) continue;
    
    cprdfs(sum, vec, cprG[now][i], now);

    sum[cprID[now]] += sum[cprID[cprG[now][i]]];
    
    if(sum[cprID[cprG[now][i]]]%2){
      vec.push_back({now, cprG[now][i]});
    }
  }
  
}

int main(){
  int n, m;
  
  scanf("%d%d",&n,&m);

  for(int i=0;i<m;i++){
    scanf("%d%d",u+i,v+i);
    u[i]--; v[i]--;
    G[u[i]].push_back({v[i],i});
    G[v[i]].push_back({u[i],i});
  }

  dfs(0);
  
  compress(0);

  //debug(cprSize);
  
  pair<int,int> addEdge[17];
  int s = 0;
  
  for(int i=0;i<m;i++){
    if(!tree[i]){
      if(depth[u[i]] > depth[v[i]]) swap(u[i], v[i]);
      addEdge[s++] = {u[i], v[i]};
    }
  }

  int ans = 0;
  int sum[SIZE] = {};
  int inedge[SIZE] = {};

  for(int i=1;i<(1<<s);i++){
    vector<pair<int,int> > vec;

    for(int i=0;i<cprSize;i++){
      sum[i] = inedge[i] = 0;
    }
    
    for(int j=0;j<s;j++){
      if(i & (1 << j)){
        sum[cprID[addEdge[j].first]]--;
        sum[cprID[addEdge[j].second]]++;
        vec.push_back({addEdge[j].first, addEdge[j].second});
      }
    }

    cprdfs(sum, vec, 0);

    //debug(vec.size());

    bool flag = true;
    UnionFind uf(cprSize);
    int group = 0;
    
    //入次数2
    for(int j=0;j<vec.size();j++){
      inedge[cprID[vec[j].first]]++;
      inedge[cprID[vec[j].second]]++;
      group += uf.set(cprID[vec[j].first], cprID[vec[j].second]);
    }
    
    for(int j=0;j<vec.size();j++){
      flag &= inedge[cprID[vec[j].first]] == 2;
      flag &= inedge[cprID[vec[j].second]] == 2;
    }
    
    //連結
    flag &= group == vec.size() - 1;
    ans += flag;
  }

  printf("%d\n",ans);
  
  return 0;
}