2296: 联谊寝室
内存限制:256 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:2
解决:1
题目描述
Metro同学迎来了他的大学生活,他发现第一件遇到的奇葩事就是联谊寝室。。
现在有n个男生宿舍和m个女生宿舍,为了完成喜(sang)闻(xin)乐(bing)见(kuang)的配对活动,需要尽可能多的将男生宿舍和女生宿舍一一对应。换句话说,每个男生宿舍都至多只能和一个女生宿舍配对,每个女生宿舍也至多只能和一个男生宿舍配对。
男生们提前得到了这个消息,于是每个男生宿舍都去考察了所有女生宿舍(大丧失。。)
现在对于每个男生宿舍,他们都有一个期望配对的女生宿舍列表,而作为辅导员同学,要做的事就是尽可能满足男生们的奇(he)怪(li)需求了。那么,最多有多少个宿舍可以成功配对呢?要知道男生们宁可没有女生宿舍与之配对,也不想选择不喜欢的宿舍呢。。
输入
第一行为两个正整数n, m, 分别代表男生宿舍和女生宿舍的数量。
接下来的n行,每行的第一个正整数ki表示i号男生宿舍期望的女生宿舍的个数。后面的ki个整数,分别表示i号男生宿舍期望与之配对的女生宿舍号。
输出
输出为一个非负整数,表示成功配对的寝室对数。
样例输入 复制
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
样例输出 复制
4
提示
n, m <= 1000000,所有男生宿舍期望的女生宿舍的总数不超过1000000。