{"raw_statement":[{"iden":"problem statement","content":"We have $N$ switches with \"on\" and \"off\" state, and $M$ bulbs. The switches are numbered $1$ to $N$, and the bulbs are numbered $1$ to $M$.\nBulb $i$ is connected to $k_i$ switches: Switch $s_{i1}$, $s_{i2}$, $...$, and $s_{ik_i}$. It is lighted when the number of switches that are \"on\" among these switches is congruent to $p_i$ modulo $2$.\nHow many combinations of \"on\" and \"off\" states of the switches light all the bulbs?"},{"iden":"constraints","content":"*   $1 \\leq N, M \\leq 10$\n*   $1 \\leq k_i \\leq N$\n*   $1 \\leq s_{ij} \\leq N$\n*   $s_{ia} \\neq s_{ib} (a \\neq b)$\n*   $p_i$ is $0$ or $1$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$k_1$ $s_{11}$ $s_{12}$ $...$ $s_{1k_1}$\n$:$\n$k_M$ $s_{M1}$ $s_{M2}$ $...$ $s_{Mk_M}$\n$p_1$ $p_2$ $...$ $p_M$"},{"iden":"sample input 1","content":"2 2\n2 1 2\n1 2\n0 1"},{"iden":"sample output 1","content":"1\n\n*   Bulb $1$ is lighted when there is an even number of switches that are \"on\" among the following: Switch $1$ and $2$.\n*   Bulb $2$ is lighted when there is an odd number of switches that are \"on\" among the following: Switch $2$.\n\nThere are four possible combinations of states of (Switch $1$, Switch $2$): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print $1$."},{"iden":"sample input 2","content":"2 3\n2 1 2\n1 1\n1 2\n0 0 1"},{"iden":"sample output 2","content":"0\n\n*   Bulb $1$ is lighted when there is an even number of switches that are \"on\" among the following: Switch $1$ and $2$.\n*   Bulb $2$ is lighted when there is an even number of switches that are \"on\" among the following: Switch $1$.\n*   Bulb $3$ is lighted when there is an odd number of switches that are \"on\" among the following: Switch $2$.\n\nSwitch $1$ has to be \"off\" to light Bulb $2$ and Switch $2$ has to be \"on\" to light Bulb $3$, but then Bulb $1$ will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print $0$."},{"iden":"sample input 3","content":"5 2\n3 1 2 5\n2 2 3\n1 0"},{"iden":"sample output 3","content":"8"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}