삼각형 찾기

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

요약

원 위의 N개 점과 서로 끝점이 겹치지 않는 M개의 선분이 주어질 때, 세 선분이 모두 서로 교차하여 삼각형을 이루는 경우의 수를 구합니다.

문제

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

동현이는 점을 매우 적절하게 찍었으므로, 한 점에서 3개 이상의 선분이 만나지 않는다.

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

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

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