35108번 - 게국지

성준이의 게국지 파스타를 잊을 수 없는 성재는 오늘도 밤하늘을 보며 게를 헤고 있다. 성재를 도와 밤하늘에 게가 얼마나 있는지 알아보자.

무방향이면서, 자기 자신을 연결하는 간선이 없고 서로 다른 두 정점을 연결하는 간선이 최대 하나인 그래프(단순 그래프) $G$가 주어질 때, $G$의 부분 그래프 중 아래 그림과 같은 게자리 모양의 그래프와 동형인 것의 개수를 구해보자. $G$의 각 정점에는 $1$번부터 $N$번까지 서로 다른 번호가 매겨져 있으며, 두 부분 그래프는 이루고 있는 간선의 집합이 다르면 다른 것으로 센다.

부분 그래프와 동형의 자세한 정의는 아래 노트를 참고하라.

첫째 줄에 $G$의 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $\left(7 \le N \le M \le 2\,500;\ N^{2}\times M \le 10^{8} \right)$

그다음 줄부터 $M$개의 줄에 걸쳐 간선의 정보가 주어진다. 각 줄에 각 간선이 연결하는 두 정점의 번호 $u, v$가 공백으로 구분되어 주어진다. $(1 \le u,v \le N)$

주어진 그래프 $G$의 부분 그래프 중 문제의 그림에 주어진 게자리 모양의 그래프와 동형인 것의 개수를 출력한다.

부분 그래프

그래프 $G=(V,E)$의 부분 그래프 $H=(V',E')$는 정점 집합 $V'$에 대하여 $V' \subseteq V$를 만족하고, 간선 집합 $E'$에 대하여 $E' \subseteq \{(u,v) \in E \mid u,v \in V'\}$를 만족하는 그래프이다. 다시 말해 $G$에서 정점 일부 또는 전부를 선택하여 정점 집합을 구성하고, 그 집합에 속한 정점들 사이를 연결하는 $G$에 존재하던 간선 일부 또는 전부를 선택하여 간선 집합을 구성한 그래프이다.

그래프의 동형

두 그래프 $G,H$의 정점 집합을 각각 $V,V'$라 할 때 $G,H$가 동형이라는 것은, $G$의 임의의 두 정점 $u,v$에 대하여 $u$와 $v$를 연결하는 간선이 $G$에서 존재하는 것과 $f(u)$와 $f(v)$를 연결하는 간선이 $H$에서 존재하는 것이 필요충분조건인 일대일 함수 $f:V \rightarrow V'$가 존재한다는 것이다.