Count Triangles

You are given an undirected graph. Your task is to count the number of triangles (cycles of length 3) there are in the graph. Three vertices $a,b,c$ ($a < b < c$) are considered a triangle if there exists edges $\{ a,b\} $, $\{ b,c\} $, $\{ c,a\} $. For instance, this means that the triples $\{ 1,2,3\} $ and $\{ 3,1,2\} $ are considered to be the same triangle and should thus only be counted once.

As the focus of the competition is improving your constant factor, here is one approach to get near-optimal time complexity.

Input

The first line of input contains two integers $N$ and $M$ ($1 \leq N \leq 10^5$, $0 \leq M \leq min(\frac{N \cdot (N-1)}{2}, 10^5)$), the number of vertices and edges. Each of the following $M$ lines contains two space-separated integers $u$ and $v$ ($0 \leq u, v < N$, $u \neq v$), meaning that there is an edge between node $u$ and $v$. There will never be more than one edge between two nodes.

Output

Print one integer, the number of triangles in the graph.

Scoring

Solve as many test groups as possible. Secondarily, minimize the runtime for the slowest testcase in a solved test group.

4 5
0 1
1 2
2 0
1 3
2 3

2

6 9
0 1
1 2
2 0
3 0
3 1
4 1
4 2
5 2
5 0

4