题目背景

#本题不同于bzoj1023 bzoj1023快捷通道：[SHOI2008] cactus仙人掌图(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（1≤n≤20000, 0≤m≤1000）。n代表图的顶点数，顶点的编号总是从1到n表示的。

接下来一共有m行。每行都代表了图上的一条路径（注意：这里所表示的一条路径可不一定是一条回路）。这些行的格式是首先有一个整数ki（2≤ki≤1000）代表这条路径通过了几个顶点，接下来是ki个在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