Problem D
Political Development
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.
Input
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. We always have $0 \leq D_ i < N \leq 50\, 000$, and $1 \leq K \leq 10$.
Output
Output a single integer, the size of the largest possible comittee.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 2 1 2 3 0 2 3 3 0 1 4 2 1 4 2 2 3 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 3 1 2 4 1 0 1 0 0 1 0 |
2 |
