Problem Description

A cactus is an undirected simple connected graph that satisfies the following condition: each edge is contained in at most one simple cycle.

Given an undirected graph \( G = (V, E) \), a bijection \( f: V \rightarrow V \) is an automorphism of \( G \) if and only if for all \( v_1, v_2 \in V \), \((v_1, v_2) \in E \Leftrightarrow (f(v_1), f(v_2)) \in E\). Two automorphisms \( f_1 \) and \( f_2 \) are considered the same if and only if for all \( v \in V \), \( f_1(v) = f_2(v) \).

You are given a cactus with \( n \) nodes and need to find the number of distinct automorphisms. Since the result may be very large, you should output its prime factorization.

The input format for the cactus is as follows: you are given \( m \) paths, and the edges covered by these paths constitute the entire cactus. It is guaranteed that these paths do not traverse any edge more than once, and the input graph is indeed a cactus.

Constraints: \( n, m \leq 5 \times 10^4 \).

Input Format

The first line of the input file contains two integers \( n \) and \( m \) (\( 1 \leq n \leq 50,000 \), \( 0 \leq m \leq 50,000 \)). Here, \( n \) is the number of vertices in the graph, numbered from 1 to \( n \). The 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 \( k_i \) (\( 2 \leq k_i \leq 1,000 \)) 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. A path can visit the same vertex multiple times, but every edge is traversed exactly once in the entire 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.

Output Format

On the first line of the output file, write the 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 the prime numbers \( p_i \) and their powers \( q_i \) separated by a space. Prime numbers must be given in ascending order.

Sample Input and Output

Input Sample #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

Output Sample #1

1
2 2

Input Sample #2

2 1
2 1 2

Output Sample #2

1
2 1

Input Sample #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

Output Sample #3

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

Notes

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

见题面 Input 部分

见题面 Output 部分