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 ll;
const int maxn = 1e5 + 20;
int n, m;
std::set<int> G[maxn], P[maxn];

int fa[maxn];
int getFa(int u) {
    if(fa[u] == u)
        return u;
    return fa[u] = getFa(fa[u]);
}

void uniFa(int u, int v) {
    u = getFa(u);
    v = getFa(v);
    fa[u] = v;
}

int epl;

void addEdge(int u, int v) {
    G[u].insert(v);
    G[v].insert(u);
}
void delEdge(int u, int v) {
    G[u].erase(v);
    G[v].erase(u);
}

bool ins[maxn];
int labl, lab[maxn], S[maxn];

std::vector<int> hash(int l, int r) {
    std::vector<int> v;
    int mn = 0, mi = -1;
    for(int i = l; i < r; ++i) {
        if(S[i] > mn) {
            mi = i;
            mn = S[i];
        }
    }
    for(int i = mi; i < r; ++i) {
        v.push_back(S[i]);
    }
    for(int i = l; i < mi; ++i) {
        v.push_back(S[i]);
    }
    return v;
}

std::set<std::vector<int> > loop;

void dfs(int u, int f) {
    lab[u] = labl;
    ins[u] = true;
    S[labl] = u;
    ++labl;

    for(const auto &v : G[u])
    if(v != f) {
        if(ins[v]) {
            loop.insert(hash(lab[v], labl));
        } else {
            dfs(v, u);
        }
    }

    ins[u] = false;
    --labl;
}

int main() {
    scanf("%d%d", &n, &m);
    if(n <= 1 || m <= n - 1) {
        puts("0");
        return 0;
    }
    if(m == n) {
        puts("1");
        return 0;
    }
    for(int i = 0, u, v; i < m; ++i) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    std::queue<int> q;
    for(int i = 1; i <= n; ++i) {
        if(G[i].size() == 1)
            q.push(i);
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        // fprintf(stderr, "%d\n", u);
        int v = *G[u].begin();
        delEdge(u, v);
        if(G[v].size() == 1)
            q.push(v);
    }
    for(int i = 1; i <= n; ++i) {
        if(G[i].size() == 2) {
            auto iter = G[i].begin();
            int u = *iter++, v = *iter++;
            if(G[u].size() == 2 && G[u].find(v) == G[u].end() && G[v].size() == 2 && G[v].find(u) == G[v].end()) {
                delEdge(u, i);
                delEdge(v, i);
                addEdge(u, v);
                // fprintf(stderr, "u, i, v %d %d %d\n", u, i, v);
            }
        }
    }
    // fprintf(stderr, "aA\n");
    // for(int i = 1; i <= n; ++i) {
    //     int u = getFa(i);
    //     for(const auto &vp : G[i]) {
    //         int v = getFa(vp);
    //         if(u == v)
    //             continue;
    //         P[u].insert(v);
    //         fprintf(stderr, "%d %d\n", u, v);
    //     }
    // }
    for(int i = 1; i <= n; ++i) {
        int u = getFa(i);
        if(!G[u].empty()) {
            dfs(u, 0);
            break;
        }
    }
    printf("%d\n", loop.size() / 2);
    return 0;
}