Description

A political party with $n$ members wants to develop some brand-new policies. To do this, the party plans to set up a committee for developing the new policies. Clearly, policies can be developed best when all committee members disagree with each other, and the committee is as large as possible.

To find out which pair of politicians disagree and which pair agree, the party arranges for every possible pair of politicians to discuss a randomly chosen topic. Whenever two politicians cannot reach an agreement on the given topic, they are recorded in the party’s book of merits.

With this book, you are assigned the task of finding the largest committee such that all members disagree with each other. However, finding a large committee is very challenging. Careful analysis of the results shows that for any non-empty subgroup of party members, there exists at least one member in the subgroup who disagrees with strictly fewer than $k$ other members in the subgroup. Therefore, the committee cannot have more than $k$ members. But can we choose a committee of this size? Find the maximum size of a committee in which no two members agree.

One-sentence summary:

Given a graph such that for any induced subgraph, there exists a vertex with degree less than $k$, find the maximum clique of the original graph.

Input Format

The first line contains two integers $n$ and $k$, where $n$ is the number of vertices and $k$ is as described above.
Each vertex is represented by an integer $i$ between $0$ and $n-1$.
The next $n$ lines describe vertices $i$, starting from $i = 0$.
Line $i$ begins with an integer $d_i$, followed by $d_i$ integers representing the vertices adjacent to vertex $i$.

Output Format

Output one line containing a single integer, the size of the maximum clique of the original graph.

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

3

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

2

Hint

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (4 pts): $k \le 2$, $n \le 5 \times 10^3$.
• Subtask 2 (12 pts): $k \le 3$, $n \le 5 \times 10^3$.
• Subtask 3 (23 pts): $d_i \le 10$.
• Subtask 4 (38 pts): $n \le 5 \times 10^3$.
• Subtask 5 (23 pts): $k \le 5$.

For $100\%$ of the testdata, $0 \le d_i < n \le 5 \times 10^4$, $1 \le k \le 10$.

Notes

Translated from BOI 2017 D1 T1 Political Development.
Translator:

Translated by ChatGPT 5