P1989 [Template] Counting Triangles in an Undirected Graph

A triangle in an undirected graph $G$ refers to a subgraph $G_0$ of $G$ such that $G_0$ has exactly three vertices $u, v, w$, and exactly three edges $\langle u, v \rangle, \langle v, w \rangle, \langle w, u \rangle$. Two triangles $G_1, G_2$ are different if and only if there exists a vertex $u$ such that $u \in G_1$ and $u \notin G_2$.

Given a simple undirected graph with $n$ vertices and $m$ edges, find the number of triangles in it.

Each test point has one and only one set of testdata. The first line contains two integers separated by a space, representing the number of vertices $n$ and the number of edges $m$. Lines $2$ to $(m + 1)$ each contain two integers $u, v$ separated by a space, indicating an edge connecting vertex $u$ and vertex $v$.

Output one line with one integer, representing the number of triangles in the graph.

**[Sample 2 Explanation]** There are $5$ triangles. The vertices contained in each triangle are $\{1, 2, 4\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\}$. **[Constraints]** **This problem uses bundled multi-testpoint evaluation and has two subtasks.** - Subtask 1 (30 points): $n \le 500$, $m \le {10}^3$. - Subtask 2 (70 points): No special properties. For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 2 \times {10}^5$, $1 \le u, v \le n$. The given graph has no multiple edges or self-loops, **but it is not guaranteed to be connected**. **[Note]** - Please pay attention to the impact of constant factors on program efficiency. Translated by ChatGPT 5