32395번 - 4-cycle (Hard)

문제

$N$개의 정점과 $M$개의 무방향 간선으로 이루어진 단순 그래프 $G$가 주어진다. 단순 그래프란, 두 정점 사이에는 최대 1ドル$개의 간선이 존재하고, 모든 간선이 서로 다른 두 정점을 연결하는 그래프이다. $G$의 정점들은 $N$ 이하의 양의 정수들로 번호가 매겨져 있다.

그래프 $G$의 길이가 $L$인 단순 사이클은 다음 조건을 만족하는 정점의 수열 $\left( v_0,v_1,\cdots ,v_L \right)$로 정의된다.

• 모든 0ドル\leq i<L$인 $i$에 대해 $v_i$와 $v_{i+1}$을 연결하는 간선이 $G$에 존재한다.
• 모든 0ドル\leq i<j<L$인 $i,j$에 대해 $v_i\neq v_j$를 만족하고, $v_L=v_0$이다.

이때, 두 단순 사이클이 다음의 연산을 이용해 서로 변환 가능하면, 이를 동일한 사이클로 간주한다.

• 수열을 뒤집는다. 즉, $\left( v_0,v_1,\cdots ,v_L \right)$을 $\left( v_L,\cdots ,v_1,v_0 \right)$로 변경한다.
• 수열의 두 번째 원소를 맨 뒤에 추가하고 첫 번째 원소를 삭제한다. 즉, $\left( v_0,v_1,\cdots ,v_L \right)$을 $\left( v_1,\cdots ,v_L,v_1 \right)$로 변경한다.

예를 들어, 단순 사이클 $\left( 1,2,3,4,1 \right)$과 $\left( 2,1,4,3,2 \right)$는 동일한 단순 사이클이다. 주어진 그래프 $G$에서 길이가 4ドル$인 서로 다른 단순 사이클의 개수를 구해보자.

입력

첫 번째 줄에 그래프 $G$의 정점의 개수 $N(2\leq N\leq 10^5)$과 간선의 개수 $M(1\leq M\leq 10^5)$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$줄에 걸쳐 그래프 $G$의 간선을 이루는 서로 다른 두 정점 $u,v(1\leq u,v\leq N)$가 공백으로 구분되어 주어진다.

간선이 중복으로 들어오지 않음이 보장된다.

출력

그래프 $G$에서 길이가 4ドル$인 서로 다른 단순 사이클의 개수를 10ドル^9+7$로 나눈 나머지를 출력한다.

단, 10ドル^9+7$은 소수이다.

제한

힌트