Count Monochromatic Triangles in a Complete Graph

You are given an undirected complete graph with n vertices. In this graph, exactly m edges are white and all remaining edges are black. Your task is to count the number of triangles (i.e. 3-cycles) whose three edges are all of the same color (either all white or all black).

The problem can be formalized as follows:

Given a complete graph with vertices \(\{1,2,\dots,n\}\). There are exactly \(m\) white edges specified in the input and every pair of vertices not connected by a white edge is connected by a black edge. A triangle is a set of three vertices \(\{i, j, k\}\) with \(i < j < k\). A triangle is monochromatic if either all its three edges are white or all are black.

Your goal is to compute the total number of monochromatic triangles.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input consists of:

• The first line contains two integers \(n\) and \(m\) where \(n\) is the number of vertices and \(m\) is the number of white edges.
• The next \(m\) lines each contain two integers \(u\) and \(v\) (with \(1 \leq u, v \leq n\) and \(u \neq v\)) representing a white edge between vertices \(u\) and \(v\).

The graph is complete, so any edge not specified as white is considered to be black.

outputFormat

Output a single integer: the number of monochromatic triangles in the graph.

sample

4 2
1 2
2 3

1