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<int,int> P;
const int N=1e5+5;
int n,m,k,sb[N],odr[N],deg[N],co,par[N],ans,s;
bool use[N],euse[20],vuse[N],isans;
vector<int> v,g[N],g2[N];
vector<P> edge;
int ufp[N];
int fi(int x)
{
    if(ufp[x]==x) return x;
    return ufp[x]=fi(ufp[x]);
}
void un(int x,int y)
{
    x=fi(x); y=fi(y);
    if(x!=y) ufp[y]=x;
}
//dfs 트리 만들면서 back edge 저장
void dfs(int x,int p)
{
    odr[x]=++co;
    for(auto &it : g[x]){
        if(it==p) continue;
        if(odr[it]&&odr[it]<odr[x]){
            edge.push_back(P(x,it));
            use[x]=use[it]=true;
            continue;
        }
        if(odr[it]) continue;
        dfs(it,x);
    }
}
// dfs 트리 tree edge들 압축 후 저장
void dfs_dcp(int x,int p)
{
    odr[x]=1;
    vector<int> v;
    sb[x]=use[x];
    for(auto &it : g[x]){
        if(it==p) continue;
        if(odr[it])
            continue;
        dfs_dcp(it,x);
        if(sb[it]) v.push_back(it);
        sb[x]+=sb[it];
    }
    if(v.size()>=2) use[x]=true;
}
void dfs_dcp2(int x,int p,int pp)
{
    odr[x]=1;
    if(use[x]){
        if(pp){
            g2[pp].push_back(x);
            par[x]=pp;
        }
        v.push_back(x);
        pp=x;
    }
    for(auto &it : g[x]){
        if(it==p) continue;
        if(odr[it])
            continue;
        dfs_dcp2(it,x,pp);
    }
}
void dfs_chk(int x)
{
    for(auto &it : g2[x])
        dfs_chk(it);
    if(deg[x]>=3) isans=false;
    if(deg[x]==1){
        if(x==1) isans=false;
        else{
            deg[x]++;
            deg[par[x]]++;
            un(x,par[x]);
            vuse[x]=vuse[par[x]]=true;
        }
    }
}
void backtrack(int curr)
{
    if(curr==k){
        for(auto &it : v) deg[it]=vuse[it]=0;
        for(auto &it : v) ufp[it]=it;
        for(int i=0;i<k;i++) if(euse[i]){
            deg[edge[i].first]++;
            deg[edge[i].second]++;
            vuse[edge[i].first]=vuse[edge[i].second]=true;
            un(edge[i].first,edge[i].second);
        }
        isans=true;
        dfs_chk(1);
        int cv=0;
        for(auto &it : v) if(it==fi(it)&&vuse[it]) cv++;
        if(isans&&cv==1) ans++;
        return;
    }
    euse[curr]=1;
    backtrack(curr+1);
    euse[curr]=0;
    backtrack(curr+1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int u,v,i=1;i<=m;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(m==n-1){
        cout<<0<<endl;
        return 0;
    }
    dfs(1,0);
    use[1]=true;
    k=edge.size();/*
    cout<<k<<endl;
    for(auto &it : edge)
        cout<<it.first<<" "<<it.second<<endl;*/
    for(int i=1;i<=n;i++) odr[i]=0;
    dfs_dcp(1,0);
    for(int i=1;i<=n;i++) odr[i]=0;
    dfs_dcp2(1,0,0);
    /*
    for(int i=1;i<=n;i++)
        cout<<i<<" : "<<use[i]<<endl;
    cout<<v.size()<<endl;
    for(auto &it : v)
        cout<<it<<" ";
    cout<<endl;*/
    backtrack(0);
    cout<<ans<<endl;
    return 0;
}