题目描述

NH 的最大比萨店为即将来临的节日准备了 T 种不同加味的原料，但考虑到 NH 人的口味和其它一些因素，原料的使用有 N 种限制。

T 种不同原料的编号为 1~T 。一个限制如 “5 3” 即表示 5 号和 3 号加味原料不能同时使用。如此，此时使用三种原料 3,5,6 的比萨是不允许的。

现在请你帮忙计算在上面条件下，最多可以制作多少不同的比萨（包括不添加任何加味原料的）。

输入格式

第一行：两个整数：T 和 N 。

下面有 N 行：每行表示一种限制。每行的第一个整数 Z( 1 ≤ Z ≤ T )表示这行后面有 Z 个表示原料编号的整数，这些原料不能同时出现在一个比萨中。

数据范围

1 ≤ T ≤ 20

1 ≤ N ≤ 52

输出格式

只一行，一个整数表示在上面的限制下最多可以制成多少种不同比萨。

样例

6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6

10

样例解释

无加料；2；

2 和 3 ；2 和 6 ；

3 ；3 和 4 ；

3 和 6 ；4 ；

4 和 6 ；6 。