Description

定义一种无向连通图叫仙人掌图（Cactus图）。仙人掌图中没有重边和自环，并且其中的每一条边至多位于一个简单环上。简单地说，仙人掌图是树的一种泛化形式，其中允许出现一些环。

现在有一个仙人掌图，你每次可以移动一条边（移除图的一条边，并将另一对顶点用一条边连接起来）。问如果要让后来得到的新图仍然是仙人掌图，有多少种移动边的办法？

Input Format

第一行包含两个整数n和m，分别表示图中的顶点数（顶点的编号分别为${1,2,3,...,n}$）和边的数目，且满足

第2~m+1行，每一行表示一条路径（从一个顶点出发一直往后走，直到当前所在的顶点没有任何未走过一条边）。

（译者注：虽然应该都能看出来了，但是还是用一个递归函数更浅显易懂）

设路径的开始点为$q_1$，$E_i$表示第$i$个点的边,$vis$数组中存储已经走过了的边，则整条路径可定义为：

1.x←q1
2.f(x)
	1.add(vis[],x)
	2.for i∈Ex do
	1.if i not in vis[] then
		1.call f(i->to)
3.print(vis[])

即：每一行的开始有一个整数$k_i$，满足 $2≤k_i≤1000$，紧接着有$k_i$个整数，表示这条路径所经过的顶点$q_i$，满足$q_i∈[1,n]$。

数据保证路径中的相邻顶点是不同的。

在路径中可以多次到达同一个顶点，但在整个输入文件中，每条边只遍历一次。

数据保证输入文件中的图形是仙人掌。

Output Format

输出文件中只有一个整数，即移动仙人掌图中一条边的方法数。

6 1
7 1 2 5 6 2 3 4

42

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

216

Hint