선인장 그래프의 자기동형사상

선인장은 모든 간선이 단순 사이클에 최대 한 개만 속하는 연결 무향 그래프다. 사이클을 몇 개 허용한 트리라고 보면 된다. NEERC는 예전부터 선인장을 다루는 문제를 여러 번 냈다. 선인장이 처음 등장한 2005년 문제의 제목은 그냥 Cactus였고, 2007년은 Cactus Reloaded, 2010년은 Cactus Revolution이었다.

이런 문제의 테스트 데이터를 만들 때 출제진은 한 가지 난관을 만난다. 틀린 풀이 중 일부는 입력에 적힌 정점 번호에 따라 결과가 달라진다. 그래서 중요한 테스트는 같은 그래프를 정점 번호만 바꿔 여러 번 넣는다. 그런데 어떤 그래프는 규칙적이라서 번호를 바꿔도 그래프가 그대로다. 어떤 그래프에 테스트를 몇 개나 만들지 객관적으로 정하려면, 그 그래프가 얼마나 규칙적인지 알려 주는 값이 필요하다.

그 값이 자기동형사상의 개수다. 정점 집합 $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$은 그 경로의 개수다.

이어지는 $m$개 줄에는 경로가 하나씩 주어진다. 각 줄은 정수 $k_i$로 시작하고($2 \le k_i \le 1000$), 그 뒤에 $1$ 이상 $n$ 이하의 정수 $k_i$개가 이어진다. 이 $k_i$개의 정수가 경로를 지나는 정점을 순서대로 나타낸다. 경로에서 인접한 두 정점은 서로 다르다. 한 경로가 같은 정점을 여러 번 지날 수 있지만, 입력 전체에서 모든 간선은 정확히 한 번씩 등장한다. 두 정점을 잇는 간선은 최대 한 개다.

입력으로 주어지는 그래프는 선인장이다.

첫째 줄에 그래프 자기동형사상 개수를 소인수분해했을 때 나오는 소인수의 개수 $k$를 출력한다. 자기동형사상이 한 개뿐이면 $0$을 출력한다. 이어지는 $k$개 줄에는 소수 $p_i$와 그 지수 $q_i$를 공백으로 구분해 출력한다. 소수는 오름차순으로 출력한다.

첫 번째 예제의 그래프는 자기동형사상이 $4 = 2^2$개다.

두 번째 예제는 정점 두 개를 간선 하나로 이은 그래프이고, 자기동형사상이 $2 = 2^1$개다.

세 번째 예제는 가운데 정점 하나에 정점 $14$개가 각각 이어진 별 그래프이고, 자기동형사상이 $14! = 87\,178\,291\,200 = 2^{11} \times 3^5 \times 5^2 \times 7^2 \times 11^1 \times 13^1$개다.