Background

We are currently at a critical stage of epidemic prevention and control. Everyone should wash their hands often to prevent infection through contact.

Correct handwashing method

Problem Description

Given an undirected complete graph with $n$ vertices, where $m$ edges are white and the remaining edges are black.

You need to find the number of monochromatic 3-cycles (that is, triangles).

Input Format

The first line contains integers $n, m$, with the meaning as described above.

The remaining $m$ lines each contain two integers $u, v$, representing the two endpoints of a white edge. It is guaranteed that the given white edges have no multiple edges and no self-loops.

Output Format

Output one integer in one line, which is the answer.

5 3
1 5
2 5
3 5

4

Hint

• For $20\%$ of the testdata, $n \leq 200$.
• For $50\%$ of the testdata, $n \leq 2000$.
• For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 3\times 10^5$.

Translated by ChatGPT 5