31853번 - 삼각형 찾기

문제

원 위에 $N$개의 점이 있다. 각 점에는 시계방향으로 1ドル$번부터 $N$번까지의 번호가 부여되어 있다. 동현이는 이 중 두 점을 연결하는 서로 다른 선분을 $M$개 그렸다. 동현이가 그린 그림에서 세 선분으로 만들 수 있는 삼각형의 개수를 구하여라.

동현이가 점을 매우 적절하게 찍었기 때문에, 한 점에서 3ドル$개 이상의 선분이 만나지 않는다.

입력

첫 번째 줄에 정수 $N,ドル $M$이 공백으로 구분되어 주어진다.

이어서 $M$개의 줄에, 각 선분의 끝점 번호 $u,ドル $v$가 공백으로 구분되어 주어진다.

출력

세 선분으로 만들 수 있는 삼각형의 개수를 출력한다.

제한

• $ 2 \le N \le 10^9 $
• $ 1 \le M \le \min(\lfloor\frac{N}{2}\rfloor, 7\times10^3) $
• $ 1 \le u, v \le N $
• 원 위의 각 점에는 최대 하나의 선분만이 연결되어 있다.

힌트