Subgraph isomorphism P57656


Statement
 

pdf   zip

html

Given an undirected graph G = (V, E), where V is a set of vertices and E is a set of edges, a connected component of G is a maximal connected subgraph of G. In other words, every two vertices x and y of V belong to the same connected component if and only if there is a path from x to y. In the example below there are 7 connected components.

Given two undirected (sub)graphs G1 = (V1, E1) and G2 = (V2, E2), G1 and G2 are said to be isomorphic if and only if there exists a bijection f : V1V2 such that for every x, yV1, {x, y} ∈ E1 ⇔ {f(x), f(y)} ∈ E2. In the example above, the connected component with vertices { 5, 2, 9} is isomorphic to exactly two connected components: those with vertices {12, 15, 8} and {6, 10, 1}.

Write a program such that, for every given undirected graph G, computes the number of pairs (not counting order) of connected components of G that are isomorphic. For instance, the result for the graph above is 4: { 5, 2, 9} with {12, 15, 8}, { 5, 2, 9} with {6, 10, 1}, {12, 15, 8} with {6, 10, 1}, and { 7} with { 4}.

Input

Input consists of several graph descriptions. Each one begins with the number of vertices n and the number of edges m. Follow m pairs of different numbers, each between 0 and n−1. You can assume 1 ≤ n ≤ 10000. No edges are repeated. Every given connected component has at most 6 vertices.

Output

For every graph, print the number of connected components that are pairwise isomorphic.

Public test cases
  • Input

    16 10
    5 2 5 9 12 8 14 11 14 3 0 13 6 10 6 1 15 8 11 3
    101 0
    

    Output

    4
    5050
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tercer Concurs de Programació de la UPC - Semifinal
    Date
    2005-09-14