시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

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.

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 ui and vi. Here, you can assume that ui < vi and thus there are no self loops.

For all pairs of i and j (i ≠ j), either ui ≠ uj or vi ≠ vj 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

힌트