Cactus Automorphisms

A cactus is a connected undirected graph in which every edge belongs to at most one simple cycle. Think of it as a tree that is allowed a few cycles. NEERC has been setting problems about cactuses for years. In 2005, the first year one appeared, the problem was called simply Cactus. In 2007 it was Cactus Reloaded, and in 2010 it was Cactus Revolution.

Preparing test data for those problems runs into one difficulty. Some wrong solutions behave differently depending on how the vertices are numbered in the input, so for the most interesting tests the judges include the same graph several times with different numbering. Some graphs are regular enough that renumbering the vertices leaves the graph unchanged. To decide objectively how many tests a graph deserves, the judges want a number that says how regular that graph is.

That number is the count of graph automorphisms. Let $(V, E)$ be an undirected graph, where $V$ is a set of vertices and $E$ is a set of edges, and each edge is a set of two distinct vertices $\{v_1, v_2\}$ with $v_1, v_2 \in V$. A graph automorphism is a bijection $m$ from $V$ onto $V$ such that for every pair of vertices $v_1$ and $v_2$ joined by an edge (so $\{v_1, v_2\} \in E$), the condition $\{m(v_1), m(v_2)\} \in E$ holds.

Every graph has at least one automorphism, the identity, and a graph with $n$ vertices has at most $n!$ of them. The count can be very large, so the answer must be written as a prime factorization $\prod_{i=1}^{k} p_i^{q_i}$, where the $p_i$ are primes in ascending order ($p_i \ge 2$, $p_i < p_{i+1}$) and the $q_i$ are the matching exponents ($q_i > 0$).

The first line contains two integers $n$ and $m$ ($1 \le n \le 50\,000$, $0 \le m \le 50\,000$). Here $n$ is the number of vertices in the graph, numbered from $1$ to $n$. The edges of the graph are given as a set of edge-distinct paths, and $m$ is the number of those paths.

Each of the next $m$ lines contains one path. A path starts with an integer $k_i$ ($2 \le k_i \le 1000$) followed by $k_i$ integers from $1$ to $n$. Those $k_i$ integers are the vertices of the path in order. Adjacent vertices in a path are distinct. A path may visit the same vertex several times, but every edge is traversed exactly once in the whole input. There are no multiedges: at most one edge joins any two vertices.

The graph in the input is a cactus.

On the first line print the number $k$ of prime factors in the factorization of the number of graph automorphisms. Print $0$ if the number of graph automorphisms is $1$. On each of the next $k$ lines print a prime $p_i$ and its power $q_i$ separated by a space. The primes must be given in ascending order.

The graph in the first example has $4 = 2^2$ automorphisms.

The second example is a simple graph with two vertices and one edge between them, which has $2 = 2^1$ automorphisms.

The third example is a star graph with a center vertex and $14$ rays, which has $14! = 87\,178\,291\,200 = 2^{11} \times 3^5 \times 5^2 \times 7^2 \times 11^1 \times 13^1$ automorphisms.