{"raw_statement":[{"iden":"problem statement","content":"There are $M$ sets, called $S_1, S_2, \\dots, S_M$, consisting of integers between $1$ and $N$.  \n$S_i$ consists of $C_i$ integers $a_{i, 1}, a_{i, 2}, \\dots, a_{i, C_i}$.\nThere are $(2^M-1)$ ways to choose one or more sets from the $M$ sets.  \nHow many of them satisfy the following condition?\n\n*   For all integers $x$ such that $1 \\leq x \\leq N$, there is at least one chosen set containing $x$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10$\n*   $1 \\leq M \\leq 10$\n*   $1 \\leq C_i \\leq N$\n*   $1 \\leq a_{i,1} \\lt a_{i,2} \\lt \\dots \\lt a_{i,C_i} \\leq N$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$C_1$\n$a_{1,1}$ $a_{1,2}$ $\\dots$ $a_{1,C_1}$\n$C_2$\n$a_{2,1}$ $a_{2,2}$ $\\dots$ $a_{2,C_2}$\n$\\vdots$\n$C_M$\n$a_{M,1}$ $a_{M,2}$ $\\dots$ $a_{M,C_M}$"},{"iden":"sample input 1","content":"3 3\n2\n1 2\n2\n1 3\n1\n2"},{"iden":"sample output 1","content":"3\n\nThe sets given in the input are $S_1 = \\lbrace 1, 2 \\rbrace, S_2 = \\lbrace 1, 3 \\rbrace, S_3 = \\lbrace 2 \\rbrace$.  \nThe following three ways satisfy the conditions in the Problem Statement:\n\n*   choosing $S_1, S_2$;\n*   choosing $S_1, S_2, S_3$;\n*   choosing $S_2, S_3$."},{"iden":"sample input 2","content":"4 2\n2\n1 2\n2\n1 3"},{"iden":"sample output 2","content":"0\n\nThere may be no way to choose sets that satisfies the conditions in the Problem Statement."},{"iden":"sample input 3","content":"6 6\n3\n2 3 6\n3\n2 4 6\n2\n3 6\n3\n1 5 6\n3\n1 3 6\n2\n1 4"},{"iden":"sample output 3","content":"18"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}