eolymp
bolt
Try our new interface for solving problems
Problems

Number of cycles

Number of cycles

Time limit 1 second
Memory limit 122 MiB

Formally, the path in the graph - it is an alternating sequence of vertices and edges of u[1], e[1], u[2], e[2], u[3], ..., u[k], starting and ending vertex, such that any adjacent vertices and edges of her incident.

Cycle is a path, where the initial and final vertices are the same. Cycle must contain at least one edge.

A simple way is different from the usual way so that it does not contain the repeated vertices.

Simple cycle is a cycle without repeated vertices and edges.

Given an undirected graph. Calculate how many different simple cycles it contains. Note that cycles are considered equal if they bypass the same set of vertices in the same order, possibly starting with another node, or if the traversal order is reversed. For example, the cycles with traversal order 1, 2, 3, 1 and 2, 3, 1, 2 and 1, 3, 2, 1 are considered identical, and the cycles 1, 2, 3, 4, 1 and 1, 3, 4, 2, 1 are not identical, since the order of traversal of vertices is different.

Input data

The first line specifies the number of vertices n (1n10) and edges m in the graph, respectively. The following m lines contain two numbers u[i] and v[i] (1u[i], v[i]n, u[i] ≠ v[i]); each such line means that the graph contains an edge between vertices u[i] and v[i]. There is no multiple edges in the graph.

Output data

Print the number of simple cycles in a given graph.

Examples

Input example #1
3 2
1 2
2 3
Output example #1
0
Input example #2
4 5
1 2
2 3
3 4
4 1
1 3
Output example #2
3