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(i) for i in input().split()]
s = []
for i in range(m):
    _, *s_ = [int(i) for i in input().split()]
    s.append(s_)
p = [int(i) for i in input().split()]

answer = 0
for i_list in itertools.product([0,1],repeat=n):

    電気点灯 = 0
    for j in range(m):
        オンになっているスイッチの個数 = 0
        for k in range(len(s[j])):
            if i_list[s[j][k]-1] == 1:
                オンになっているスイッチの個数 += 1
        if オンになっているスイッチの個数 % 2 == p[j]:
            電気点灯 += 1

    if 電気点灯 == m:
        answer += 1

print(answer)

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

ans = 0
for i in range(1 << N):
  tmp = 1
  for j, b in enumerate(KS):
    if sum([1 for bb in b[1:] if (i >> (bb - 1)) & 1 == 1])%2 != P[j]:
      tmp = 0
      break
  if tmp:
    ans += 1
print(ans)

Solution (Python):
import copy

N, M = map(int, input().split())
L = []

for i in range(M):
    k = list(map(int, input().split()))
    l = [i-1 for i in k[1:]]  
    L.append(l)

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


def calc(idx, lampe):
    if idx == N:
        ans = 0
        for l in range(M):
            if sum([lampe[v] for v in L[l]]) % 2 != p[l]:
                return 0

        return 1

    ans = 0
    ans += calc(idx+1, lampe)
    lampe2 = copy.copy(lampe)
    lampe2[idx] = 1
    ans += calc(idx+1, lampe2)
    return ans


ans = calc(0, [0]*N)
print(ans)

Solution (Python):
import itertools
import copy

N, M = map(int, input().split())
L = []

for i in range(M):
    k = list(map(int, input().split()))
    l = [i-1 for i in k[1:]]  
    L.append(l)

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


def calc(idx, lampe):
    if idx == N:
        ans = 0
        for l in range(M):
            s = [lampe[v] for v in L[l]]
            if sum(s) % 2 != p[l]:
                return 0

        return 1

    ans = 0
    ans += calc(idx+1, lampe)
    lampe2 = copy.copy(lampe)
    lampe2[idx] = 1
    ans += calc(idx+1, lampe2)
    return ans


ans = calc(0, [0]*N)
print(ans)

Solution (Python):
import itertools

n, m = [int(i) for i in input().split()]
s = []
for i in range(m):
    _, *s_ = [int(i) for i in input().split()]
    s.append(s_)
p = [int(i) for i in input().split()]

answer = 0
for i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10 in itertools.product(range(2), range(2), range(2),range(2), range(2), range(2),range(2), range(2),range(2), range(2), range(2)):
    
    i_list = [i10, i9, i8, i7, i6, i5, i4, i3, i2, i1, i0]
    
    if i_list[n] == 1:
        break

    電気点灯 = 0
    for j in range(m):
        オンになっているスイッチの個数 = 0
        for k in range(len(s[j])):
            if i_list[s[j][k]-1] == 1:
                オンになっているスイッチの個数 += 1
        if オンになっているスイッチの個数 % 2 == p[j]:
            電気点灯 += 1

    if 電気点灯 == m:
        answer += 1

print(answer)

Solution (Python):
import itertools

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

s= []


for i in range(m):
	ss = list(map(int, input().split()))
	temp_ss = []
	for i in range(1, len(ss)):
		temp_ss.append(ss[i]-1)
	s.append(temp_ss)
p = list(map(int, input().split()))

ans = 0





for c in itertools.product([0,1], repeat=n):
	
	is_ans = True
	for i in range(len(s)):
		if(sum([c[a] for a in s[i]])) % 2 != p[i]:
			is_ans = False
			break

	if(is_ans):
		ans += 1
print(ans)

Solution (Python):


N, M = map(int, input().split())
lights = [list(map(int, input().split()[1:])) for i in range(M)]
p = list(map(int, input().split()))

combi = 0
for i in range(1<<N):
    flag = True
    for j, switch in enumerate(lights):
        if sum([1 for s in switch if (i>>(s-1)) & 1 == 1])%2 != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Solution (Python):

N,M = map(int,input().split())
K = []
S = []
for i in range(M):
    ks =list(map(int,input().split()))
    ss = []
    kk = ks[0]
    K.append(kk)
    for j in range(kk):
        ss.append(ks[j+1])
    
    S.append(ss)
P = list(map(int,input().split()))
Bit = 2**N
ans = 0
for i in range(Bit):
    b = bin(i)
    b = b.lstrip("0b")
    lenb = len(b)
    j = 0
    for j in range(N-lenb):
        b = "0"+b
        
    sw = []
    j = 0

    for j in range(N):
        if b[j] == "1":
            sw.append(1)
        else:
            sw.append(0)
    
    j = 0
    flag = 0
    for j in range(M):
        cond = P[j]
        now = 0
        for k in range(K[j]):
            now+=sw[S[j][k]-1]
            
        if now%2 == cond:
            pass
        else:
            flag = 1
            break
            
    if flag == 0:
        ans+=1
    
print(ans)

Solution (Python):
N, M = map(int, input().split())
dict = {}
for i in range(M):
    l = list(map(int, input().split()))
    for j in range(l[0]):
        if l[j+1] in dict:
            dict[l[j+1]].append(i)
        else:
            dict[l[j+1]] = [i]
ps = list(map(int, input().split()))
n = 1 << N
ans = 0
while n:
    cnt = 0
    ks =[0]*M
    for i in range(N):
        if n >> i & 1:
            if i+1 in dict:
                for k in dict[i+1]:
                    ks[k] += 1
    for j in range(M):
        if ks[j] % 2 == ps[j]:
            cnt += 1
    if cnt == M:
        ans += 1
    n -= 1
print(ans)

Solution (Python):
I=lambda:list(map(int,input().split()))
n,m=I()
s=eval('I(),'*m)
p=I()
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k][1:]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Solution (Python):
N, M = map(int, input().split())
k, lights = [], []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp[0])
    lights.append(tmp[1:])
p = [int(i) for i in input().split()]

ans = 0
for switch in range(0, 2**N):
    flag = True
    for i in range(M):
        s = 0
        for j in range(k[i]):
            s += (switch >> (lights[i][j] - 1)) & 0b1
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Solution (Python):
import itertools

N,M = map(int, input().split())
all_lst = []
for i in range(M):
  lst = list(map(int, input().split()))
  all_lst.append(lst[1:])

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

l = [0, 1]
on_off = list(itertools.product(l, repeat=N))
ans = 0
for idx,i in enumerate(on_off):
  ans_lst = []
  for j in range(M):
    sum = 0
    for k in all_lst[j]:
      sum += i[k-1]
    ans_lst.append(sum % 2)
  if(ans_lst == lst_p):
    ans += 1
print(ans)

Solution (Python):
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]




list_pattern = [[] for j in range(2**N)]

for i in range(len(list_pattern)):
  b = bin(i)[2:].zfill(N)
  list_pattern[i] = [int(k) for k in b]



num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in dict_rel[light]:
      if pattern[i-1] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      
  if flg == True:
    num_full += 1

print(num_full)

Solution (Python):
from itertools import product
N, M = list(map(int, input().split()))
k_list = []
s_list_list = []
for _ in range(M):
    k, *s_list = list(map(int, input().split()))
    k_list.append(k)
    s_list_list.append(s_list)
p_list = list(map(int, input().split()))

def light_check(switch_pattern):
    return all([
        sum([int(switch_pattern[s-1]) for s in s_list]) % 2 == p
        for s_list, p in zip(s_list_list, p_list)
    ])

cnt = 0
for switch_pattern in product('01', repeat=N):
    if light_check(switch_pattern):
        cnt += 1
print(cnt)

Solution (Python):
import itertools

N, M = map(int, input().split())
k = []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp)

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

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    flag = True
    for i in range(M):
        end = k[i][0]+1
        sum = 0
        for j in range(1, end):
            sum += li[k[i][j]-1]
        if sum % 2 != p[i]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

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


ans = 0
for i in range(2**n):
    bina = list(reversed(format(i, '010b')))
    flag = True
    for j in range(m):
        count = 0
        sw = ks[j]
        for k in range(1,len(sw)):
            if bina[sw[k]-1] == "1":
                count += 1
        if count % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
def statecheck(state,kS,p):
  status = True
  i = 0
  for ks in kS:
    check_num = 0
    for s in ks[1:]:
      check_num = (check_num + state[s-1])
    if p[i] != check_num%2:
      status = False
      break
    i+=1
  return status

N, M= (int(i) for i in input().split())

kS = [list(map(int, input().split())) for _ in range(M)]
p = [int(i) for i in input().split()]

ans = 0

for i in range(2**N):
  state = list(format(i, 'b').zfill(N))
  state = list(map(int,state))
  if statecheck(state,kS,p):
    ans += 1

print(ans)

Solution (Python):
import math
N, M = map(int, input().split())
s=[] 
num=pow(2,N+1)-1
flag=True
count=0
for i in range(M):
  s2=list(map(int,input().split()))
  s.append(s2) 
p=list(map(int,input().split())) 
for i in range(pow(2,N)): 
  if N<10:
    S=format(num, '0'+str(N)+'b')
  else:
    S=format(num, str(N)+'b')
  S2=list(S)
  flag=True
  for j in range(M): 
    sum=0
    for k in range(s[j][0]):
      sum=sum+int(S[s[j][k+1]])
    if sum%2 != p[j]:
      flag=False
  if flag==True:
    count=count+1
  num=num-1
print(count)

Solution (Python):
import itertools

def main():
    n,m=list(map(int,input().split(' ')))
    swich_all=list(itertools.product([0,1],repeat=n))
    swich=[]
    cnt=0
    for i in range(m):
        swich.append(list(map(int,input().split(' '))))
    check_p=list(map(int,input().split(' ')))
    for i in swich_all:
        check = []
        for j in range(m):
            tmp = 0
            for k in swich[j][1:]:
                tmp += i[k-1]
            check.append(tmp%2)
        if check == check_p:
            cnt +=1

    print(cnt)

main()

Solution (Python):
n,m=map(int,input().split())
s=eval('list(map(int,input().split()[1:])),'*m)
*p,=map(int,input().split())
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Solution (Python):
from itertools import product
n,m = (int(i) for i in input().split())
x,ans = [],0
for i in range(m):
    y = [int(i)-1 for i in input().split()]
    x.append(y[1:])
z = [int(i) for i in input().split()]
def check(q):
    p = 0
    for i in range(m):
        num = 0
        for j in x[i]:
            if q[j]: num+=1
        if num%2==z[i]: p+=1
    return p==m
for i in product((0,1), repeat=n):
    if check(i): ans+=1
print(ans)

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

    for i in range(m):
        k, *s_list = map(int, input().split())
        k_list.append((k, s_list))
    p_list = list(map(int, input().split()))
    return n, m, k_list, p_list


def solve(n, m, k_list, p_list):
    def bit_count(bit):
        count = 0
        while bit > 0:
            if bit & 1:
                count += 1
            bit >>= 1
        return count

    selected_light_list = []
    for i in range(m):
        bit_sum = 0
        target = k_list[i][1]
        for j in target:
            bit_sum += 2 ** int(j - 1)
        selected_light_list.append(bit_sum)

    total_count = 0
    for sp in range(2 ** n):
        
        condition_list = []
        for i in range(m):
            if  bit_count(selected_light_list[i] & sp) % 2 == p_list[i]:
                condition_list.append(True)
            else:
                condition_list.append(False)
        if all(condition_list):
            total_count += 1
    return total_count


def main():
    n, m, k_list, p_list = input_from_console()
    print(solve(n, m, k_list, p_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  
        check_cases()
    else:
        main()

Solution (Python):
import math
N,M=map(int,input().split())
sw=[list(map(int,input().split())) for i in range(M)]
for i in range(len(sw)):
    del sw[i][0]
p=list(map(int,input().split()))

ans=0

for i in range(2**N): 
    bini=format(i,"b")
    
    num="0"*(len(format(2**N-1,"b"))-len(bini))+bini
    
    
    
    

    light=[0]*M
    for j in range(M):
        int1=0
        
        for k in sw[j]:
            
            int1+=int(num[k-1])
        if int1%2==p[j]:
            light[j]=1
    if light==[1]*M:
        ans+=1
print(ans)

Solution (Python):
n,m = map(int,input().split())
k = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
import copy
def on(l):
    for i in range(m):
        num = k[i][0]
        s = k[i][1:]
        cnt = 0
        for j in s:
            if l[j-1]:
                cnt += 1
        if not cnt%2==p[i]:
            return False
    return True

def dfs(l,i):
    if i==n:
        if on(l):
            return 1
        return 0
    ret = 0
    l_ = copy.copy(l)
    l_[i] = 1
    ret += dfs(l,i+1)
    ret += dfs(l_,i+1)
    return ret

print(dfs([0]*n,0))

Solution (Python):
import itertools
N ,M = map(int, input().split())
L = []
cou = 0
ans = 0
for i in range(M):
    L.append(list(map(int, input().split())))
p = list(map(int,input().split()))
l = list(itertools.product(range(2),repeat=N))

for li in l:
    li = list(li)
    for i in range(M):
        for j in range(L[i][0]):
            ans += li[L[i][j+1]-1]
    
        if ans % 2 == p[i]:
            ans = 0
        else:
            ans = 0
            break
        if i == M-1:
            cou += 1
            ans = 0
print(cou)

Solution (Python):
n, m = map(int, input().split())
ss = []
for _ in range(m):
  k, *s = map(int, input().split())
  ss.append(s)
plist = list(map(int, input().split()))

ans = 0
for i in range(1, pow(2, n)+1):
  den = 0
  alist = [0 for _ in range(n+1)]
  j = 0
  while i > 0:
    if i % 2 == 1:
      alist[j] = 1
    j += 1
    i //= 2
  for i, s in enumerate(ss):
    on = 0
    for _s in s:
      if alist[_s-1] == 1:
        on += 1
    if on % 2 == plist[i]:
      den += 1
  if den == m:
    ans += 1

print(ans)

Solution (Python):
numofswitch,numoflump = list(map(int, input().split()))
s = []
for i in range(numoflump):
    tmps = list(map(int, input().split()))
    s.append(tmps)
p = list(map(int, input().split()))
switch_counter = 0
num_of_comnination = 0




for switchcombi in range(2**numofswitch):
    Anal = 0
    for lumpindex in range(numoflump):
        switch_counter = 0
        for switch_checker in range(1,len(s[lumpindex])):
            if (switchcombi >> (s[lumpindex][switch_checker] -1)) % 2 == 1:
                
                switch_counter += 1
            
        if switch_counter % 2 != p[lumpindex]:
            Anal = 1
            
            break
    if Anal == 0:
        num_of_comnination += 1
print(num_of_comnination)

Solution (Python):
N,M = [int(x) for x in input().split()]
ks = [[int(x) for x in input().split()] for _ in range(M)]
p = [int(x) for x in input().split()]
li = []

for i in ks:
    n = 0
    for j in i[1:]:
        n += 1<<(j-1)
    li.append(n)

cnt = 0

for i in range(1<<N):
    flag = True
    for ind,j in enumerate(li):
        if(bin(j&i)[2:].count(str(1))%2 == p[ind]):
            pass
        else:
            flag = False
    if(flag):
        cnt += 1
print(cnt)

Solution (Python):
import itertools
N, M = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
print(sum([all([sum([s[j-1] for j in v])%2==t  for v,t in zip(k, p)]) for s in itertools.product([0,1],repeat=N)]))

Solution (Python):
import sys
import numpy as np
import copy
import itertools
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())

ks =  [[int(i) for i in input().split()] for M in range(M)]

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

kouho = []

for i in range(2**N):
    kouho.append(format(i, '0'+str(N)+'b'))

temp = 0

end = 0

ans = len(kouho)


for i in range(len(kouho)):
    
    end = 0
    for j in range(M):
        if end == 1:
            break
        temp = 0
        for k in range(ks[j][0]):
            temp = temp + int(kouho[i][ks[j][k+1]-1])
            if k == ks[j][0] - 1:
                
                
                if temp % 2 == p_amari[j]:
                    continue
                else:
                    end = 1
                    ans = ans - 1
                    break
        
    
print(ans)

Solution (Python):


import math, string



def toBinary(decimal, press=True):
    if decimal == 0: return '0'
    bin_str = ""
    i = 31
    while i >= 0:
        bi = int((decimal & int(math.pow(2, i))) >> i)
        bin_str += str(bi)
        i -= 1
    if press:
        try:
            bin_str = bin_str[bin_str.index('1'):]
        except ValueError:
            print('error')
            bin_str = '0'
    return bin_str

def isLight(bin_temp):
    for index,light in enumerate(light_list):
        light_count=0
        for switch_num in light:
            light_count += int(bin_temp[switch_num-1])
        if light_count%2 != even_or_odd[index]:
            return False
    return True
    
N,M= map(int,input().split())
light_list=[]
even_or_odd=[]
for i in range(M):
    temp=list(map(int,input().split()))
    temp = temp[1:]
    light_list.append(temp)

even_or_odd=list(map(int,input().split()))
pattern_list=[]
ans =0
for i in range(2**N):
    bin_temp = toBinary(i).rjust(N,'0')
    bin_temp=bin_temp[::-1]
    pattern_list.append(bin_temp)
    
    if isLight(bin_temp):
        ans += 1
        
            


print(ans)

Solution (Python):
from itertools import product
N, M = map(int, input().split())
S = [0]*N
for i in range(M):
    k, *s = map(int, input().split())
    for e in s:
        S[e-1] |= 1 << i
*P, = map(int, input().split())
R = 0
for i, e in enumerate(P):
    if e:
        R |= 1 << i

ans = 0
for p in product([0, 1], repeat=N):
    r = 0
    for s, e in zip(S, p):
        if e:
            r ^= s
    if r == R:
        ans += 1
print(ans)

Solution (Python):
import numpy as np
n, m = (int(_) for _ in input().split())  
skp = [[int(i) for i in input().split()] for i in range(m+1)]
sk, p = skp[:-1], skp[-1]

def judge(sw_status, sk, p):
    sk = (np.array(sk) - 1).tolist()
    num = sw_status[[sk[1:]]].sum()%2
    if num == p:
        light = 1
    else:
        light = 0
    return light

ans = 0
for i in range(2**n):
    sw_status = np.array([j for j in bin(i)[2:].zfill(n)]).astype(int)
    for SK, P in zip(sk, p):
        j = judge(sw_status, SK, P)
        if j is 0:
            break
    if j is 1:
        ans += 1

print(ans)

Solution (Python):
def run(N, M, K, S, P):
    ret = 0
    for i in range(2 ** N):
        bit = bin(i)[2:].zfill(N)
        chk = True
        for j in range(M):
            cnt = 0
            for s in S[j]:
                cnt += int(bit[s-1])
            if cnt % 2 == P[j]:
                pass
            else:
                chk = False
                break
        if chk:
            ret += 1
    return ret


def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        K.append(tmp[0])
        S.append(tmp[1:])
    P = list(map(int, input().split()))
    print(run(N, M, K, S, P))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import itertools
N, M = list(map(int, input().split()))
tmp = [[int(i) for i in input().split()] for i in range(M)]
p = list(map(int, input().split()))
ans = 0
for switch in itertools.product(range(2),repeat=N):
    
    num_clear_light = 0
    for i in range(M):
        count = 0
        for j in range(tmp[i][0]):
            
            if(switch[tmp[i][j+1] - 1] == 1):
                count += 1
        if(count % 2 == p[i]):
            num_clear_light += 1
    if(num_clear_light == M):
        ans += 1
    num_clear_light = 0

print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
K = [[int(i) for i in input().split()] for j in range(m)]
P = [int(i) for i in input().split()]

ans = 0

for bits in range(2 ** n):
    ok = True
    for i, k in enumerate(K):
        ok = ok and sum((bits >> (s - 1)) & 1 for s in k[1:]) % 2 == P[i]
    if ok:
        ans += 1

print(ans)

Solution (Python):
from itertools import combinations, product
N, M = map(int, input().split())
S = []
for i in range(M):
    l = [int(i)-1 for i in input().split()]
    S.append(l[1:])

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

ans = 0
for l in product([0,1], repeat=N):
    count = 0
    for p, s in zip(P, S):
        if sum([l[a] for a in s]) % 2 == p:
            count += 1
    if count == M:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
switch=[]
for i in range(m):
    a=list(map(int,input().split()))
    switch.append(a[1:])
p=list(map(int,input().split()))
cur=0
s=[]
a=''
def generate(a,n):
    if len(a)==n:
        s.append(a)
    else:
        generate(a+'0',n)
        generate(a+'1',n)
generate(a,n)
result=0
for k in s:
    tmp=0
    for i in range(m):
        count=0
        for j in switch[i]:
            if k[j-1]=='1':
                count+=1
        if count%2==p[i]:
            pass
        else:
            break
        tmp+=1
    if tmp==m:
        result+=1
print(result)

Solution (Python):
import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
N, M = map(int, input().split())
k = deque()
counter = 0
for i in range(M):
    k.append(list(map(int, input().split())))
p = list(map(int, input().split()))

counter = 0
for i in range(2**N):
    really = deque()
    bin_str = format(i, '012b')
    bin_str = bin_str[2:]
    for i in range(M):
        sum = 0
        for j in range(k[i][0]):
            sum += int(bin_str[10 - k[i][j+1]])
        if sum % 2 == p[i]:
            really.append(1)
        else:
            really.append(0)
    if really == deque([1]*len(really)):
        counter += 1
print(counter)

Solution (Python):
import itertools

switch, light = map(int, input().split())
ksm = []
for i in range(1, light+1):
    ks = input().split()
    ksm.append(ks)

pm = input().split()

ans = 0
for i in itertools.product([0, 1], repeat=switch):
    isOk = True
    for li in range(light):
        if not isOk:
            break
        p = int(pm[li])
        ks = ksm[li]
        light_sum = 0
        for ksi in range(int(ks[0])):
            light_sum += i[int(ks[ksi + 1]) - 1]
        if light_sum % 2 != p:
            isOk = False
    if isOk:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
lights = []
for _ in range(M):
    lights.append([int(i) for i in input().split()])
p = [int(i) for i in input().split()]

ans = 0
for switch in range(0, 2**N):
    flag = True
    for i in range(M):
        s = 0
        for j in range(lights[i][0]):
            s += (switch >> (lights[i][j + 1] - 1)) & 0b1
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Solution (Python):

def spaceinput():
    return list(map(int,input().split(" ")))


N,M=spaceinput()

S=[]
for i in range(M):
    tmp=spaceinput()
    k=tmp[0]
    S.append(tmp[1:])

p=spaceinput()

res=0
for i in range(2**N):
    flg=False
    hoge=list(bin(i)[2:].zfill(N))
    state_sw=list(map(int,hoge))
    sp=[0]*M
    
    for j in range(M):        
        for l in S[j]:
            if state_sw[l-1]:
                sp[j]+=1
        if sp[j]%2 !=p[j]:
            flg=True
            break
    
    if flg:
        continue        
    res+=1

print(res)

Solution (Python):


inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])

lights = []
for i in range(M):
    switch = input().split(' ')[1:]
    switch = [int(s) for s in switch]
    lights.append(switch)

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

combi = 0
for i in range(2**N):
    i = str(bin(i)).split('0b')[1]
    if len(i) < N:
        i = '0'*(N-len(i)) + i
    flag = True
    for j, switch in enumerate(lights):
        on = 0
        for s in switch:
            if i[s-1] == '1':
                on += 1
        if (on%2) != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Solution (Python):
n, m = [int(i) for i in input().split(" ")]
s = [0 for i in range(m)]

for i in range(m):
    s[i] = [int(j) for j in input().split(" ")]
    s[i] = s[i][1:]

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

def r(a):
    if len(a) < n:
        r(a + [0])
        r(a + [1])
        return

    global c
    for i in range(m):
        if sum([a[k - 1] for k in s[i]]) % 2 != p[i]:
            return
    c += 1

r([])
print(c)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
k = [list(map(int,input().split())) for p in [0]*m]
p = list(map(int,input().split()))

ans = 0
for bit in range(2**n):
	flag = 1
	for x in range(m):
		t = 0
		for y in range(k[x][0]):
			t = t +  2 ** (k[x][y+1]-1)
		s = bit & t
		search = 0
		while (s != 0):
			search += s%2
			s = s//2
		if search%2 != p[x]:
			flag = 0
	if flag == 1:
		ans += 1
print(ans)

Solution (Python):
import itertools

if __name__ == '__main__':
    in1 = input().split(' ')
    n = int(in1[0])
    m = int(in1[1])
    arr = []
    for i in range(m):
        arr.append(input().split(' '))
    ps = input().split(' ')

    l = list(itertools.product((True, False), repeat=n))
    c = 0
    for tfs in l:
        isOK = True
        for index, item in enumerate(arr):
            ss = item[1:]
            count = 0
            for s in ss:
                if tfs[int(s) - 1]:
                    count = count + 1
            if (count % 2) != int(ps[index]):
                isOK = False
                break
        if isOK:
            c = c + 1
    print(str(c))

Solution (Python):
n,m=map(int,input().split())
s=eval('list(map(int,input().split()[1:])),'*m)
*p,=map(int,input().split())
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Solution (Python):
import itertools

N, M = map(int, input().split())
data = []
for x in range(M):
	i = x + 1
	data.append(list(map(int, input().split())))
ps = list(map(int, input().split()))



def lightIsON(switches, light):
	
	
	

	p = ps[light - 1]
	datum = data[light - 1]
	is_k = True
	count = 0
	for x in datum:
		if(is_k):
			is_k = False
			continue
		
		

		if(switches[x-1] == 1):
			count += 1
	
	if(count % 2 == p):
		return True
	else:
		return False

def allLightIsON(switches):
	for x in range(M):
		m = x + 1
		if(not lightIsON(switches, m)):
			break
		if(m == M):
			return True
	return False

ans = 0
switch = (0, 1)


for i in itertools.product(switch, repeat=N):
	
	if(allLightIsON(i)):
		ans += 1

print(ans)

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

ret = [(bin(n)[2:].zfill(N))[::-1] for n in range(2**N)]


kss = []
for i in range(M):
  kss.append(input())
ps = list(map(int, input().split()))



def test(ret):

  return sum([int(ret[t-1]) for t in tmp]) % 2 == ps[p_i]



p_i = 0
for ks in kss:
  l = list(map(int, ks.split()))
  tmp = l[1:]
  ret = list(filter(test, ret))
  if ret == None:
    break
  p_i = p_i + 1


if ret != None:
  print(len(ret))
else:
  print(0)

Solution (Python):
N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp1 = 0
    for j in range(tmp[0]):
        tmp1 = tmp1 | 2**(tmp[j+1]-1)
    S.append(tmp1)    
        
p = list(map(int, input().split()))

ans = [True] * (2**N)
for i in range(M):
    if p[i] == 0:
        for j in range(2**N):
            if bin(j & S[i]).count("1") % 2 != 0:
                ans[j] = False
    else:
        for j in range(2**N):
            if bin(j & S[i]).count("1") % 2 != 1:
                ans[j] = False
            
print(ans.count(True))

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

k_list = []
s_lists = []

for i in range(M):
    tmp = list(map(int, input().split()))
    k_list.append(tmp[0])
    s_lists.append(tmp[1:])

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

count = 0

for i in range(1 << N):
    sw_state = [0] * N
    for j in range(N):
        if ((i >> j) & 1) == 1:
            sw_state[j] = 1
    
    
    
    flag = 0
    
    for num, s_list in enumerate(s_lists):
        tmp = sum([sw_state[s-1] for s in s_list])
        
        if tmp % 2 != p_list[num]:
            flag = 1
            break
    
    if flag != 1:
        
        count += 1

print(count)

Solution (Python):
def swit(count, ON_list):
    global ans
    if count == N:
        for l in range(M):
            d = 0
            for m in range(1,len(a[l])):

                if ON_list[a[l][m]-1] == 1:
                    d = d + 1
            if d % 2 != p[l]:
                return 0
        ans = ans + 1
    else:
        for l in range(2):
            ON_list[count] = l
            swit(count+1, ON_list)

N, M = map(int, input().split())
a = []
for i in range(M):
    b = list(map(int, input().split()))
    a.append(b)
p = list(map(int, input().split()))
ans = 0
swit(0, [0]*N)
print(ans)