NEERC 在往年曾推出过许多关于仙人掌图（cactus）的题目。仙人掌图是一种连通的无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是树的一种推广，允许存在一些环。

在 2005 年，即仙人掌图相关题目出现的第一年，题目被简单地命名为“Cactus”。2007 年的题目名为“Cactus Reloaded”，2010 年则称为“Cactus Revolution”。下图中展示了 NEERC 2007 题目中的一个仙人掌图示例。

评委在准备这些题目的测试数据时面临的挑战是，一些错误的解法可能会依赖于输入文件中顶点的编号。因此，为了得到最有趣的测试用例，评委通常会包含多个具有相同图结构但顶点编号不同的输入。然而，有些图非常规则，即使重新编号，图的结构依然保持不变。评委需要一个关于图的度量指标，用以衡量给定图的规则程度，从而客观地决定该图需要创建多少个测试用例。

你需要计算的指标是图的自同构（automorphism）数量。给定一个无向图 $(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$。

每个图至少有一个自同构（即恒等映射），对于一个有 $n$ 个顶点的图，最多可能有 $n!$ 个自同构。由于自同构的数量可能非常大，答案必须以质因数分解的形式 $\prod_{i=1}^k p_i^{q_i}$ 给出，其中 $p_i$ 是按升序排列的质数（$p_i \ge 2, p_i < p_{i+1}$），$q_i$ 是对应的幂次（$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$，表示图自同构数量的质因数分解中质因子的个数。如果图的自同构数量为 $1$，则输出 $0$。在接下来的 $k$ 行中，每行写入一个质数 $p_i$ 及其幂次 $q_i$，中间用空格隔开。质数必须按升序排列。

样例

输入 1

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

1
2 2

说明 1

第一个样例输入对应题目描述中的图片。该图有 $4 = 2^2$ 个自同构。

输入 2

2 1
2 1 2

输出 2

1
2 1

说明 2

第二个样例输入是一个简单的图，包含两个顶点和它们之间的一条边，该图有 $2 = 2^1$ 个自同构。

输入 3

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

输出 3

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

说明 3

第三个样例输入是一个“星形”图，包含一个中心顶点和 $14$ 条射线，该图有 $14! = 87\,178\,291\,200 = 2^{11} \times 3^5 \times 5^2 \times 7^2 \times 11^1 \times 13^1$ 个自同构。