Devu and Nicky

All submissions for this problem are available.
Today is the Swayamvar of Nicky, the daughter of Chef. To win the swayamvar participants needs to solve the Problem of DIV.
Problem of Div is described as follows:
Initially the participants will be given N names (length of name be LEN) and K sets of names. Now lets say we can write N names in a set S = {name1, name2, ..., nameN}, also this set can be written in the form as R = {R1, R2,...,Rj} such that R1 U R2... U Rj = S. Ri and Rj are mutually disjoint sets.
Each participant need to answer the number of ways of forming R, such that neither of the K sets are the subsets of any Ri in R. (see the explanation for more clarity).
Devu a friend of yours is participating in the swayamvar. He needs your help in solving the problem of DIV. Help Devu in winning the swayamvar and getting married to Nicky.
Use BigInt library as the answer can be large.
Input
 First line contains T the number of test cases.
 The first line of each test case contains two spaceseparated integers N and K.
 Next line contains N names.
 Each of the next 2*K lines contains the following:
first line L the number of names in the set; second line contains L names in that set.
Output
 For each test case solve the problem of DIV and print the required answer.
Constraints and Subtasks
 1 <= T <= 5
 1 <= N <= 100
 1 <= K, LEN <= 10
 1 <= L <= N
 Each of the name in K sets are from the N names
Subtask 1: 5 points
 1<=N<=5
 1<=K<=3
Subtask 2: 10 points
 1<=N<=25
 1<=K<=5
Subtask 3: 85 points
 original constraints.
Example
Input: 2 3 2 a b cd 2 a b 3 a b cd 3 2 a b cd 2 a b 1 a Output: 3 0
Explantion
We can split a b cd in the following ways. 1: {{a}, {b}, {cd}} 2: {{a, b}, {cd}} 3: {{a, cd}, {b}} 4: {{a}, {b, cd}} 5: {{a, b, cd}} Case :1 as 2, 5 contains {a, b} and 5 contains {a, b, cd}, they must not be counted. Hence the answer is 3. Case :2 as 2, 5 contains {a, b} and 1,2,3,4,5 contains {a}, they must not be counted. Hence the answer is 0.
Author:  adi28galaxyak 
Tags  adi28galaxyak 
Date Added:  30012016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 