Counting Crossing Edges

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.

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.

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