교차 간선 개수 세기

왼쪽 집합과 오른쪽 집합에 각각 1부터 N까지 번호가 붙은 정점이 N개씩 있다. 두 집합 사이를 잇는 M개의 간선이 주어진다.

서로 다른 두 간선 (a1, b1), (a2, b2)에 대해 a1 < a2이고 b1 > b2이거나, a1 > a2이고 b1 < b2이면 두 간선은 교차한다고 한다.

주어진 모든 간선 쌍 중 교차하는 쌍의 개수를 구하라.

첫째 줄에 정점 번호의 범위 N과 간선 수 M이 주어진다. 1 <= N <= 2,000, 1 <= M <= N*(N-1)/2이다.

다음 M개 줄에는 간선 하나를 나타내는 두 정수 i와 j가 주어진다. 이는 왼쪽 집합의 i번 정점과 오른쪽 집합의 j번 정점이 연결되어 있음을 뜻한다. 같은 간선은 두 번 주어지지 않는다.

주어진 간선 쌍 중 교차하는 쌍의 총개수를 출력한다.