[SHOI2006]仙人掌

题目背景

#本题不同于bzoj1023 bzoj1023快捷通道:[[SHOI2008] cactus仙人掌图(II)](https://www.luogu.org/problemnew/show/P4244)

题目描述

仙人掌图(cactus)是一种无向连通图,它的每条边最多只能出现在一个简单回路(simple cycle)里面。从直观上说,可以把仙人掌图理解为允许存在回路的树。但是仙人掌图和树之间有个本质的不同,仙人掌图可以拥有多个支撑子图(spanning subgraph),而树的支撑子图只有一个(它自身),我们把仙人掌图的支撑子图的数目称为“仙人数”。你的任务就是计算给定图的“仙人数”。 一些关于仙人掌图的举例: ![](https://cdn.luogu.com.cn/upload/pic/13241.png) 第一张图是一个仙人掌图,第二张图的边(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。注意最后的答案可能是一个很大很大的数。

输入输出样例

输入样例 #1

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

输出样例 #1

35

输入样例 #2

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

输出样例 #2

0

输入样例 #3

5 1
4 1 2 3 4

输出样例 #3

0