Algorithms and Data Structures

Count the Number of Triangles in a Graph

Given an undirected graph with v vertices and e edges, you are asked to count the number of triangles in the graph.
A triangle in a graph is a set of 3 vertices that any are all connected to each other.
For instance, the graph in the image has 3 triangles:
  1. 1-2-5
  1. 2-5-4
  1. 3-2-4
notion image

Input

The first line of the input contains two integers v (1 ≤ v ≤ 100) and e (1 ≤ e ≤ ).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print the number of triangles in the given graph.

Examples

Input
Output
5 7 1 2 1 5 2 5 4 5 2 4 2 3 3 4
3
3 2 1 2 2 3
0
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in