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++
- Event
- Tercer Concurs de Programació de la UPC - Semifinal
- Date
- 2005-09-14