题目描述

XX 被布置了 $m$ 道作业题，可是他一道也不会......但他知道有 $n$ 位高手，并知道每位高手会做哪些题，请问 XX 至少请多少位高手才能把所有的题都做出来？

输入输出格式

输入

第一行两个整数 $m,n$ 表示有 $m$ 道作业题和 $n$ 位高手，作业题以 $1...m$ 编号； 接下来 $n$ 行，第 $i+1$ 行第一个数 $l_i$ 表示第 $i$ 位高手会做的题目的数量，接下来 $l_i$ 个数表示第 $i$ 位高手会做哪些题目。

输出

一个数,XX至少要请多少位高手?

样例

输入1

4 4
2 1 2
1 4
3 2 3 4
2 1 3

输出1

2

数据范围

对于 40% 的数据，$3<=m$, $n<=10$ 对于 100% 的数据，$3<=m$, $n<=60$, $1<=l_i<=6$

提示

搜索是基础算法.虽然近几年中NOIP搜索题占的比率并不大,但是在考试临近结束时,或者有题不会时,写一个简单的搜索程序往往会带来意想不到的结果.比如去年的金明的预算方案,有很多大牛虽然写了DP但是某一个小细节处理错了,0分;那些写搜索的反而至少能得40-50分,加几条剪枝甚至能达到80-90分.可见搜索在实战中的作用.

这道题朴素搜索想不超时很难，需加几条剪枝才可全过:

1 可行性剪枝,如果当前选择的高手的数量已经大于等于当前最优解的数量,剪.这也是最基础,最简单,但却是最实用的剪枝之一. 2 重复数据 数据中不可避免地会出现某一个高手会做的题目,有另外一个高手全会做的情况.这种情况下,这个高手就不需要了,因为它完全可以被另外那个高手取代. 3 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决。