15339번 - 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.

입력

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 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.

제한

힌트