정점이 \(n\) 개, 간선이 \(m\) 개인 방향 그래프가 주어진다. 이 그래프에 들어 있는 단순 사이클의 개수를 세어라.

단순 사이클이란 같은 정점을 두 번 이상 지나지 않으면서, 간선 방향을 따라 어떤 정점에서 출발해 다시 그 정점으로 돌아오는 닫힌 경로를 말한다. 사이클의 길이(정점 수)는 \(2\) 이상이어야 한다.

두 사이클은, 같은 정점 집합을 같은 순환 순서·같은 방향으로 도는 경우에만 같은 것으로 본다. 예를 들어 \(1 \to 2 \to 3 \to 1\) 과 \(2 \to 3 \to 1 \to 2\) 는 같은 사이클이지만, 방향이 반대인 \(1 \to 3 \to 2 \to 1\) 은 (간선이 모두 존재한다면) 다른 사이클이다.

그래프에는 셀프 루프와 중복 간선이 없다.

\(1 \le n \le 18\)

\(0 \le m \le n(n-1)\)

셀프 루프와 중복 간선은 없다.

첫째 줄에 정점의 수 \(n\) 과 간선의 수 \(m\) 이 공백으로 구분되어 주어진다.

다음 \(m\) 개의 줄에 각각 두 정수 \(u\), \(v\) 가 주어지며, \(u\) 에서 \(v\) 로 가는 방향 간선을 뜻한다 (\(1 \le u, v \le n\), \(u \ne v\)).

그래프에 존재하는 단순 방향 사이클의 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original