Subgraph isomorphism P57656

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 G₁ = (V₁, E₁) and G₂ = (V₂, E₂), G₁ and G₂ are said to be isomorphic if and only if there exists a bijection f : V₁ → V₂ such that for every x, y ∈ V₁, {x, y} ∈ E₁ ⇔ {f(x), f(y)} ∈ E₂. 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.