382. Counting Triangles

Challenge1000 ms256 MBSolved by 0%

Edges are undirected again. Print how many triangles the graph contains, meaning how many sets of three vertices where all three pairs are joined.

This is the problem that pays for an adjacency MATRIX. Checking every set of three vertices means asking "is there an edge between a and b" a great many times, and an adjacency list answers that by scanning a list while a matrix answers it by one array lookup.

The trade is memory. The matrix is n by n regardless of how few edges there are, which is why n is small here and large everywhere else in this topic.

Count each triangle once by only ever considering a < b < c. Without that, every triangle is found six times, once per ordering of its three vertices.

Constraints - `1 ≤ n ≤ 200` - `0 ≤ m ≤ 5000` - There are no self-loops and no repeated edges.

Input

The first line contains two integers n and m, the number of vertices and edges. Each of the next m lines contains two integers u and v, an undirected edge between those vertices. Vertices are numbered 1 to n.

Output

Print one integer, the number of triangles.

Input3 3 1 2 2 3 3 1

Output1

Noteis a single triangle, which must be counted once and not six times

Input4 6 1 2 1 3 1 4 2 3 2 4 3 4

Output4

Notejoins every pair among four vertices, giving one triangle per set of three

Input4 3 1 2 2 3 3 4

Output0

Noteis a path, where no three vertices are all joined

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution