Problem:
 Score : 300 points    Problem Statement 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 .  Bulb 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 .  How many combinations of "on" and "off" states of the switches light all the bulbs?      Constraints  1 \leq N, M \leq 10  1 \leq k_i \leq N  1 \leq s_{ij} \leq N  s_{ia} \neq s_{ib} (a \neq b)  p_i is 0 or 1 .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  k_1  s_{11}  s_{12}  ...  s_{1k_1}  :  k_M  s_{M1}  s_{M2}  ...  s_{Mk_M}  p_1  p_2  ...  p_M       Output Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.        Sample Input 1 2 2
2 1 2
1 2
0 1      Sample Output 1 1   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   There 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 .       Sample Input 2 2 3
2 1 2
1 1
1 2
0 0 1      Sample Output 2 0   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1 .  Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   Switch 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 .       Sample Input 3 5 2
3 1 2 5
2 2 3
1 0      Sample Output 3 8

Solution (Python):
import itertools
N,M = [int(x) for x in input().split()]
d = [[]]*M
for i in range(M):
    s = [int(x) for x in input().split()]
    d[i] = s[1:]
p = [int(x) for x in input().split()]

l = [(0,x) for x in range(1,N+1)]
kumi = itertools.product(*l)
ans = 0

for s in kumi:
    ok = True
    for i in range(M):
        if not ok:
            break
        if len(set(s) & set(d[i]))%2 != p[i]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1::] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    f = True
    bag = []
    jotai = [False for _ in range(M)]
    for j in range(0, N):  
        if (i >> j) & 1:  
            bag.append(j + 1)

    
    
    
    
    
    
    
    
    
    
    

    for s in S:
        total = 0
        for ss in s:
            if ss in bag:
                total += 1
        if total % 2 != P[S.index(s)]:
            f = False
    if f:
        ans += 1
print(ans)

Solution (Python):
i = input().split(" ")

N = int(i[0])
M = int(i[1])

m = []

for _ in range(M):
	i = list(map(int, input().split(" ")))
	m.append(i[1:])

p = list(map(int, input().split(" ")))

from itertools import product

co = 0

s = list(product([True, False], repeat=N))

for comb in s:
	
	allon = True
	for l, b in enumerate(m):
		look = [comb[i - 1] for i in b]
		
		if look.count(True) % 2 != p[l]:
			allon = False
			break
	if allon:
		co += 1

print(co)

Solution (Python):
N, M = map(int,input().split())
SWs = []

from collections import defaultdict
d = defaultdict(list)
for i in range(N):
    d[i+1].append(0)


for i in range(M):
    As = list(map(int,input().split()))
    SWs.append(As[1:])
    for A in As[1:]:
        d[A].append(i+1)


ps = list(map(int,input().split()))
ans = 0


for i in range(2**N):
    light = [0] * (M+1)
    flg = True
    x = bin(i)[2:]
    
    a = "0"*(N-len(x))+x
    for i,s in enumerate(a):
        if int(s) == 0:
            for A in d[i+1]:
                light[A] += 1
    
    for p,l in zip(ps,light[1:]):
        if p != l%2:
            flg = False
    if flg:
        ans += 1

print(ans)

Solution (Python):
import itertools
N, M = (int(i) for i in input().split())

l = [[0] * N for i in range(M)]

for x in range(M):
    s = [int(i) for i in input().split()]
    for ind in range(1, s[0]+1):
        l[x][s[ind]-1] = 1

p = [int(i) for i in input().split()]

res = 0
all = list( itertools.product([0,1], repeat=N))

for pos in all:
    f = True
    for dn in range(M):
        r = 0
        for mm in range(len(pos)):
            r += pos[mm] * l[dn][mm]
            r = r % 2
        if p[dn] != r:
            f = False
    if f :
        res += 1



print(res)

Solution (Python):
from sys import stdin
from numpy import array
from numpy import dot
import itertools


def main():
     n,m = [int(x) for x in stdin.readline().split()]
     A = array([[0]*n for _ in range(m)])
     for i in range(m):
          tmp = [int(x) for x in stdin.readline().split()]
          for j in tmp[1:]:
               A[i][j-1] = 1
     k = array([int(x) for x in stdin.readline().split()])
     swt = [0,1]
     
     ans = 0
     for i in itertools.product(swt, repeat=n):
          i = array(i)
          Ai = dot(A,i)
          if (Ai%2 == k).all():
               ans += 1
     print(ans)
          
     
if __name__ == '__main__':
     main()

Solution (Python):
def solve(n, m, list1, listp):
    cnt = 0
    loopflag = 0
    for i in range(2**n):
        list2 = [(i%(2**(j+1)))//(2**j) for j in range(n)]  
        for j in range(m):  
            s = sum([list2[k] for k in list1[j][1:]])
            if s%2 != listp[j]:
                loopflag = 1
                break
        if loopflag == 0:
            cnt += 1
        loopflag = 0
    return cnt

n, m = map(int, input().split())
list1 = []
for i in range(m):
    list1 += [list(map(int, input().split()))]
    list1[i][1:] = list(map(lambda x: x-1, list1[i][1:]))
listp = list(map(int, input().split()))
print(solve(n, m, list1, listp))

Solution (Python):








ans=0
lis=list(map(int,input().split()))
k=[]
for i in range(lis[1]):
    a=list(map(int,input().split()))
    k.append(a)
p=list(map(int,input().split()))
for i in range(2**lis[0]):
    a=str(bin(2**(lis[0]+1)-i-1))[3:]
    
    for j in range(lis[1]):
        flag=0
        s=0
        for l in range(k[j][0]):
            s+=int(a[k[j][l+1]-1])
        if s%2!=p[j]:
            flag=1
            break
    if flag==0:
        ans+=1


print(ans)

Solution (Python):
n,m = map(int, input().split())
d = dict()
cnt = 0
for i in range(n):
  d[i] = []
for x in range(m):
  s = list(map(int, input().split()))
  for i in s[1:]:
    d[i-1].append(x)
p = list(map(int, input().split()))
for bi in range(2**n):
  l = [0]*m
  for k in range(n):
    if bi & 2**k:
      for x in d[k]:
        l[x] = 1-l[x]
  if l == p:
    cnt += 1
print(cnt)

Solution (Python):
a,b = map(int,input().split())


As=[]
for i in range(b):
    A=list(map(int,input().split()))
    As.append(A)
B=list(map(int,input().split()))

count=0
arr=[]
for i in range(2**a):
    tmp=bin(i)
    tmparr=[int(j) for j in tmp[2:]]
    while len(tmparr)<a:
        tmparr.insert(0,0)
    
    

    for num,j in enumerate(As):
        on=0
        flag=1
        
        for k in j[1:]:
            on=on^tmparr[k-1]
        if  B[num]!=on:
            flag=0
            break
            
            
    if flag==1:
        count+=1
print(count)

Solution (Python):
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

out = 0
for i in range(2 ** n):
    i2 = bin(i)[2:].zfill(n)
    flag = True

    for j in range(m):
        k = int(ks[j][0])
        s = ks[j][1:]
        _p = p[j]

        total = 0
        for _s in s:
            total += int(i2[_s - 1])

        if total % 2 != _p:
            flag = False

    if flag:
        out += 1
print(out)

Solution (Python):
N,M = map(int,input().split(' '))

s = []
for i in [0]*M:
	s.append(list(map(int,input().split(' ')))[1:])

p = list(map(int,input().split(' ')))

bs = []
for t in s:
	rep = 0
	for i in t:
		rep += (1 << (i-1))
	bs.append(rep)

ans = 0
for i in range(0,2**N):
	f = True
	for j,cp in zip(bs,p):
		ch = i & j
		if (bin(ch).count("1") - cp) % 2:
			f = False
			break
	if f:
		ans += 1
print(ans)

Solution (Python):
import itertools

N, M = tuple([int(x) for x in input().split(' ')])

tmp = [[int(x) for x in input().split(' ')] for i in range(M)]
k, s = zip(*[(t[0], t[1:]) for t in tmp])
p = [int(x) for x in input().split(' ')]

pats = itertools.product([0,1], repeat=N)

count = 0
for pat in pats:
    flag = True
    for m in range(M):
        tmp = [pat[ss-1] for ss in s[m]]
        flag = flag and sum([pat[ss-1] for ss in s[m]]) % 2 == p[m]
    if flag:
        count += 1

print(count)

Solution (Python):
import numpy as np

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        eb = np.asarray(e_ball)
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

def transform_sw(sw):
    if sw[0] == 0:
        sw[0] = 1
        return sw
    else:
        sw[0] = 0

    for i, s in enumerate(sw[1:]):
        if s == 0:
            sw[i + 1] = 1
            return sw
        elif s == 1:
            sw[i + 1] = 0
    
    return sw


N, M = map(int, input().split())

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

p = [int(pi) for pi in input().split()]

sw = np.array([0 for _ in range(N)])
cnt = 0

while np.sum(sw == 1) != N:
    if test_switch(e_balls, sw, p):
        cnt += 1
    transform_sw(sw)

if test_switch(e_balls, sw, p):
        cnt += 1

print(cnt)

Solution (Python):
N,M=map(int,input().split())
S=[]
total = 0
for i in range(M):
  iin = list(map(int,input().split()))
  k = iin[0]
  sin = 0
  for j in range(k):
    sin |= 1 << (iin[j+1] - 1) 
  S.append(sin)
p = list(map(int,input().split()))
for i in range(2**N):
  ok = 1
  for j in range(M):
    tmp = i & S[j]
    tmp2 = 0
    for ii in range(10):
      tmp2 += ((tmp >> ii) & 1)
    if (tmp2%2) != p[j]:
      ok = 0
      break
  if ok == 1:
    total += 1
print(total)

Solution (Python):
import itertools
n,m = map(int, input().split())
ks = []
c = 0
for i in range(m):
  ks.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for i in list(itertools.product((0,1), repeat=n)):
  count = 0
  for j in ks:
    if sum([i[j[k+1]-1] for k in range(len(j)-1)]) % 2 == p[ks.index(j)]:
      count += 1
  if count == m:
    c += 1
print(c)

Solution (Python):
def main():
    n, m = map(int, input().split())
    s = []

    for _ in range(m):
        r = [int(x) for x in input().split()]
        s.append(r[1:])
    
    p = [int(s) for s in input().split()]

    print(solve(m, n, s, p))

def solve(m, n, s, p):
    c = 0
    for bits in range(2 ** n):
        for i in range(m):
            if not check(bits, s[i], p[i]):
                break
        else:
            c += 1
    return c

def check(bits, si, pi):
    n = 0
    for sij in si:
        if bits & (1 << (sij - 1)):
            n += 1
    
    if n % 2 == pi:
        return True

    return False


main()

Solution (Python):
N,M=map(int,input().split())
klist = []
slist = []
for i in range(M):
  ks = list(map(int,input().split()))
  klist.append(ks[0])
  slist.append(ks[1:])
plist = list(map(int,input().split()))

cnt = 0
for i in range(2**N):  
  sbin = format(i, '0'+str(N)+'b')
  
  ison = True
  for j in range(M):
    cnt_k = 0
    for sk in slist[j]:
      if sbin[sk-1] == "1":
        cnt_k += 1
      
    if cnt_k%2 != plist[j]:
      ison = False
      break
      
  if ison:
    cnt += 1
    
print(cnt)

Solution (Python):
n,m = map(int,raw_input().split())
switch = []
for i in xrange(m):
	a = map(int,raw_input().split())
	conn = [0]*n
	for x in a[1:]:
		conn[x-1] = 1
	switch.append(conn)
p = map(int,raw_input().split())
res = 0
for i in xrange(2**n):
	temp = i
	lit = [0]*m
	for j in xrange(n):
		if temp%2 == 1:
			for b in xrange(m):
				if switch[b][j]:
					lit[b] += 1
		temp /= 2
	res += 1
	for j in xrange(m):
		if lit[j]%2 != p[j]:
			res -= 1
			break
print res

Solution (Python):
from operator import itemgetter
import itertools

N,M = map(int,input().split())
L = [0]*M
for i in range(M):
  L[i] = list(map(int,input().split()))
P = list(map(int,input().split()))

cnt = 0

for b in list(itertools.product(range(2),repeat = N)):
  flag = 1
  for i in range(M):
    k = L[i][0]
    b_sum = 0
    for j in range(1,k+1):
      b_sum += b[L[i][j]-1]
    if b_sum % 2 != P[i]:
      flag = 0
  if flag == 1:
    cnt += 1
print(cnt)

Solution (Python):
N, M = [int(i) for i in input().split()]
L = [[int(i) - 1 for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]

ans = 0
for i in range(2 ** N):
    su = 0
    for k in range(M):
        count = 0
        for l in L[k][1:]:
            if (i >> l) & 1:
                count += 1
        if count % 2 == P[k]:
            su += 1
    if su == M:
        ans += 1
print(ans)

Solution (Python):
N,M = (int(i) for i in input().split())
s = [[int(i) for i in input().split()] for i in range(M)]
p = [int(i) for i in input().split()]
result2 = 0

for i in range(2 ** N):
    hoge = bin(i + 1)
    hoge = str(hoge)
    hoge = hoge[2:]
    hoge = hoge.zfill(len(str(bin((2 ** N)))) - 2)
    result = True
    for j in range(M):
        onon = 0
        for k in s[j][1:]:
            if hoge[k] == "1":
                onon += 1
        if onon % 2 != p[j]:
            result = False
    if result:
        result2 += 1
print(result2)

Solution (Python):
N, M = [int(i) for i in input().split()]
kss = [ [int(j) for j in input().split()] for i in range(M)]
ps = [int(i) for i in input().split()]

def count_one(s):
    return bin(s).count('1')

all_pat = [i for i in range(2**N)]
masks = [sum([2**(s-1) for s in ks[1:]]) for ks in kss]

res = [sum([1 for i, mask in enumerate(masks) if count_one(pat & mask)%2 == ps[i]]) for pat in all_pat]
print(res.count(M))

Solution (Python):
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))

count = 0
for i in range(2 ** N):
    state = ''.join(list(reversed(str(bin(i))[2:].zfill(N))))
    flg = True
    for m in range(M):
        on = 0
        for s in S[m]:
            if state[s - 1] == '1':
                on += 1
        if on % 2 != P[m]:
            flg = False
            break
    if flg:
        count += 1
print(count)

Solution (Python):
N,M=map(int, raw_input().split())
S=[ map(int, raw_input().split())[1:] for _ in range(M) ] 
P=map(int, raw_input().split())

ans=0
for i in range(2**N):
	for m in range(M):
		tmp=0
		for s in S[m]:
			tmp+=( i>>(N-s) ) & 1

		tmp%=2

		if tmp!=P[m]:
			break
	else:
		ans+=1

print ans

Solution (Python):
N, M = map(int, input().split())

s_list = []

for i in range(M):
    s = list(map(int, input().split()))
    s.pop(0)

    s_list.append(s)

p = list(map(int, input().split()))

on_off_list = [0] * N


def rec(index_on_off):

    if index_on_off == N:

        all_on = True

        for index_m in range(M):

            on_count = 0

            for s_value in s_list[index_m]:
                if on_off_list[s_value - 1] == 1:
                    on_count += 1

            if (on_count % 2) != p[index_m]:
                all_on = False

        if all_on:
            return 1
        else:
            return 0

    counter = 0

    on_off_list[index_on_off] = 0
    counter += rec(index_on_off + 1)

    on_off_list[index_on_off] = 1
    counter += rec(index_on_off + 1)

    return counter


print(rec(0))

Solution (Python):
n,m = map(int, input().split())
dic = []
for i in range(m):
    dic.append(list(map(int, input().split()))[1:])
P = list(map(int, input().split()))
cn = 0
for i in range(2**n):
    b = format(i,"b").rjust(n)
    for j in range(m):
        swcn = 0
        for s in dic[j]:
            swcn += 1 if b[s-1] == "1" else 0
        if swcn%2 != P[j]: break
    else:
        cn += 1
print(cn)

Solution (Python):
N, M = map(int, input().split())
S = []
for _ in range(M):
    s = list(map(int, input().split()))
    S.append(s[1:])
P = list(map(int, input().split()))
SS = [0] * N

ans = 0
for i in range(2**N):
    num = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            SS[j] = 1
    flg = True
    for j, s in enumerate(S):
        num = 0
        for e in s:
            if SS[e-1] == 1:
                num += 1
        if num % 2 != P[j]:
            flg = False
            break
    if flg:
        ans += 1
    SS = [0] * N   
print(ans)

Solution (Python):
n,m=map(int,input().split( ))
line=[]
for i in range(m):
    line.append(list(map(int,input().split( ))))
p_line=list(map(int,input().split( )))

C=0

for i in range(2**n):
    bin_i=format(i,'b')
    l=len(bin_i)
    for j in range(n-l):
        bin_i='0'+bin_i
    bin_i=list(bin_i)
    

    count=0

    for j in range(m):
        check=line[j]
        
        s=0
        for k in range(check[0]):
            s+=int(bin_i[check[k+1]-1])
        s+=p_line[j]
        if s%2==0:
            count+=1
    
    
    if count==m:
        C+=1
        

print(C)

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
import itertools

INF = 10 ** 10


N, M = [int(x) for x in stdin.readline().rstrip().split()]
ks =  [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
p = [int(x) for x in stdin.readline().rstrip().split()] 


nums = [0, 1]
data = list(itertools.product(nums, repeat=N))

ans = 0

for d in data:
    result = True
    for i in range(M):
        k = ks[i][0]
        s = ks[i][1:]

        count = 0
        for ss in s:
            count += d[ss-1]

        if count % 2 != p[i]:
            result = False
            break
    
    if result:
        ans += 1
        
print(ans)

Solution (Python):
N,M = map(int,input().split())
s = []
for i in range(M):
    s += [[int(x) for x in input().split()]]
p = [int(x) for x in input().split()]
ans = 0

for i in range(2**N):
    sw = [(i//2**x)%2 for x in range(N)]
    for j in range(M):
        a = True
        sums = 0
        for k in range(s[j][0]):
            if sw[s[j][k+1]-1] == 1:
                sums += 1
        if sums%2 != p[j]:
            a = False
            break
    if a:   ans += 1

print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())

K = []

for i in range(m):
    l = list(map(int,input().split()))
    K.append(l[1:])
res = 0
p = list(map(int,input().split()))
for s in itertools.product([0,1],repeat=n):
    cnt = [0]*m
    for j in range(len(s)):
        if s[j] == 0:
            continue
        for k in range(len(K)):
            if (j+1) in K[k]:
                cnt[k]+=1
    flag = True

    for j in range(len(cnt)):
        if cnt[j]%2 != p[j]:
            flag = False
            break
    if flag:
        res += 1 
print(res)

Solution (Python):
n,m = map(int,input().split())
A=[list(map(int,input().split())) for i in range(m)]

P=list(map(int,input().split()))
B=[]
for i in range(2**n):
    B.append(format(i,'b').zfill(n))



ans = 0
for i in range(len(B)):
    ok = 1
    for j in range(m): 
        aa = 0
        for k in range(1,len(A[j])):
            if B[i][A[j][k]-1]=="1":
                aa += 1
        
        if aa%2 != P[j]:
            ok=0
    if ok==1:
        ans+=1
print(ans)

Solution (Python):

N,M = list(map(int,input().split(" ")))
denkyus = []
for _ in range(M):
    denkyus.append(list(map(int,input().split(" ")[1:])))

ps  = list(map(int,input().split(" ")))
ans = 0
for i in range(2 ** N):
    temp = [0] * M
    for j in range(0,N): 
        if ((i >> j) & 1): 
            for di,denkyu in enumerate(denkyus):
                if j+1 in denkyu:
                    temp[di] +=1

    for pind,p in enumerate(ps):
        flag = True
        if temp[pind] %2 != p:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):

import sys
INF = float("inf")

MOD = 2  


def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        kk, *rest = map(int, input().split())
        K.append(kk)
        S.append(rest)
    P = list(map(int, input().split()))
    
    

    counter = 0
    for n in range(2**N):    
        flag = True
        
        for k, s, p in zip(K, S, P):
            
            sumof = 0
            for ss in s:
                sumof += (n >> (ss-1))
            sumof %= 2
            if sumof != p:
                flag = False
                break
        if flag:
            counter += 1
    print(counter)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
K = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
ALL = 0
for i in range(2**N):
    state = [((i >> j) & 1) for j in range(N)]
    for j in range(M):
        k = K[j][1:]
        p = sum([int(state[l-1]) for l in k])%2
        if p != P[j]:
            break
    else:
        ALL += 1
print(ALL)

Solution (Python):
N, M = map(int, input().split())
data = []
for x in range(M):
    line = input().split()
    data.append(list(map(int, line[1:])))
turns = list(map(int, input().split()))

def check(i, s, data, turns):
    count_on = 0
    for x in data[i]:
        if s[x - 1] == '1':
            count_on = count_on + 1
    return count_on % 2 == turns[i]

def exec(s, n, data, turns, cases):
    if n == 0:
        ans = True
        for x in range(M):
            if check(x, s, data, turns) == False:
                ans = False
                break
        if ans == True:
            
            cases.append(1)
        return
    for i in range(2):
        exec(s + str(i), n - 1, data, turns, cases)

cases = []
exec('', N, data, turns, cases)
print(len(cases))

Solution (Python):
N, M = map(int, input().split())
S = [[0 for _ in range(N)] for _ in range(M)]

for i in range(M):
    li = list(map(int, input().split()))
    ki = li[0]
    for sij in li[1:]:
        S[i][sij - 1] = 1
P = list(map(int, input().split()))



states = [0 for _ in range(N)]

def dfs(j, jon, states):
    if j == N:
        return 1 if isok(states) else 0
    states[j] = 1 if jon else 0
    count = 0
    count += dfs(j + 1, True, states)
    count += dfs(j + 1, False, states)
    return count

def isok(states):
    for i in range(M):
        x = 0
        for j in range(N):
            x += states[j] if S[i][j] == 1 else 0
        if x % 2 != P[i]:
            return False
    return True

ans = dfs(0, True, states) + dfs(0, False, states)
print(ans // 2)

Solution (Python):
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

N, M = [int(x) for x in input().split(" ")]
Ss = [0] * N
bulbs = []
for i in range(M):
    s = [int(x) for x in input().split(" ")]
    k = s[0]
    ss = set(s[1:])
    bulbs.append(ss)
ps = [int(x) for x in input().split(" ")]
bulbs = list(zip(bulbs, ps))

def checkPattern(subset, bs, p):
    inter = subset.intersection(bs)
    res = len(inter) % 2 == p
    return res

count = 0
for subset in powerset(set(range(1, N+1))):
    subset = set(subset)
    pts = [checkPattern(subset, bs, p) for bs, p in bulbs]
    if all(pts):
        count += 1

print(count)

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
    x=list(map(int,input().split()))
    l.append(x)
p=list(map(int,input().split()))

sum=0
for i in range(2**n):
    sum1=0
    ll = [0] * (n)
    for j in range(n+1):
        if i >> j & 1:
            ll[j] = 1
    for h in range(m):
        k=l[h][0]
        total=0
        for x in range(1,k+1):
            total+=ll[l[h][x]-1]
        if total%2==p[h]:
            sum1+=1
    if sum1==m:
        sum+=1
print(sum)

Solution (Python):
from itertools import combinations
def is_lighted(re):
    for i in range(m):
        total = 0
        for each in ls[i]:
            if each in re:
                total+=1
        if total%2 != p[i]:
            return 0
    return 1

n,m = [int(x) for x in input().split()]
ls = []
ans = 0
for i in range(m):
    ki = [int(x) for x in input().split()]
    ls.append(ki[1:])
p = [int(x) for x in input().split()]

t = [i for i in range(1,n+1)]
for i in range(n+1):
    for each in combinations(t,i):
        if is_lighted(each):
            ans += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

res = 0
for i in range(2**N):
    s = bin(i)[2:].zfill(N)
    l_count = 0
    for p,x in zip(P,X):
        s_count = 0
        for si in x[1:]:
            if s[si-1]=='1':
                s_count += 1
        if s_count%2 == p:
            l_count += 1
    if l_count == M:
        res += 1
print(res)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,m=LI()
  l2=[]
  for _ in range(m):
    l2.append(LI())

  l3=LI()

  l=[]
  a=len(bin(1<<n))-3
  for i in range(1<<n):
    l.append(str(bin(i))[2:].zfill(a))

  cnt=0
  for x in l:
    x=list(x)

    f=True
    for i in range(len(l2)):

      y=l2[i]
      c=0

      for a in y[1:]:
        c+=int(x[a-1])

      
      if c%2==l3[i]:
        pass
      else:
        f=False
        break

    if f:
      cnt+=1

  return cnt

print(main())

Solution (Python):
import itertools
N,M = map(int, input().strip().split(' '))
sw = [[0 for _ in range(M)] for __ in range(N)]
for m in range(M):
  col = list(map(int, input().strip().split(' ')))[1:]
  for i in col:
    sw[i-1][m] = 1
p = list(map(int, input().strip().split(' ')))

ok_count = 0
for c in itertools.product([0,1], repeat=N):
  lamp = [0 for _ in range(M)]
  for i in range(N):
    if c[i]:
      lamp = [l+s for l,s in zip(lamp, sw[i])]
  lamp = [l%2 for l in lamp]
  if lamp == p:
    ok_count += 1
print(ok_count)

Solution (Python):
n,m=map(int,input().split())
x=[]
ans=0
for i in range(m):
    l=list(map(int,input().split()))
    x.append(l)
p=list(map(int,input().split()))
for i in range(2**n):
    frag=True
    for j in range(m):
        count=0
        for a in range(1,x[j][0]+1):
            s=x[j][a]
            count+=(i>>(s-1))&1
        if count%2!=p[j]:
            frag=False
    if frag:
        ans+=1
print(ans)

Solution (Python):



def count1(n):
    return bin(n).count("1")


def tobin(ns):
    rv = 0
    for n in ns:
        rv += 1 << (n-1)
    return rv


def solv(n, m, ss, z1s):
    ss = list(map(tobin, ss))
    ans = 0
    for on in range(2**n):
        
        ok = 1
        for i in range(m):
            
            if count1(ss[i] & on) % 2 != z1s[i]:
                ok = 0
                break
        ans += ok
    return ans


if __name__ == '__main__':

    n, m = map(int, input().split())

    ss = []
    for _ in range(m):
        s = list(map(int, input().split()))
        s = s[1:]
        ss.append(s)

    z1s = list(map(int, input().split()))

    ans = solv(n, m, ss, z1s)
    print(ans)

Solution (Python):
N, M = map(int, input().split())

KS = [list(map(int, input().split()))[1:] for _ in range(M)]

P = list(map(int, input().split()))





ans = 0
for i in range(pow(2, N)):
    bin_i = str(bin(i))[2:]
    if len(bin_i) != N:
        bin_i = '0' * (N - len(bin_i)) + bin_i
    

    

    flg = True
    
    for i, ks in enumerate(KS):
        
        cnt = 0
        for j in ks:
            if bin_i[j-1] == '1':
                cnt += 1
        if cnt % 2 != P[i]:
            flg = False
            break

    if flg:
        ans += 1


print(ans)

Solution (Python):


N, M = map(int, input().split())

S = [list(map(int, input().split())) for i in range(M)]
P = list(map(int, input().split()))

def check_S(state, S, P):
    for s, p in zip(S, P):
        count = 0
        for si in s[1:]:
            if state[si-1] == '1':
                count += 1 
        if count%2 != p:
            return False
    return True

ans = 0
for i in range(2**N):
    state = list(format(i, '0'+format(N)+'b'))
    if check_S(state, S, P):
        ans += 1
print(ans)

Solution (Python):
from collections import *
from functools import *
from itertools import *
import operator as op

def main():
    
    n, m = map(int, input().split())
    
    
    xs = [ list(map(int, input().split()))[1:] for _ in range(m) ]
    ps = list(map(int, input().split()))
    def pick(i, ofst):
        return (i >> ofst) & 1
    ans = 0
    for i in range(2**n):
        if any([ p ^ reduce(op.xor, [ pick(i, x-1) for x in xs[j]]) for j, p in enumerate(ps) ]):
            pass
        else:
            ans += 1
            pass
        pass
    print(ans)
    pass


if __name__ == "__main__":
    main()
    pass

Solution (Python):
n, m = map(int, input().split())
A = []
for i in range(m):
    B = list(map(int, input().split()))
    A.append(B[1:])
P = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    Q = []
    u = i
    for j in range(n):
        Q.append(u%2)
        u//=2
    pop = True
    for j in range(m):
        u = 0 
        for k in A[j]:
            if (Q[-k]==1):
                u+=1
        if ((u%2) != (P[j])):
            pop = False
            
            break
    if (pop):
        ans+=1
print(ans)

Solution (Python):
n,m = list(map(int,input().split()))
k = [0]*m
counter = 0
for i in range(0,m):
    k[i] = list(map(int,input().split()))
p = list(map(int,input().split()))

for h in range(0,2**n):
    c = [0]*n
    for s in range(0,n):
        if (h >> s)% 2 == 1:
            c[s] = 1
    for i in range(0,m):
        check = 0
        for j in range(1,k[i][0]+1):
            if c[k[i][j]-1] == 1:
                check += 1
        if check%2 != p[i]:
            break
    else:
        counter += 1

print(counter)

Solution (Python):

n, m= map(int, input().split())
ks=[]
for i in range(m):
  ks.append(list(map(int, input().split())))
p= list(map(int, input().split()))
k=[0]*n
count=0
for i in range(2**n):
  for j in range(n):
    k[j]=i%2
    i=i//2
  for a in range(m):
    sm=0
    for j in range(ks[a][0]):
      sm = sm + k[ks[a][j+1]-1]
    if sm%2 != p[a]:
      break
  else:
    count = count + 1
print(count)

Solution (Python):




N, M = [int(x) for x in input().split()]

S = [[0] * N for _ in range(M)]
for m in range(M):
    s = [int(x) for x in input().split()]
    for s1 in s[1:]:
        S[m][s1 - 1] = 1

P = [int(x) for x in input().split()]

cnt = 0
for i in range(2 ** N):
    tmp = True
    for j in range(M):
        c = 0
        for k in range(N):
            if i & (1 << k):
                c += S[j][k]

        if c % 2 != P[j]:
            tmp = False

        
        
    

    if tmp == True:
        cnt += 1

print(cnt)