Crossing Diagonals

You are given a regular polygon with $n$ vertices, and $m$ of its diagonals have been selected. Count how many pairs of the selected diagonals cross each other. Two diagonals cross when they intersect strictly inside the polygon; two diagonals that share only a common vertex (endpoint) are not counted as crossing.

Write a program that:

• reads the description of the polygon and the selected diagonals from standard input,
• counts the number of pairs of diagonals that cross,
• writes that number to standard output.

The first line contains two integers $n$ and $m$, separated by a single space, where $n$ is the number of vertices of the polygon and $m$ is the number of selected diagonals ($4 \le n \le 1\,000\,000$, $2 \le m \le 10\,000\,000$).

Each of the next $m$ lines describes one diagonal. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), separated by a single space, denoting the diagonal that joins vertex $a_i$ with vertex $b_i$. The vertices of the polygon are numbered from $1$ to $n$ in counter-clockwise order.

You may assume that every pair of numbers describes a valid diagonal (never a single vertex, and never an edge of the polygon), and that all diagonals in the input are distinct.

Print a single integer: the number of pairs of selected diagonals that cross. If no pair of diagonals crosses, print $0$.

In the picture above, the solid lines and the dashed lines show two different sets of selected diagonals on the same polygon.