这是第 20 届东北欧区域竞赛（NEERC）。仙人掌图问题已经成为了 NEERC 的传统。第一个仙人掌图问题出现在 2005 年，因此今年是一个纪念——仙人掌图问题十周年。

仙人掌图是一个连通无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是树的一种推广，允许存在一些环。仙人掌图中不允许有重边（一对顶点之间有多条边）和自环（连接顶点与其自身的边）。

给定一个仙人掌图。我们定义“移动一条边”为：移除图中的一条边，并连接一对不同的顶点，使得变换后的图仍然是一个仙人掌图。请问有多少种方法可以执行这样的移动？

例如，在上面左侧的仙人掌图中（对应第一个样例），有 42 种移动边的方法。在右侧的仙人掌图中（对应第二个样例，即 2005 年原题中的经典 NEERC 仙人掌图），有 216 种移动边的方法。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 50\,000$, $0 \le m \le 50\,000$)。其中 $n$ 是图中的顶点数。顶点编号从 $1$ 到 $n$。图的边由一组边不相交的路径表示，$m$ 是这些路径的数量。

接下来的 $m$ 行，每行包含图中的一条路径。路径以一个整数 $k_i$ ($2 \le k_i \le 1000$) 开头，后跟 $k_i$ 个 $1$ 到 $n$ 之间的整数。这些整数表示路径上的顶点。路径中相邻的顶点是不同的。路径可以多次经过同一个顶点，但整个输入文件中每条边恰好被遍历一次。

输入文件中的图是一个仙人掌图。

输出格式

输出一个整数，表示在仙人掌图中移动一条边的方法数。

样例

样例输入 1

6 1
7 1 2 5 6 2 3 4

样例输出 1

42

样例输入 2

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

样例输出 2

216