SSB 토너먼트

시간 제한2초메모리 제한512 MB

요약

주어진 친분 그래프에서 세 명이 모두 아는 사이인 삼각형의 수와 세 명 모두 모르는 사이인 독립 삼중쌍의 수를 세어 합한다.

난이도: 보통10점 중 6점
유형: 그래프, 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Aditya는 신작 게임 Super Slam Battle (SSB)로 큰 토너먼트를 열려고 한다. 그런데 고전적인 $1$ 대 $1$ 경기가 아니라, 모든 경기에 $3$ 명의 선수가 참가하도록 해서 경기에 혼란을 좀 더하고 싶어 한다. 그는 토너먼트에 참가할 $n$ 명을 모집했다. 참가자 중 일부는 전에 서로 알고 지낸 사이라서, 같은 경기에 있으면 경쟁 규칙 세트를 쓸 때만 서로 경기를 한다. 두 참가자가 전에 서로 모르는 사이라면, 캐주얼 규칙 세트를 쓸 때만 서로 경기를 한다. 따라서 Aditya는 $3$ 명의 참가자 사이의 경기를 열려면 그들이 모두 전에 서로 알고 지낸 사이라거나, 모두 전에 서로 모르는 사이라야 한다는 것을 깨달았다. 토너먼트 전에 서로 알고 지낸 $k$ 쌍이 주어질 때, Aditya가 열 수 있는 경기의 총 개수를 구하시오.

입력

첫째 줄에는 공백으로 구분된 두 정수 $n$ 과 $k$ 가 주어진다. $n$ 은 토너먼트에 참가하는 사람 수, $k$ 는 토너먼트 전에 서로 알고 지낸 사람 쌍의 수이며, $3 \leq n \leq 10^6$ , $1 \leq k \leq 10^6$ 이다. 다음 $k$ 개 줄에는 각각 공백으로 구분된 두 정수 $u$ 와 $v$ ( $1 \leq u,v \leq n$ , $u \neq v$ )가 주어지며, 이는 두 사람 $u$ 와 $v$ 가 토너먼트 전에 서로 알고 지낸 사이라는 뜻이다. 각 쌍 $(u, v)$ 는 최대 한 번만 주어진다.

출력

Aditya가 열 수 있는 서로 다른 $3$ 명의 경기 수를 출력한다.

예제2

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