{"problem":{"name":"Coverage","description":{"content":"There are $M$ sets, called $S_1, S_2, \\dots, S_M$, consisting of integers between $1$ and $N$.   $S_i$ consists of $C_i$ integers $a_{i, 1}, a_{i, 2}, \\dots, a_{i, C_i}$. There are $(2^M-1)$ ways to c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc289_c"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc289_c","tags":[],"sample_group":[["3 3\n2\n1 2\n2\n1 3\n1\n2","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$."],["4 2\n2\n1 2\n2\n1 3","0\n\nThere may be no way to choose sets that satisfies the conditions in the Problem Statement."],["6 6\n3\n2 3 6\n3\n2 4 6\n2\n3 6\n3\n1 5 6\n3\n1 3 6\n2\n1 4","18"]],"created_at":"2026-03-03 11:01:14"}}