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;
const int Maxn = 1e5 + 5;
set <int> vec[Maxn];
int cnt = 0;
int vis[Maxn], a[1010][1010], mp1[Maxn], mp2[Maxn];
int dfs(int x, int y){
    if (x == y) return 1;
    int ans = 0;
    vis[x] = 1;
    for (int i = 1; i <= cnt; i++)
        if (a[x][i] && !vis[i]){
            ans += dfs(i, y);
        }
    vis[x] = 0;
    return ans;
}
int main()
{
    //freopen("004.in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    //cout << n << " " << m << endl;
    for (int i = 1; i <= m; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        //cout << x << " " << y << endl;
        vec[y].insert(x);
        vec[x].insert(y);
    }
    queue <int> q;
    for (int i = 1; i <= n; i++){
        if (vec[i].size() == 1) q.push(i);
    }
    //cout << q.size() << endl;
    while(!q.empty()){
        int x = q.front(), y = *vec[x].begin();
        //cout << x << endl;
        q.pop();
        vec[y].erase(x);
        vec[x].clear();
        if (vec[y].size() == 1){
            q.push(y);
        }
    }
    for (int i = 1; i <= n; i++){
        if (vec[i].size() == 2){
            set <int>::iterator it;
            it = vec[i].begin();
            int x = *it;
            it++;
            int y = *it;
            if (vec[x].find(y) == vec[x].end()){
                vec[x].insert(y);
                vec[y].insert(x);
                vec[x].erase(i);
                vec[y].erase(i);
                vec[i].clear();
            }
        }
    }
    for (int i = 1; i <= n; i++){
        if (!vec[i].empty()) mp1[i] = ++cnt, mp2[cnt] = i;
    }
    //cout << cnt << endl;
    for (int i = 1; i <= cnt; i++){
        int x = mp2[i];
        multiset <int>::iterator it;
        for (it = vec[x].begin(); it != vec[x].end(); it++){
            int y = *it;
            a[i][mp1[y]] = 1;
            //a[mp1[y]][i] = 1;
        }
    }
    int ans = 0;
    //cout << cnt << endl;
    for (int i = 1; i <= cnt; i++)
        for (int j = i + 1; j <= cnt; j++)
            if (a[i][j]){
            a[i][j] = a[j][i] = 0;
            ans += dfs(i, j);
    }
    cout << ans << endl;
    return 0;
}