Squares in a graph P99912


Statement
 

pdf   zip

thehtml

You are given an undirected graph G. Let us define a square as any cycle of length exactly four in G. Can you count the number of squares in G?

Input

Input consists of several cases. Every case begins with two natural numbers n and m, which are respectively the number of vertices and the number of edges of G. Follow m pairs x y to indicate that there is an edge connecting vertices x and y. Assume 0 ≤ n ≤ 2000 and 0 ≤ m ≤ 10n. Vertices are numbered starting at 0. There are no edges of the kind x x, nor repeated edges.

Output

For every given G, print its number of squares.

Public test cases
  • Input

    4 4
    0 1  1 2  2 3  3 0
    
    6 5
    0 1  0 2  1 2  2 4  4 5
    
    5 7
    0 1  2 0  0 3  4 1  2 4  3 4  2 1
    

    Output

    1
    0
    3
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++