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
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int db[100005][21],dep[100005];
int n,m,cnt; vector<int>edge[100005],G[100005]; P add[20]; bool used[100005];
vector<int>all;
struct unionfind{
    int par[100005],ran[100005];
    void init(){
        rep(i,100005) par[i] = i;
    }
    void initall(){
        rep(i,all.size()) par[all[i]]=all[i],ran[all[i]]=0;
    }
    int find(int x){
        if(x==par[x]) return x;
        else return par[x] = find(par[x]);
    }
    void unite(int a,int b){
        a = find(a); b = find(b);
        if(a == b) return;
        if(ran[a]<ran[b]){
            par[a] = b;
        }
        else{
            par[b] = a;
            if(ran[a]==ran[b]) ran[a]++;
        }
    }
    bool same(int x,int y) { return find(x)==find(y); }
}uf;
void dfs(int v,int u){
    db[v][0] = u;
    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 x,int y){
    if(dep[x] > dep[y]) swap(x,y);
    rep(j,20){
        int dif = dep[y]-dep[x];
        if(!((dif>>j)&1)) continue;
        y = db[y][j];
    }
    if(x==y)return x;
    //cout<<x<<y<<endl;
    for(int j=19;j>=0;j--){
        if(db[x][j] == db[y][j]) continue;
        x = db[x][j];
        y = db[y][j];
    }
    //cout<<db[x][0]<<x<<endl;
    return db[x][0];
}
int get(int v){
    v = db[v][0];
    while(v != -1){
        if(used[v]) return v;
        v = db[v][0];
    }
    return -1;
}
int val[100005],up[100005],deg[100005],flag;
int DFS(int v,int u){
    int cc = val[v];
    rep(i,G[v].size()){
        if(G[v][i]==u) continue;
        cc += DFS(G[v][i],v);
    }
    if(cc%2 == 1){
        uf.unite(v,u);
        deg[v]++; deg[u]++;
        if(deg[v]>2 || deg[u]>2) flag = 1;
    }
    return cc;
}
 
int main(){
    scanf("%d%d",&n,&m);
    uf.init();
    rep(i,m){
        int a,b; scanf("%d%d",&a,&b);
        if(uf.same(a,b)) add[cnt++] = mp(a,b);
        else{
            edge[a].pb(b);
            edge[b].pb(a);
            uf.unite(a,b);
        }
    }
    dfs(1,-1); //cout<<db[2][0]<<endl;
    for(int j=0;j<19;j++) for(int i=1;i<=n;i++){
        if(db[i][j]==-1) db[i][j+1]=-1;
        else db[i][j+1] = db[db[i][j]][j];
        //if(db[2][0]==-1)cout<<i<<j<<endl;
    }
    vector<int>vec;
    rep(i,cnt) {vec.pb(add[i].fi); vec.pb(add[i].sc);}
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    all = vec;
    rep(i,vec.size()){
        for(int j=i+1;j<vec.size();j++){
            all.pb(lca(vec[i],vec[j]));
        //  cout <<lca(vec[i],vec[j])<<  endl;
        }
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
    int root = -1;
    rep(i,all.size()) used[all[i]] = 1;
    rep(i,all.size()){
        int v = get(all[i]);
        if(v==-1){
            root = all[i];
            up[all[i]] = -1;
        }
        else{
            G[all[i]].pb(v);
            G[v].pb(all[i]);
            up[all[i]] = v;
        }
        //cout << all[i] << v << endl;
    }
    int ret = 0;
    rep(mask,(1<<cnt)){
        uf.initall();
        rep(i,all.size()) val[all[i]] = deg[all[i]] = 0;
        rep(i,cnt){
            if(!((mask>>i)&1)) continue;
            val[add[i].fi]++;
            val[add[i].sc]++;
            val[lca(add[i].fi,add[i].sc)]-=2;
            //cout<<lca(add[i].fi,add[i].sc)<<endl;
        }
        flag = 0;
        DFS(root,-1);
        rep(i,cnt){
            if(!((mask>>i)&1)) continue;
            uf.unite(add[i].fi,add[i].sc);
            deg[add[i].fi]++;
            deg[add[i].sc]++;
            if(deg[add[i].fi]>2||deg[add[i].sc]>2) flag = 1;
        }
        int pre = -1;
        if(flag) goto fail;
        rep(i,cnt){
            if(!((mask>>i)&1)) continue;
            if(pre != -1 && pre != uf.find(add[i].fi)) goto fail; else pre = uf.find(add[i].fi);
            if(pre != -1 && pre != uf.find(add[i].sc)) goto fail; else pre = uf.find(add[i].sc);
        }
        ret++; fail:;
    }
    cout<<ret-1<<endl;
}