You are given an undirected, complete graph \(G\) that contains \(N\) vertices. Each edge is colored in either white or black. You are required to determine the number of triplets \((i,j,k)\) \((1 \le i < j < k \le N)\) of vertices such that the edges \((i,j), (j,k), (i,k)\) are of the same color.

There are \(M\) white edges and \(\frac{N(N-1)}{2} - M\) black edges.

Input format

First line: Two integers - \(N\) and \(M\) \((3 \le N \le 10^5, 1 \le M \le 3 \cdot 10^5)\)
\((i + 1)^{th}\) line: Two integers - \(u_i\) and \(v_i\) \((1 \le u_i, v_i \le N)\) denoting that the edge \((u_i, v_i)\) is white in color

Note: The conditions\((u_i,v_i) \neq (u_j, v_j)\) and \((u_i,v_i) \neq (v_j,u_j)\) are satisfied for all \(1 \le i < j \le M\).

Output format

Print an integer that denotes the number of triples that satisfy the mentioned condition.

Additional information

For \(20\) points: \(N \le 200\) is satisfied
For additional \(20\) points: \(N \le 2000\) is satisfied
Original constraints for remaining points