题目背景

本题不同于 bzoj1023，bzoj1023 洛谷快捷通道：[SHOI2008] 仙人掌图 II。

题目描述

仙人掌图（cactus）是一种无向连通图，它的每条边最多只能出现在一个简单回路（simple cycle）里面。从直观上说，可以把仙人掌图理解为允许存在回路的树。但是仙人掌图和树之间有个本质的不同，仙人掌图可以拥有多个支撑子图（spanning subgraph），而树的支撑子图只有一个（它自身），我们把仙人掌图的支撑子图的数目称为“仙人数”。你的任务就是计算给定图的“仙人数”。

一些关于仙人掌图的举例：

第一张图是一个仙人掌图，第二张图的边 $(2,3)$ 在两个不同的回路里面，所以不是仙人掌图，第三张图不是一个连通图，所以也不是仙人掌图。

以下是对一些术语的解释：

• 简单回路（simple cycle）：简单回路是原图的一条路径，这条路径的边集构成了回路，回路中顶点只能出现一次。比如对于上例中第二个图来说，它一共有三个简单回路，分别是 $(4,3,2,1,6,5)$、$(7,8,9,10,2,3)$ 和 $(4,3,7,8,9,10,2,1,6,5)$；
• 支撑子图（spanning subgraph）：支撑子图也是原图的子图，这种子图可以比原来少一些边，但是不能破坏图的连通性，也不能去除原来图上的任何顶点。“支撑”的概念类似于我们熟知的“最小支撑树”，对于上例中的第一张图来说，任意去除回路I中的图或回路II中的一条边都能构成一个支撑子图，所以它的支撑子图一共有 $6 + 4 + 6 × 4 + 1 = 35$ 种（注意图自身也是自己的一个子图）。

输入格式

输入文件的第一行是两个整数 $n$ 和 $m$。$n$ 代表图的顶点数，顶点的编号总是从 $1$ 到 $n$ 表示的。

接下来一共有 $m$ 行。每行都代表了图上的一条路径（注意：这里所表示的一条路径可不一定是一条回路）。这些行的格式是首先有一个整数 $k_i$ 代表这条路径通过了几个顶点，接下来是 $k_i$ 个在 $1$ 到 $n$ 之间的数字，其中每个数字代表了图上的一个顶点，相邻的顶点之间就定义了一条边。一条路径上可能通过一个顶点好几次，比如对于第一个例子，第一条路径从 $2$ 经过 $3$，又从 $8$ 返回到了 $3$，但是我们保证所有的边都会出现在某条路径上，而且不会重复出现在两条路径上，或者在一条路径上出现两次。

输出格式

输出这张图的“仙人数”，如果它不是一张仙人掌图，输出 0。注意最后的答案可能是一个很大很大的数。

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

35

10 2
7 1 2 3 4 5 6 1
6 3 7 8 9 10 2

0

5 1
4 1 2 3 4

0

提示

对于所有数据，满足 $1\le n\le 20000$，$0\le m\le 1000$，$2\le k_i\le 1000$。