Background

A triangle in an undirected graph $G$ is a subgraph $G_0$ of $G$ that consists of 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$ and $G_2$ are considered 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 the graph.

Input Format

Each test case consists of a single input file.

The first line contains two integers separated by a space, representing the number of vertices $n$ and the number of edges $m$ of the graph.

From the second line to the $(m + 1)$-th line, each line contains two integers $u$ and $v$ separated by a space, indicating an edge connecting vertex $u$ and vertex $v$.

Output Format

Output a single integer on one line, representing the number of triangles in the graph.

Sample Input and Output

Sample Input #1

3 3
1 2
2 3
3 1

Sample Output #1

1

Sample Input #2

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

Sample Output #2

5

Notes

Explanation of Sample 2

There are 5 triangles, each containing the following sets of vertices: $\{1, 2, 4\}$, $\{2, 3, 4\}$, $\{2, 3, 5\}$, $\{2, 4, 5\}$, $\{3, 4, 5\}$.

Data Range and Constraints

This problem is divided into two subtasks with bundled test cases.

• 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 graph does not contain duplicate edges or self-loops, and it is not guaranteed to be connected.

Hints

• Be mindful of the impact of constant factors on the efficiency of your program.

见题面 Input 部分

见题面 Output 部分