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_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 \to V_2$ such that for every $x, y \in V_1$, $\{x, y\} \in E_1 \Leftrightarrow \{f(x), f(y)\} \in 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 \le n \le 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.