Một đảng chính trị có \(N\) thành viên muốn xây dựng những chính sách hoàn toàn mới. Để làm điều đó, đảng dự định thành lập một ủy ban phát triển chính sách mới. Rõ ràng, những chính sách tốt nhất được xây dựng khi mọi cặp thành viên trong ủy ban đều bất đồng với nhau, và khi ủy ban có càng nhiều thành viên càng tốt.

Để xác định những cặp chính trị gia nào bất đồng và những cặp nào không, đảng đã bố trí cho mọi cặp chính trị gia thảo luận về một chủ đề được chọn ngẫu nhiên. Mỗi khi hai chính trị gia không thể thống nhất về chủ đề được giao, điều đó được ghi lại trong Sổ Những Thành Tựu Vĩ Đại của đảng.

Với cuốn sổ này, bạn được giao nhiệm vụ tìm ủy ban lớn nhất mà mọi cặp thành viên đều bất đồng với nhau. Tuy nhiên, việc tìm một ủy ban lớn có thể không dễ dàng: qua phân tích kỹ lưỡng, người ta nhận thấy rằng với mọi nhóm không rỗng gồm các thành viên của đảng, luôn tồn tại ít nhất một người trong nhóm bất đồng với ít hơn \(K\) người khác trong chính nhóm đó. Vì vậy, ủy ban không thể có nhiều hơn \(K\) thành viên. Nhưng liệu có thể chọn được một ủy ban có đúng số thành viên này hay không? Hãy tìm số thành viên lớn nhất của một ủy ban mà không có hai người nào đồng ý với nhau.

Ảnh: Federal Open Market Committee, Federal Reserve Bank of Philadelphia, qua Wikimedia Commons; CC0, thuộc phạm vi công cộng.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\): số thành viên trong đảng và giá trị \(K\) được mô tả ở trên. Các thành viên được đánh số từ \(0\) đến \(N-1\).

Tiếp theo là \(N\) dòng, lần lượt ứng với các chính trị gia \(i=0,1,\ldots,N-1\). Dòng của chính trị gia \(i\) bắt đầu bằng số nguyên \(D_i\), theo sau là \(D_i\) số nguyên chỉ những thành viên khác mà người này bất đồng, theo Sổ Những Thành Tựu Vĩ Đại.

Dữ liệu ra

In ra một số nguyên: số thành viên lớn nhất có thể có trong ủy ban.

Ràng buộc

• \(0 \le D_i < N \le 50\,000\) với mọi \(0 \le i < N\).
• \(1 \le K \le 10\).
• Với mọi nhóm không rỗng gồm các thành viên của đảng, có ít nhất một người bất đồng với ít hơn \(K\) người khác trong nhóm đó.

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (4 điểm): \(K \le 2\) và \(N \le 5\,000\).
• Nhóm 2 (12 điểm): \(K \le 3\) và \(N \le 5\,000\).
• Nhóm 3 (23 điểm): Mỗi thành viên của đảng bất đồng với nhiều nhất \(10\) thành viên khác, tức là \(D_i \le 10\) với mọi \(0 \le i < N\).
• Nhóm 4 (38 điểm): \(N \le 5\,000\).
• Nhóm 5 (23 điểm): \(K \le 5\).

Ví dụ

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

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 1.