선인장 그래프

트리는 연결된 무향 그래프 중에서 어떤 간선도 사이클에 속하지 않는 그래프이다. 이와 비슷하게 선인장 그래프는 연결된 무향 그래프 중에서 모든 간선이 많아야 하나의 사이클에만 속하는 그래프이다.

스패닝 부분 그래프는 원래 그래프의 모든 정점을 포함하고, 원래 그래프의 간선 중 일부를 선택해서 만든 연결 부분 그래프이다. 원래 그래프 자신도 스패닝 부분 그래프에 포함된다.

그래프가 주어졌을 때, 이 그래프가 선인장 그래프인지 판별하고, 선인장 그래프라면 스패닝 부분 그래프이면서 선인장 그래프인 경우의 수를 구하시오.

첫째 줄에 두 정수 N과 M이 주어진다. N은 그래프의 정점 수이고, M은 간선을 표현하는 경로의 수이다.

• 1 <= N <= 20,000
• 0 <= M <= 1,000

다음 M개의 줄에는 경로가 하나씩 주어진다. 각 줄의 첫 번째 정수는 그 경로에 포함된 정점의 수이고, 이어서 경로의 정점들이 순서대로 주어진다. 한 줄에서 서로 이웃한 두 정점 사이에 간선이 있다.

하나의 정점은 여러 경로에 나타날 수 있지만, 하나의 간선은 전체 입력에서 정확히 한 번만 나타난다. 입력으로 주어지는 그래프의 간선 수는 항상 2N 이하이다.

그래프가 선인장 그래프가 아니라면 첫째 줄에 0을 출력한다.

그래프가 선인장 그래프라면 스패닝 부분 그래프이면서 선인장 그래프인 경우의 수를 첫째 줄에 출력한다.