시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5862220458219.550%

문제

각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다.

  • 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 < A2, B1 > B2 또는 A1 > A2, B1 < B2를 만족한다면 두 간선을 교차한다고 한다.

예를 들어 위에 예에서 (3, 2)는 (1, 5)와 (5, 1)과 교차한다. 이 문제를 해결하는 프로그램을 작성하시오.

입력

첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. 중복되는 간선이 입력으로 주어지지 않는다.

출력

입력에서 주어진 간선이 교차하는 총 개수를 출력한다.

예제 입력 1

5 6
1 5
2 2
3 2
4 3
5 1
5 3

예제 출력 1

8

출처

  • 문제를 번역한 사람: author6