Split the SSHS 2

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

요약

무향 연결 그래프에서 세 정점을 골라 그 정점들에 연결된 간선을 모두 지웠을 때 그래프가 분리되는 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 그래프, DFS, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

서울의 명소 서울과학고등학교에는 1부터 $N$ 까지의 번호가 매겨진 건물이 $M$ 개의 길로 연결되어 있다. 길은 서로 다른 두 건물을 양방향으로 연결하고, 두 건물을 잇는 길은 최대 하나이다. 또한 서울과학고등학교는 어떤 두 건물 사이도 연결된 길만을 이용하여 오갈 수 있다. 정후는 서울과학고등학교를 여러 조각으로 분열시킨 후 서울과학고등학교를 지배할 계획을 세우고 있다. 구체적인 계획은 다음과 같다.

서로 다른 세 건물 $a, b, c$ 를 고른다.
건물 $a, b, c$ 중 서로 다른 두 건물을 연결하고 있는 길이 있다면, 그러한 길들을 모두 막아서 더 이상 사용할 수 없도록 한다.
남아있는 길만을 이용하여 서로 이동할 수 없는 두 건물이 있다면 정후의 계획이 성공한 것이다.

정후의 계획이 성공하기 위해 골라야 할 세 건물의 집합 $\\{ a, b, c\\}$ 의 가짓수를 구해 주자.

입력

첫 번째 줄에 $N$ , $M$ 이 주어진다.

두 번째 줄부터 $M$ 개의 줄에 걸쳐 각 줄에 서울과학고등학교의 길이 잇는 두 건물의 번호가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 정답을 출력한다.

제한

$3 \leq N \leq 200\\,000$
$N-1 \leq M \leq 200\\,000$
어떤 두 건물 사이도 연결된 길만을 이용하여 오갈 수 있다.
길이 연결하는 두 건물은 서로 다르다.
두 건물을 잇는 길은 최대 하나이다.
주어지는 모든 수는 정수이다.

예제2

예제 1
입력
```
4 5
1 2
1 3
2 3
2 4
3 4
```
예상 출력
```
2
```
예제 2
입력
```
5 4
1 2
2 3
3 4
4 5
```
예상 출력
```
9
```