P6998 [NEERC 2013] Cactus Automorphisms

NEERC 在前几年中曾出现过一些关于仙人掌图的问题——仙人掌图是一个连通的无向图，其中每条边最多属于一个简单环。从直观上看，仙人掌图是树的一种推广，其中允许存在一些环。 在 2005 年，首次出现关于仙人掌图的问题时，问题被简单地称为“Cactus”。在 2007 年，它被称为“Cactus Reloaded”，而在 2010 年，它被称为“Cactus Revolution”。下图展示了 NEERC 2007 年问题中的一个仙人掌图示例。  在为这些问题准备测试用例时，评委面临的挑战是，一些错误的解决方案可能依赖于输入文件中顶点的编号。因此，对于最有趣的测试用例，评委通常会包含几个具有相同图但顶点编号不同的输入。然而，有些图是如此规则，以至于即使重新编号其顶点，图仍保持不变。评委需要一些关于图的度量来判断给定图的规则性，以便对需要为该图创建的测试用例数量做出客观决定。 你需要计算的度量是图的自同构数量。给定一个无向图 $(V , E)$，其中 $V$ 是顶点集，$E$ 是边集，每条边是由两个不同顶点组成的集合 $\{v_{1}, v_{2}\} (v_{1}, v_{2} \in V)$，图的自同构是一个从 $V$ 到 $V$ 的双射 $m$，使得对于每对由边连接的顶点 $v_{1}$ 和 $v_{2}$（即 $\{v_{1}, v_{2}\} \in E$），以下条件成立：$\{m(v_{1}), m(v_{2})\} \in E$。 每个图至少有一个自同构（当 $m$ 是恒等函数时），对于具有 $n$ 个顶点的图，最多可能有 $n!$ 个自同构。由于自同构的数量可能是一个非常大的数字，答案必须以素因数分解的形式呈现 $\prod^{k}_{i=1} p_{i}^{q_{i}}$，其中 $p_{i}$ 是按升序排列的素数 $(p_{i} \ge 2, q_{i} > 0)$。

输入文件的第一行包含两个整数 $n$ 和 $m (1 \le n \le 50 000, 0 \le m \le 50 000)$。这里 $n$ 是图中的顶点数。顶点从 $1$ 到 $n$ 编号。图的边由一组边不重复的路径表示，其中 $m$ 是这样的路径数。 接下来的 $m$ 行中的每一行包含图中的一条路径。路径以一个整数 $k_{i} (2 \le k_{i} \le 1000)$ 开头，后跟 $k_{i}$ 个从 $1$ 到 $n$ 的整数。这些 $k_{i}$ 个整数表示路径的顶点。路径中的相邻顶点是不同的。路径可以多次经过同一顶点，但整个输入文件中每条边恰好被遍历一次。图中没有重边（任意两个顶点之间最多有一条边）。 输入文件中的图是一个仙人掌图。

在输出文件的第一行写入数字 $k$——图自同构数量的素因数分解中的素因子数量。如果图自同构的数量是 $1$，则写入 $0$。在接下来的 $k$ 行中写入素数 $p_{i}$ 及其幂 $q_i$，用空格分隔。素数必须按升序给出。

时间限制：5 秒，内存限制：256 MB。 题面翻译由 ChatGPT-4o 提供。