题目描述

NEERC had featured a number of problems in previous years about cactuses -- connected undirected graphs in which every edge belongs to at most one simple cycle. Intuitively, cactus is a generalization of a tree where some cycles are allowed.

In $2005$ , the first year where problems about cactuses had appeared, the problem was called simply Cactus. In $2007$ it was Cactus Reloaded and in $2010$ it was called Cactus Revolution. An example of cactus from NEERC $2007$ problem is given on the picture below.

The challenge that judges face when preparing test cases for those problems is that some wrong solutions may depend on the numbering of vertices in the input file. So, for the most interesting test cases judges typically include several inputs with the same graph, but having a different numbering of vertices. However, some graphs are so regular that the graph remains the same even if you renumber its vertices. Judges need some metric about the graph that tells how regular the given graph is in order to make an objective decision about the number of test cases that need to be created for this graph.

The metric you have to compute is the number of graph automorphisms. Given an undirected graph $(V , E)$ , where $V$ is a set of vertices and $E$ is a set of edges, where each edge is a set of two distinct vertices ${v_{1}, v_{2}} (v_{1}, v_{2} ∈ V ),$ graph automorphism is a bijection $m$ from $V$ onto $V$ , such that for each pair of vertices $v_{1}$ and $v_{2}$ that are connected by an edge (so ${v_{1}, v_{2}} ∈ E)$ the following condition holds: ${m(v_{1}), m(v_{2})} ∈ E$ .

Each graph has at least one automorphism (one where $m$ is an identity function) and may have up to $n$ ! automorphisms for a graph with $n$ vertices. Because the number of automorphisms may be a very big number, the answer must be presented as a prime factorization $∏^{k}_{i=1} p_{i}^{q_{i}},$ where $p_{i}$ are prime numbers in ascending order $(p_{i} \ge 2 , p_{i} 0)$ .

输入格式

The first line of the input file contains two integer numbers $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. Vertices are numbered from $1$ to $n$ . Edges of the graph are represented by a set of edge-distinct paths, where $m$ is the number of such paths.

Each of the following $m$ lines contains a path in the graph. A path starts with an integer number $k_{i} (2 \le k_{i} \le 1000)$ followed by $k_{i}$ integers from $1$ to $n$ . These $k_{i}$ integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input file. There are no multiedges in the graph (there is at most one edge between any two vertices).

The graph in the input file is a cactus.

输出格式

On the first line of the output file write number $k$ -- the number of prime factors in the factorization of the number of graph automorphisms. Write $0$ if the number of graph automorphisms is $1$ . On the following $k$ lines write prime numbers $p_{i}$ and their powers $q_i$ separated by a space. Prime numbers must be given in ascending order.

题目大意

• 仙人掌是满足如下条件的无向简单连通图：每条边被包含于至多一个简单环中。
• 设有无向图 $G=(V,E)$。称双射 $f:V\rightarrow V$ 是 $G$ 的自同构，当且仅当 $\forall v_1,v_2\in V$，都有 $(v_1,v_2)\in E\Leftrightarrow (f(v_1),f(v_2))\in E$。称两个自同构 $f_1,f_2$ 相同，当且仅当 $\forall v\in V$ 均有 $f_1(v)=f_2(v)$。
• 给定有 $n$ 个节点的仙人掌，求它的不同的自同构数。由于结果可能很大，你需要输出它的质因子分解的结果。
• 输入仙人掌的方式为：给定 $m$ 条路径，这些路径所覆盖的边即为仙人掌的全部边。保证这些路径不会重复经过一条边两次，且输入的图是仙人掌。
• $n,m\leq 5\times 10^4$。

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10

1
2 2

2 1
2 1 2

1
2 1

15 7
3 1 2 3
3 4 2 5
3 6 2 7
3 8 2 9
3 10 2 11
3 12 2 13
3 14 2 15

6
2 11
3 5
5 2
7 2
11 1
13 1

提示

Time limit: 5 s, Memory limit: 256 MB.