Problem4346--Victoria的舞会 I

4346: Victoria的舞会 I

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Victoria 是一位颇有成就的艺术家,他因油画作品《我爱北京天安门》闻名于世界。现在,他为了报答帮助他的同行们,准备开一个舞会。
Victoria 准备邀请 $n$ 个已经确定的人,可是问题来了:
这 $n$ 个人每一个人都有一个小花名册,名册里面写着他所愿意交流的人的名字。比如说在 $A$ 的人名单里写了 $B$,那么表示 $A$ 愿意与 $B$ 交流;而且如果 $A$ 名单里面有 $B$,那么 $B$ 名单里面肯定有 $A$,也就是说两个人如果一方愿意和另一方交流,那么另一方也肯定愿意和这一方交流。
Victoria 觉得需要在这 $n$ 个人里面确定 $m$ 个人,保证这 $m$ 个人每一个人都能在舞会的 $n$ 个人中找到至少 $k$ 个人交流,并求出一种方案以确定 $m$ 的最大值是多少。
注意:自己的名单里面不会有自己的名字。

Input

第一行两个数 $n,\ k\ (1 \leq n,\ k \leq 200)$。
接下来 $n$ 行,每 $i+1$ 行表示编号为i的人的小花名册名单,名单以 $0$ 结束。

Output

一个数,$m$。

Sample 1 Input

22 1
4 5 10 11 20 21 0
2 3 6 8 11 16 0
2 3 5 8 12 15 16 18 0
1 5 6 10 11 12 16 18 0
1 3 4 16 20 0
2 4 19 21 22 0
8 9 13 19 20 0
2 3 7 10 19 0
7 10 14 16 19 0
1 4 8 9 10 20 0
1 2 4 18 19 20 21 0
3 4 13 0
7 12 15 16 18 19 21 22 0
9 16 0
3 13 21 0
2 3 4 5 9 13 14 20 0
18 22 0
3 4 11 13 17 21 0
6 7 8 9 11 13 19 21 22 0
1 5 7 10 11 16 21 22 0
1 6 11 13 15 18 19 20 0
6 13 17 19 20 0

Sample 1 Output

22

HINT

题目来源:Vijos 1021

Source/Category