Problem J
Triangle Counting
Having
a simple undirected graph 
, a triangle is defined as a triple 
where 
and 
for all 
and 
. In this problem, you are given an undirected graph and
asked to count all the triangles in this graph. You are assured that there is
no edge in this graph that is the member of more than 2 triangles.
The Input
The
first line of input contains an integer 
, which is the number of test cases. Each test case begins
with a line containing two integers 
and m which are the number of vertices and the number
of edges in the graph respectively. The next m lines contain two
integers 
indicating that there
is an edge between vertex 
and vertex
.
Tip
for C++ Programmers: Any attempt to
use ifstream to
read the input will exceed the time limit for this problem. Use scanf instead.
The Output
Output
for each test case consists of one line containing the number of triangles in
the specified graph of the test case.
Sample Input
1
4 6
1 2
2 3
3 1
1 4
2 4
3 4
Sample Output
4