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_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}),
G_{1} and G_{2} are said to be isomorphic
if and only if there exists a bijection f : V_{1} → V_{2}
such that for every x, y ∈ V_{1},
{x, y} ∈ E_{1} ⇔ {f(x), f(y)} ∈ E_{2}.
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++