Đếm tập hợp

Xem PDF

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) tập hợp \(A_1,A_2,...,A_n\) biết rằng, tất cả các phần tử trong mỗi tập hợp đã cho đều thuộc đoạn \([1;m]\) và các phần tử trong mỗi tập hợp đều khác nhau từng đôi một !

Yêu cầu: Hỏi ta có thể tạo thành được bao nhiêu tập hợp khác nhau bằng cách lấy một vài tập hợp từ \(n\) tập hợp đã cho hợp lại với nhau.

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số testcase

  • \(t\) block tiếp theo, mỗi block có dạng như sau:

    • Dòng thứ nhất chứa hai số nguyên \(n,m(1\le n\le 100,1\le m\le 14)\)

    • \(n\) dòng tiếp theo, mỗi dòng gồm \(k+1(k\le m)\) số nguyên trong đó: Phần tử đầu tiên thể hiện số lượng phần tử của tập hợp \(A_i\)\(k\) phần tử tiếp theo - thể hiện các phần tử của tập \(A_i\)

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

Test 1

Input
2
2 3
1 1
2 1 3
2 4
2 2 3
2 1 4
Output
2
3
Note
  • Ứng với testcase 1, ta chỉ có thể tạo ra được 2 tập khác nhau đó là: \(\left\{1\right\}\) ; \(\left\{1,3\right\}\)

  • Ứng với testcase 2, ta chỉ có thể tạo ra được 3 tập khác nhau đó là: \(\left\{2,3\right\}\) ; \(\left\{1,4\right\}\) ; \(\left\{1,2,3,4\right\}\)


Bình luận

Không có bình luận nào.