Baltic Olympiad in Informatics: 2017 Day 1, Problem 1

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 committee where everyone disagrees. However, finding a large committee 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 committee such that nobody in that committee agrees.

Input Specification

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 ~D_i~, and is followed by ~D_i~ integers indicating with which other party members the ~i~th politician disagrees according to the Book of Great Achievements.

Constraints

We always have ~0 \le D_i < N \le 50\,000~, and ~1 \le K \le 10~. For subcases, the inputs have these further restrictions:

• Group 1: 4 points ~K \le 2,N \le 5\,000~
• Group 2: 12 points ~K \le 3, N \le 5\,000~
• Group 3: 23 points Each party member disagrees with at most ~10~ other members.
• Group 4: 38 points ~N \le 5\,000~
• Group 5: 23 points ~K \le 5~

Output Specification

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

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

2