Đàn bò muốn lập đội thám hiểm khu rừng ở rìa đất của Farmer John. Thám hiểm cần nhiều kỹ năng hơn đứng trong đồng cỏ và gặm cỏ.
Đội gồm $C$ con bò ($1 \le C \le 20$) đánh số 1..$C$ cần bò biết tìm đường không lạc, đẩy lùi sinh vật to lớn hung dữ, kể chuyện cười nâng tinh thần, v.v. Mỗi khả năng đặc biệt trong $A$ khả năng ($1 \le A \le 20$), đánh số 1..$A$, phải được ít nhất một bò trong đội có. Một số có một khả năng, nhiều con có nhiều, và vài con chỉ ăn bám hoàn toàn vô dụng.
Cho tất cả bò và khả năng mỗi con, đếm số đội thám hiểm khác nhau mà cả đội có mọi khả năng được cho.
Dữ liệu vào
- Dòng 1: hai số nguyên $C$ và $A$.
- Các dòng 2..$A$+1: mỗi dòng mô tả một khả năng bằng các số nguyên cách nhau bởi dấu cách. Dòng 2 là khả năng 1, dòng 3 là khả năng 2, v.v. Số đầu $K$ ($1 \le K \le C$) là số bò có khả năng đó. $K$ số tiếp theo biểu thị những con bò ấy.
Dữ liệu ra
- Dòng 1: số nguyên là số đội thám hiểm khác nhau có thể lập.
Ví dụ
Dữ liệu vào 1
4 2 2 3 1 1 2
Dữ liệu ra 1
6
Ghi chú
Chi tiết dữ liệu vào
Có 4 bò và 2 khả năng. Bò 1 và 3 có khả năng 1, chỉ bò 2 có khả năng 2. Bò 4 tương đối không có tài.
Chi tiết dữ liệu ra
Các đội có thể là $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$ và $\{1, 2, 3, 4\}$.
Tác giả bài toán: Percy Liang, 2004