Counting Simple Cycles in an Undirected Graph

Given an undirected graph with N vertices and M edges, count the number of simple cycles in the graph.

A simple cycle is defined as a closed path (starting and ending at the same vertex) that:

• Contains at least three vertices, i.e. its length is at least 3.
• Does not visit any vertex more than once (except for the starting/ending vertex).

You are given the graph in the following format:

• The first line contains two integers N and M.
• Each of the following M lines contains two integers u and v which denote an undirected edge between vertices u and v.

Note: For avoiding duplicate counting of cycles, consider only those cycles that have the minimum vertex as the starting point. In mathematical notation, if a cycle contains vertices \(v_1, v_2, \dots, v_k\) (with \(k \ge 3\)), then require that \(v_1 = \min\{v_1, v_2, \dots, v_k\}\).

Formally, if the cycle is represented as a sequence \(v_1, v_2, \dots, v_k, v_1\), then it is valid if and only if:

$$ \min\{v_1,v_2,\dots,v_k\} = v_1 \quad \text{and} \quad k \ge 3. $$

Your task is to count the total number of such simple cycles.

inputFormat

The input is given from standard input (stdin) in the following format:

N M
u1 v1
u2 v2
...
uv M

Here, the first line contains two integers N (the number of vertices) and M (the number of edges). Each of the following M lines contains two integers u and v, representing an undirected edge between the vertices u and v.

outputFormat

Output to standard output (stdout) a single integer which is the number of simple cycles in the graph.

## sample

5 6
1 2
2 3
3 4
4 1
2 4
3 5

3