Background

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$.

Problem Description

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

Input Format

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 Format

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

3 3
1 2
2 3
3 1

1

5 8
1 2
2 3
3 5
5 4
4 2
5 2
1 4
3 4

5

Hint

[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