시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 96 | 35 | 23 | 38.333% |
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.
4 5 1 2 1 3 1 4 2 3 3 4
3
7 9 1 2 1 3 2 4 2 5 3 6 3 7 2 3 4 5 6 7
3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
7