사이클에 붙은 두 잎

시간 제한4초메모리 제한1024 MB

요약

그래프에서 4-사이클 하나와 그 사이클의 한 꼭짓점에 붙은 리프 두 개로 이루어진 부분그래프의 개수를 모듈로 1e9+7로 세는 문제입니다.

난이도: 어려움10점 중 8점
유형: 그래프, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

무방향 단순 그래프 $G$ 가 주어진다. 다음과 같은 모양의 부분 그래프 개수를 구하라.

서로 다른 네 정점이 하나의 4-사이클을 이룬다.
그 4-사이클의 한 정점에 서로 다른 두 정점이 잎처럼 하나씩 연결된다.

즉, 찾는 그래프는 4-사이클 하나와, 그 사이클의 같은 정점에 붙은 두 개의 pendant edge로 이루어진다. 두 부분 그래프는 선택한 간선의 집합이 다를 때만 서로 다른 것으로 센다. 원래 그래프에 선택하지 않은 간선이 더 있어도 상관없다. 답은 $10^9+7$ 로 나눈 나머지로 구한다.

입력

첫째 줄에 $G$ 의 정점 수 $N$ 과 간선 수 $M$ 이 공백으로 구분되어 주어진다. $(1 \le N, M \le 239000)$

다음 $M$ 개의 줄에는 간선으로 연결된 두 정점의 번호 $x, y$ 가 공백으로 구분되어 주어진다. $(1 \le x, y \le N)$

그래프는 단순 그래프이며, 각 정점에는 $1$ 번부터 $N$ 번까지 번호가 붙어 있다.

출력

조건을 만족하는 부분 그래프의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.

예제1

예제 1
입력
```
8 8
1 3
2 3
3 4
3 5
4 6
5 6
6 7
6 8
```
예상 출력
```
2
```