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.

입력 형식

The input consists of a single test case of the following format.</p>

n m
u1 v1
.
.
.
um vm

A test case represents an undirected graph G.

The first line shows the number of vertices n (3 ≤ n ≤ 100 000) and the number of edges m (n − 1 ≤ m ≤ 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 ui and vi 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 ≠ j), either u_i ≠ u_j or v_i ≠ v_j holds. In other words, there are no parallel edges.

You can assume that G is connected.

출력 형식

The output should be a line containing a single number that is the number of simple cycles in the graph.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

7 9
1 2
1 3
2 4
2 5
3 6
3 7
2 3
4 5
6 7

예제 출력 2

3

예제 입력 3

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

예제 출력 3

7