시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

A certain political party with N members wants to develop some brand new politics. In order to do so, the party plans to make a committee for new political development. Clearly, the best politics is developed when all committee members disagree with each other, and when the committee is as large as possible.

In order to figure out which pairs of politicians disagree and which don’t, the party then arranged for every possible pair of politicians to discuss a randomly selected topic. Whenever two politicians couldn’t agree on their assigned topic, this was recorded in the party’s Book of Great Achievements.

Armed with this book, you have now been assigned the task of finding the largest comittee where everyone disagrees. However, finding a large comittee can prove challenging; careful analysis have revealed that for any non-empty group of party members, there is always at least one member of the group who disagrees with (strictly) less than K of the other group members. Obviously, then, the committee can not have more than K members. But is there a choice of committee of this size? Find the size of a largest possible committe such that nobody in that committee agrees.

입력

The first line contains two integers, N the number of members in the party, and K as described above. Each member is indicated by an integer i between 0 and N − 1. After the first line follow N lines, one for each politician i, starting with i = 0. The line for politician i begins with an integer Di, and is followed by Di integers indicating with which other party members the i-th politician disagrees according to the Book of Great Achievements.

출력

Output a single integer, the size of the largest possible comittee.

제한

We always have 0 ≤ Di < N ≤ 50 000, and 1 ≤ K ≤ 10. For subcases, the inputs have these further restrictions.

서브태스크

번호 배점 제한
1 4

K ≤ 2, N ≤ 5 000

2 12

K ≤ 3, N ≤ 5 000

3 23

Each party member disagrees with at most 10 other members.

4 38

N ≤ 5000

5 23

K ≤ 5

예제 입력 1

5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3

예제 출력 1

3

예제 입력 2

5 3
3 1 2 4
1 0
1 0
0
1 0

예제 출력 2

2

채점 및 기타 정보

  • 예제는 채점하지 않는다.