Counting Cycles

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

inputFormat

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.

outputFormat

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

样例

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

3