|
Лимит времени 1500/1000/1000/1000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
Given a set of elements U = {1, 2, ..., n} and K subsets of set U. Identify the smallest number of sets whose union still contains all elements in the U. For example, assume we are given the following elements U = {1, 2, 3, 4, 5} and sets {1, 2, 3}, {2, 4}, {3, 4}, {4, 5}. We can cover all of the elements with the following sets: {1, 2, 3} and {4, 5}.
Input
There are two integers N and K on the first line of input (1 ≤ N ≤ 20, 1 ≤ K ≤ 50).
Next K lines contain information about subsets. The first number si in each line - number of elements in subset, then si integers - elements of subset.
Output
Write the minimum number of subsets required to cover U.
Example
| stdin |
stdout |
|
5 4
3 1 2 3
2 4 2
2 3 4
2 4 5
|
2 |
Для отправки решений необходимо выполнить вход.
|