Farmer John tổ chức một bữa tiệc và muốn mời một số con bò của mình để cho chúng thấy ông quan tâm đến đàn bò đến nhường nào. Tuy nhiên, ông cũng muốn mời số lượng bò ít nhất có thể, bởi ông vẫn nhớ rất rõ thảm họa xảy ra trong lần gần nhất ông mời quá nhiều bò đến dự tiệc.

Trong đàn bò của FJ, có một số nhóm bạn rất khó tách rời. Với bất kỳ nhóm nào như vậy (giả sử có kích thước \(k\)), nếu FJ mời ít nhất \(k-1\) con bò trong nhóm đến dự tiệc thì ông cũng phải mời con bò cuối cùng, qua đó mời toàn bộ nhóm. Các nhóm có thể có kích thước bất kỳ và thậm chí có thể giao nhau, mặc dù không có hai nhóm nào chứa chính xác cùng một tập hợp thành viên. Tổng kích thước của tất cả các nhóm không vượt quá \(250\,000\).

Cho các nhóm trong đàn bò của FJ, hãy xác định số lượng bò tối thiểu mà FJ có thể mời đến bữa tiệc nếu ông quyết định rằng trước tiên chắc chắn phải mời bò số \(1\) (các con bò được đánh số thuận tiện từ \(1\) đến \(N\), với \(N\) không vượt quá \(1\,000\,000\)).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) (số lượng bò) và \(G\) (số lượng nhóm), cách nhau bởi dấu cách.
• \(G\) dòng tiếp theo, mỗi dòng mô tả một nhóm bò. Dòng bắt đầu bằng một số nguyên cho biết kích thước \(S\) của nhóm, theo sau là \(S\) con bò trong nhóm (mỗi con được biểu diễn bằng một số nguyên trong khoảng từ \(1\) đến \(N\)).

Dữ liệu ra

In ra số lượng bò tối thiểu mà FJ có thể mời đến bữa tiệc.

Ví dụ

10 4
2 1 3
2 3 4
6 1 2 3 4 6 7
4 4 3 2 1

4

Nguồn

USACO 2013 January Contest, Silver — Problem 3: Party Invitations

Tác giả đề: Travis Hance, 2012.