Counting Crossing Edges

Interview

Time limit2sMemory limit128 MB

Summary

Given M cross edges between two labeled vertex sets of size N, count how many unordered pairs of edges cross each other.

Level: Medium5 of 10
Topics: Sorting, Divide and conquer, Prefix sum, Array
Solved: No attempts yet

Problem

There are two vertex sets, left and right, each containing vertices numbered from 1 through N. M edges connect vertices across the two sets.

For two distinct edges (a1, b1) and (a2, b2), the two edges cross if a1 < a2 and b1 > b2, or if a1 > a2 and b1 < b2.

Count how many unordered pairs of the given edges cross.

Input

The first line contains N, the vertex-number range, and M, the number of edges. The constraints are 1 <= N <= 2,000 and 1 <= M <= N*(N-1)/2.

Each of the next M lines contains two integers i and j, describing an edge between vertex i in the left set and vertex j in the right set. No edge is given more than once.

Output

Print the total number of crossing pairs among the given edges.

Examples1

Example 1
Input
```
5 6
1 5
2 2
3 2
4 3
5 1
5 3
```
Expected output
```
8
```