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-2-5
- 2-5-4
- 3-2-4

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