Triangle Counting

Having a simple undirected graph G = (V,E), a triangle is defined as a triple (v1,v2,v3) where v1,v2,v3 ∈V and(v1,v2)∈Eforall1≤i,j≤3andi̸=j. Inthisproblem,youaregivenan 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. Input The first line of input contains an integer T ≤ 250, which is the number of test cases. Each test case begins with a line containing two integers 1 ≤ n ≤ 3000 and m which are the number of vertices and the number of edges in the graph respectively. The next m lines contain two integers 1 ≤ i,j ≤ 3000 indicating that there is an edge between vertex i and vertex j. Tip for C++ Programmers: Any attempt to use ifstream to read the input will exceed the time limit for this problem. Use scanf instead. 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 46 12 23 31 14 24 34 Sample Output 4