Bao phủ tập hợp
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
recursion
Đề bài
Cho tập vũ trụ $U = {1, 2, \ldots, N}$ và $M$ tập con $S_1, S_2, \ldots, S_M$ của $U$. Tìm số tập con ít nhất trong ${S_1, \ldots, S_M}$ sao cho hợp của chúng bằng $U$. Nếu không thể, in $-1$.
Dữ liệu vào
- Dòng đầu: hai số nguyên $N$ và $M$ $(1 \le N \le 20, 1 \le M \le 20)$.
- $M$ dòng tiếp theo: dòng thứ $i$ bắt đầu bằng $k_i$ (số phần tử của $S_i$), theo sau là $k_i$ số nguyên — các phần tử của $S_i$.
Dữ liệu ra
- Một số nguyên — số tập con ít nhất, hoặc $-1$.
Ví dụ
| Input | Output |
|---|---|
| 5 3\n3 1 2 3\n3 3 4 5\n2 1 5 | 2 |
| 3 2\n1 1\n1 2 | -1 |
Giới hạn
- $1 \le N \le 20$
- $1 \le M \le 20$
Community Discussion