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):
N,M=map(int,input().split())
ks=[list(map(int,input().split())) for i in range(M)]

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

ans=0
for i in range(2**N):
    on=[0]*N
    tmp=0
    for j in range(N):
        if((i>>j)&1):
            on[j]=1
    for j in range(M):
        count=0
        for h in range(1,ks[j][0]+1):
            if(on[ks[j][h]-1]==1):
                count+=1
        if(count%2==p[j]):
            tmp+=1
    if(tmp==M):
        ans+=1

print(ans)

Solution (Python):
def main():
    N,M=map(int,input().split())
    s=[[] for i in range(0,M)]
    for i in range(0,M):
        s[i]+=list(map(int,input().split()))
    p=list(map(int,input().split()))
    ans=0
    for i in range(0,2**N):
        flag=0
        for j in range(0,M):
            x=0
            for k in range(1,s[j][0]+1):
                x+=(i >> (s[j][k]-1) & 1)
            if x%2!=p[j]:
                flag=1
        if flag==0:
            ans=ans+1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
K, S = [], []
for _ in range(M):
    ks = list(map(int, input().split()))
    K.append(ks[0])
    S.append(ks[1:])
P = list(map(int, input().split()))
    
from itertools import product
pattern = list(product(*[[0, 1]]*N))

ans = 0
for patt in pattern:
    success = 1
    for k, s, p in zip(K, S, P):
        on = 0
        for i in range(k):
            on += patt[s[i] - 1]
        if on % 2 != p:
            success = 0
            break
    if success:
        ans += 1
print(ans)

Solution (Python):
def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


def main():
    N, M = map(int, input().split())

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

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

    ans = 0
    for bits in range(0, 1 << N):
        on_switch = list(map(lambda x: x + 1, bits2tuple(bits)))

        all_on = True
        for p, k, sk in zip(pM, kM, skM):
            if len(set(on_switch) & set(sk)) % 2 != p:
                all_on = False
                break

        if all_on:
            ans += 1

    print(ans)


main()

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


ans = 0


cnt_s_on = 0


cnt_switch = 0

for i in range(2**n):
    cnt_s_on = 0
    
    
    for j in range(m):
        cnt_switch = 0
        
        
        for K in range(k[j]):
            if ((i >> (s[j][K]-1)) & 1):
                
                cnt_switch += 1
        
        if cnt_switch%2 == p[j]:
            
            cnt_s_on += 1
    
    if cnt_s_on == m:
        ans += 1

print(ans)

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


ans = 0


cnt_s_on = 0


cnt_switch = 0

for i in range(2**n):
    
    
    

    
    tmpS=[0]*m
    cnt_s_on = 0
    
    
    for j in range(m):
        cnt_switch = 0
        
        
        for K in range(k[j]):
            if ((i >> (s[j][K]-1)) & 1):
                
                cnt_switch += 1
        
        
        
        
        if cnt_switch%2 == p[j]:
            
            cnt_s_on += 1
            tmpS[j] = 1
    
    
    
    if cnt_s_on == m:
        ans += 1

    
print(ans)

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




ans = 0
for i in range(2**n):
    state = [0] * n
    for j in range(n):
        state[j] = (i >> j) & 1

    

    cnt = 0
    for j in range(m):
        num_on = 0
        for l in range(1, len(k[j])):
            if state[int(k[j][l]) - 1] == 1:
                num_on += 1
        if num_on % 2 == p[j]:
            cnt += 1
    if cnt == m:
        ans += 1

print(ans)

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

ans = 0

for i in range(2**N):
    light = 0
    for j in range(M):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            light += 1
    if light == M:
        ans += 1

print(ans)

Solution (Python):
def count_one(num):
  ret = 0
  while num:
    if num & 1: ret+=1
    num = num >> 1

  return ret

def solve():
  N,M = map(int, input().split())
  switches = []
  for _ in range(M):
    switches_pattern = list(map(int, input().split()))[1:]
    pattern_int = sum(2**(i-1) for i in switches_pattern)
    switches.append(pattern_int)
  ps = list(map(int, input().split()))

  switch_pattern_upper = 2**N

  def check(pattern):
    ret = True
    for i in range(M):
      bit_count = count_one(switches[i] & pattern)
      
      if bit_count % 2 != ps[i]:
        ret = False
        break
      
    return ret
    
  ret = 0
  
  for pattern in range(switch_pattern_upper):
    
    if check(pattern): ret += 1

  print(ret)
  
solve()

Solution (Python):


class Proc:
    def __init__(self):
        (n, m) = [int(i) for i in input().rstrip().split(" ")]
        self.switch_count = n
        self.light_count = m
        self.light_connect = [[int(i) - 1 for i in input().rstrip().split(" ")][1:] for j in range(m)]
        self.light_setting = [int(i) for i in input().rstrip().split(" ")]

    def get_ans(self, index: int, subtotal: int):
        if index >= self.switch_count:
            light_connect_count = [0 for i in range(self.light_count)]
            for i in range(0, self.switch_count):
                if ((1 << i) & subtotal) == 0:
                    continue
                for j in range(self.light_count):
                    if i in self.light_connect[j]:
                        light_connect_count[j] += 1
            if all([light_connect_count[i] % 2 == self.light_setting[i] for i in range(self.light_count)]):
                return 1
            else:
                return 0

        ret = self.get_ans(index + 1, subtotal) + self.get_ans(index + 1, subtotal + (1 << index))
        return ret


print(Proc().get_ans(0, 0))

Solution (Python):
n,m = map(int,input().split())
s = []
k = []
for i in range(m):
    s_in = list(map(int,input().split()))
    s.append(s_in[1:])
    k.append(s_in[0])
p = list(map(int,input().split()))
ans = 0
def bfs(switch):
    global ans
    if len(switch)==n:
        ok = 1 
        for i in range(m):
            on_cnt=0
            for j in range(k[i]):
                if switch[s[i][j]-1]==1:
                    on_cnt+=1
            if on_cnt%2!=p[i]:
                ok = 0
        if ok:
            ans+=1
    else:
        bfs(switch+[0])
        bfs(switch+[1])
bfs([])
print(ans)

Solution (Python):
from itertools import product
N, M = map(int, input().split())
denkyu = [[int(x) for x in input().split()] for _ in range(M)]
P = [int(x) for x in input().split()]
L = list(product([0,1], repeat = N))
ans = 0
for i in L:
    den = 0
    for j in range(M):
        count = 0
        for k in range(denkyu[j][0]):
            if i[denkyu[j][k+1]-1] == 0:
                count += 1
        if count % 2 == P[j]:
           den += 1 
    if den == M:
        ans += 1
print(ans)

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

s = []
ans = 0
for i in range(m):
  k = ks[i][0]
  l = [ks[i][j] for j in range(1, k+1)]
  s.append(l)

swh = [False for _ in range(n)]
for i in range(2 ** n):
  
  flag = True
  
  for j in range(n):
    if ((i >> j) & 1): swh[j] = True
    else: swh[j] = False
      
  
  for j in range(m):
      
      judge = [swh[si-1] for si in s[j]]
      
      if judge.count(True) % 2 != p[j]:
        flag = False
        break
        
  if flag: ans += 1
  
      
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = []
for i in range(M):
  k, *s = list(map(int, input().split()))
  S.append(s)

P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  if all([
    sum([i & 2 ** (n-1) > 0 for n in S[m]]) % 2 == P[m] for m in range(M)
  ]):
    ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
indices = []
for _ in range(m):
  s_map = map(int, input().split())
  next(s_map)
  indices.append([s-1 for s in s_map])
p = list(map(int, input().split()))
count = 0
for i in range(1 << n):
  list_i = [int(bit) for bit in format(i, '0{}b'.format(n))]
  flag = True
  for j in range(m):
    on = 0
    for idx in indices[j]:
      on ^= list_i[idx]
    if on != p[j]:
      flag = False
      break
  if flag:
    count += 1
print(count)

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

ans = 0
for b in range(2**N):
    for s,p in zip(S,P):
        c = 0
        for t in s:
            if b&(1<<(t-1)): c += 1
        if c%2 != p:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())
s = [set(map(int, sys.stdin.readline().split()[1:])) for _ in range(m)]
*p, = map(int, sys.stdin.readline().split())

def main():
    combs = 0
    for i in range(2 ** n):
        t = set([j + 1 for j in range(n) if i >> j & 1])
        for k in range(m):
            if len(s[k] & t) & 1 != p[k]:
                break
        else:
            combs += 1
    
    return combs

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
def so(l, n, ar):
	if (n < l):
		so(l, n + 1, ar + [True])
		so(l, n + 1, ar + [False])
	elif (n == l):
		global switchOnOff
		switchOnOff.append(ar)
        
switchOnOff = []
n, m = [int(i) for i in input().split()]
denkyus = []
for i in range(m):
	a = [int(j) for j in input().split()]
	denkyus.append(a[1:])
hikaku = [int(i) for i in input().split()]   
so(n, 0, [])

ret = 0
denkyuCnt = [0] * m
for ss in switchOnOff:
	denkyuCnt = [0] * m
	for si, s in enumerate(ss):
		for ji, j in enumerate(denkyus):
			if s and (si + 1) in j:
				denkyuCnt[ji] += 1
	subcnt = 0
	for i, d in enumerate(denkyuCnt):
		if d % 2 == hikaku[i]:
			subcnt += 1
	if subcnt == m:
		ret += 1
print (ret)

Solution (Python):
import os, sys, re, math

(N, M) = [int(n) for n in input().split()]
S = []
for i in range(M):
    v = [int(n) for n in input().split()]
    S.append(v[1:])
P = [int(n) for n in input().split()]

result = 0
for i in range(2 ** N):
    bulbs = bin(i)[2:].zfill(N)
    all_ok = True
    for j in range(len(S)):
        l = sum([int(bulbs[s - 1]) for s in S[j]])
        all_ok &= (l % 2 == P[j])
    if all_ok:
        result += 1

print(result)

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

v = 0
for i in range(1 << n):
    on = True
    for k, p in zip(ks, ps):
        c = 0
        for b in k[1:]:
            if i & 1 << (b-1) > 0:
                c += 1
        if c % 2 != p:
            on = False
            break
    if on:
        v += 1

print(v)

Solution (Python):
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((b >> (j - 1)) & 1 for j in k[i]) % 2 == p[i] for i in range(m)) for b in range(2 ** n)))

Solution (Python):
n, m = list(map(int, input().split(' ')))
kk = []
ss = []
for i in range(m):
    l = list(map(int, input().split(' ')))
    k = l[0]
    s = l[1:]
    kk.append(k)
    ss.append(s)
    
pp = list(map(int, input().split(' ')))
def ok(switches):
    valid = True
    for i in range(len(ss)):
        s = ss[i]
        temp = 0
        for j in range(len(s)):
            temp += switches[s[j]-1]
        if temp % 2 != pp[i]:
            valid = False
            break
    return valid

def f(current, switches):
    if current == n:
        return ok(switches)
    ans = f(current + 1, switches + [1])
    ans += f(current + 1, switches + [0])
    return ans
print(f(0, []))

Solution (Python):
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
lights=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))

cnt=0
for i in range(2**n):
  flag=True
  i=format(i,'b')
  i=i.zfill(n)
  for j in range(m):
    ans=0
    for k in range(1,lights[j][0]+1):
      ans+=int(i[lights[j][k]-1])
      ans%=2
    if ans==p[j]:
      continue
    else:
      flag=False
  if flag:
    cnt+=1
print(cnt)

Solution (Python):
N_sw, N_ball = map(int, input().split())

switches = [list(map(int, input().split())) for i in range(N_ball)]
P = list(map(int, input().split()))
cnt = 0

def judge_OK(state_2):
    flag = True
    
    for i in range(N_ball):
        S = switches[i]
        count = 0
        
        for j in range(1, len(S)):
            index = S[j] - 1
            count += state_2[index]
        
        if (count % 2 != P[i]):
            flag = False
            break
    
    return(flag)


for state in range(2 ** N_sw):
    state_2 = []
    
    for i in range(N_sw):
        tmp = int((state & 1 << i) == 1 << i)
        state_2.append(tmp)
    
    cnt += judge_OK(state_2)

print(cnt)

Solution (Python):
import itertools

n, m = [int(x) for x in input().split()]
lst = []
for _ in range(m):
    a = [int(x) for x in input().split()]
    lst.append(a)
p = tuple([int(x) for x in input().split()])

sta = [0,1]
cnt = 0

for v in itertools.product(sta, repeat=n):
    for i in range(m):
        if sum(v[x - 1] for x in lst[i][1:]) % 2 != p[i]:
            break 
    else:
        cnt += 1

print(cnt)

Solution (Python):
N, M = map(int, input().split())
lights = []
for i in range(M):
    k, *s = map(int, input().split())
    lights.append(list(map(lambda x: x-1, s)))
P = list(map(int, input().split()))
ans = 0
for b in range(2 ** N):
    flg = True
    for m in range(M):
        cnt = 0
        for switch in lights[m]:
            if (b >> switch) & 1:
                cnt += 1
        if cnt % 2 != P[m]:
            flg = False
    if flg:
        ans += 1
print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, m = MAP()

l = [LIST() for i in range(m)]
p = LIST()


bits = product([0, 1], repeat=n)
ans = 0


for b in bits:
    light = 0
    for i, s_l in enumerate(l):
        on = 0
        for s in s_l[1:]:
            on += b[s-1]
        if on % 2 == p[i]:
            light += 1
    if light == m:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
switch = [0]*N
for m in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        switch[s-1] |= 2**m
li = 0
for index,p in enumerate(list(map(int, input().split()))):
    if p==1: li += 2**index
answer = 0
for n in range(2**N):
    l = 0
    for s in range(N):
        if (n>>s)&1: l^=switch[s]
    if li==l: answer+=1
print(answer)

Solution (Python):
from numpy import *

n, m = map(int, input().split())
l = []
for _ in range(m):
   *a, = map(int, input().split())
   l.append(a[1:])
*p, = map(int, input().split())

ans = 0
for t in range(2**n):
   tmp = array([t >> s & 1 for s in range(n)])
   if p == [sum(tmp[array(i)-1]) % 2 for i in l]:
      ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
lights=[]
for i in range(M):
    k,*s=map(int,input().split())
    lights.append(list(map(lambda x:x-1,s)))
P=list(map(int,input().split()))
cnt=0
for b in range(1<<N):
    
    flg=True
    for m in range(M):
        on_cnt=0
        for switch in lights[m]:
            if (b>>switch)&1:
                on_cnt+=1
        
        if on_cnt%2 != P[m]:
            flg=False
    if flg:
       cnt+=1
       
print(cnt)

Solution (Python):


N, M = map(int, input().split())
SW = [[] for _ in range(M)]

for i in range(M):
  SW[i] = [int(s)-1 for s in input().split()[1:]]

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

ans = 0
for bit in range(1<<N): 
  ok = True
  for i in range(M):
    con = 0
    for sw in SW[i]: 
      if bit & (1<<sw):
        con += 1
    if con%2 != P[i]:
      ok = False
  if ok:
    ans += 1
print(ans)

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

cnt=0
for i in range(2**n):
    Q=0
    light=set([i+1 for i,j in enumerate(format(i,"b").zfill(n)[::-1]) if j=="1"])
    for k,j in enumerate(S):
        if len(light&set(j))%2==P[k]:Q +=1
    if Q==m:cnt +=1

print(cnt)

Solution (Python):
def check(l, s, p):
    for i in range(len(l)):
        l_i = l[i]
        cnt = 0
        for j in range(1,len(l_i)):
            cnt += s[l_i[j]-1]
        if cnt % 2 != p[i]:
            return False
    return True


n,m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for k in range(2**n):
    s = []
    for i in range(n):
        s.append( int(k & 1<<i == 1<<i) )
    ans += int(check(l,s,p))
print(ans)

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

ans=0
for i in range(2 ** n):
    swi = []
    for j in range(n):
        if ((i >> j) & 1):
            swi.append(1)
        else:
            swi.append(0)
    swi.reverse()

    ok_flag=True
    for lit in range(m):
        sm=0
        for tmp in range(1,len(l[lit])):
            sm += swi[l[lit][tmp]-1]
        if sm % 2 != p[lit]:
            ok_flag=False

    if ok_flag:
        ans+=1
print(ans)

Solution (Python):
import itertools

def main():
    n, m = map(int, input().split())
    num_list = []
    for i in range(m):
        num_list.append(list(map(int,input().split())))

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

    ans = 0

    for i in itertools.product([0,1], repeat=n):
        check = [0] * m
        for j in range(m):
            tmp = 0
            check[j] = True
            for n in range(1, num_list[j][0] + 1):
                if i[num_list[j][n] - 1] == 1:
                    tmp += 1
            if tmp % 2 != p_list[j] % 2:
                check[j] = False
        if all(check):
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

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()))

SS = []

for s in S:
  s.pop(0)
  SS.append(s)

count = 0

for bit in range(1 << N):
  flag = True

  for index, s in enumerate(SS):
    on = 0

    for n in range(N):
      if n+1 in s and bit & (1 << n):
        on += 1

    if on % 2 != P[index]:
      flag = False

  if flag:
    count += 1

print(count)

Solution (Python):
k = []

n, m = map(int, input().split())
for i in range(m):
    k.append(list(map(int, input().split())))
    del k[i][0] 

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

cnt = 0
ans = 0
for i in range(2 ** n):
    lis = [False] * n

    for j in range(n):
        if (i >> j) & 1:
            lis[j] = True
    
    cnt = 0
    for j in range(m):
        val = 0
        for l in range(len(k[j])):
            if lis[k[j][l]-1] == True:
                val += 1
            
        if val % 2 == p[j]:
            cnt += 1
        
        
    if cnt == m:
        ans += 1
    



print(ans)

Solution (Python):
n, m = map(int, input().split())
den = []
for _ in range(m):
    i = list(map(int, input().split()))
    i.pop(0)
    tden = [0] * n
    for j in i:
        tden[j - 1] = 1
    den.append(tden)

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

import itertools as it

stat = [i for i in it.product([0, 1], repeat=n)]
ans = 0
for st in stat:
    f = 1
    for no, td in enumerate(den):
        l = [min(i, j) for i, j in zip(st, td)]
        tento = sum(l) % 2
        if p[no] != tento:
            f = 0
            break
    if f: ans += 1
print(ans)

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

ans = 0
for i in range(2**N):
    switch = list((str(bin(i)[2:])).zfill(N))
    all_on = True
    for j in range(M):
        on = 0
        for k in range(1,len(light[j])):
            if switch[light[j][k] - 1] == "1":
                on += 1
        if on % 2 != p[j]:
            all_on = False
            break
    if all_on == True:
        ans += 1

print(ans)

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

ans = 0

for i in range(2 ** n):
    isLightOn = [False] * m
    for k in range(m):
        count = 0
        for j in range(len(s[k])):
            if (i >> s[k][j] - 1) & 1:
                count += 1
        if count % 2 == p[k]:
            isLightOn[k] = True
    if sum(isLightOn) == m:
        ans += 1

print(ans)

Solution (Python):


class Light:
    def __init__(self, conect, condition):
        self.conect = conect 
        self.condition = condition

def main():
    n, m = map(int, input().split())
    preArray = []
    for i in range(m):
        tmp = [int(i) - 1 for i in input().split()][1:]
        preArray.append(tmp)
    ps = [int(i) for i in input().split()]


    Lights = []
    for i in range(m):
        Lights.append(Light(preArray[i], ps[i]))



    ans = 0
    for i in range(1<<n):
        swichState = [0 for _ in range(n)]
        for k in range(n):
            if (i >> k) & 1:
                swichState[k] = 1
        
        

        flag = True
        for j in range(m):
            conec = Lights[j].conect
            cond = Lights[j].condition
            cnts = 0
            for k in range(len(conec)):
                if swichState[conec[k]] == 1:
                    cnts += 1 
            if cnts % 2 == cond:
                continue
            else:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)
main()

Solution (Python):
from itertools import product
 
n, m = map(int, input().split())
k = []
s = []
for i in range(m):
    tmp = list(map(int, input().split()))
    k.append(tmp[0])
    s.append(tmp[1:])
p = list(map(int, input().split()))
 
ans = 2 ** n
for prod in (product([0, 1], repeat=n)):
    for i in range(m):
        tmp = 0
        for j in s[i]:
            tmp += prod[j - 1]
        if (tmp % 2 != p[i]):
            ans -= 1
            break
print(ans)

Solution (Python):
N, M = map(int, input().split())
lstMain = list()
for i in range(M):
    lstSub = list(map(int, input().split()))
    lstMain.append(lstSub[1:])
lstP = list(map(int, input().split()))

endStr = ("0000000000" + "1"*N)[-10:]
count = 0

for i in range(0, 2 ** 10):
    binStr = ("0000000000" + format(i, 'b'))[-10:]
    errFlg = 0
    
    for j in range(M):
        s = 0
        for k in range(len(lstMain[j])):
            s += int(binStr[(-1) * lstMain[j][k]])
        if s % 2 != lstP[j]:
            errFlg = 1
        if errFlg == 1:
            break
    if errFlg == 0:
        count += 1
    if binStr == endStr:
        break
    
print(count)

Solution (Python):
n,m = map(int, input().split( ))
sw = [0 for _ in range(m)]
for i in range(m):
    s = list(map(int, input().split( )))
    s = [si-1 for si in s[1:]]
    bt = 0
    for sj in s:
        bt += 1<<sj
    sw[i] = bt
    
p = list(map(int, input().split( )))


bit = 1<<n
ans = 0
for i in range(bit):
    flag = True
    for j in range(m):
        cnt = 0
        for k in range(n):
            cnt += (i&sw[j])>>k
        if cnt%2!=p[j]:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
f = lambda : map(int, input().split())

n, m = f()
ll = [[0]*n for i in range(m)]
for i in range(m):
  _, *t = f()
  for j in t:
    ll[i][j-1] = 1
lp = list(f())

import itertools as it
ans = 0

for p in it.product([0,1], repeat=n):
  if lp == [sum(a*b for a, b in zip(p,l))%2 for l in ll]:
    ans += 1

print(ans)

Solution (Python):
f = lambda : map(int, input().split())

n, m = f()
ll = [[0]*n for i in range(m)]
for i in range(m):
  k, *t = f()
  for j in range(k):
    ll[i][t[j]-1] = 1
lp = list(f())

import itertools as it
ans = 0

for p in it.product([0,1], repeat=n):
  if lp == [sum(a*b for a, b in zip(p,l))%2 for l in ll]:
    ans += 1

print(ans)

Solution (Python):
f = lambda : map(int, input().split())
n, m = f()
ll = [[0]*n for i in range(m)]
for i in range(m):
  k, *t = f()
  for j in range(k):
    ll[i][t[j]-1] = 1
lp = list(f())

import itertools as it
lt = [p for p in it.product([0,1], repeat=n)]

ans = 0
for p in lt:
  lj = []
  for l in ll:
    lj.append(sum(a*b for a, b in zip(p,l))%2)
  if lp == lj:
    ans += 1

print(ans)

Solution (Python):
def fbit(k,n):
    t=[]
    kk=k
    for i in range(n):
        t.append(kk%2)
        kk=int(kk/2)
    return t        

n,m=map(int,input().split())
s=[]
for i in range(m):
    si=[]
    for j in range(n):
        si.append(0)
    s.append(si)
    
for j in range(m):
    str=input().split()
    k_m=int(str[0])
    for k in range(k_m):
        ii=int(str[k+1])-1
        s[j][ii]=1

str=input().split()
p=[]
for k in range(m):
    p.append(int(str[k]))

icnt=0
for k in range(2**n):
    icnt2=0
    bit=fbit(k,n)
    for im in range(m):
        icnt3=0
        for kn in range(n):
            icnt3=icnt3+bit[kn]*s[im][kn]
        if icnt3%2==p[im]:
            icnt2=icnt2+1
    if icnt2==m:
        icnt=icnt+1
print(icnt)

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

sss = []
for _ in range(M):
    k, *ss = map(lambda x: int(x) - 1, input().split())
    sss.append(ss)
ps = list(map(lambda x: x == '0', input().split()))




cnt = 0
for i in range(2 ** N):
    lights = ps[:]
    
    for j, ss in enumerate(sss):
        for s in ss:
            if i >> s & 1:
                lights[j] = not lights[j]
    
    if all(lights):
        cnt += 1

print(cnt)

Solution (Python):
import itertools

N, M = map(int, input().split())
skss = []
for _ in range(M):
    k, *sks = map(int, input().split())
    skss.append(set(sks))
pMs = list(map(lambda x: x == '0', input().split()))

count = 0
for i in range(2 ** N):
    pMstmp = pMs[:]
    for j, b in enumerate(format(i, '0' + str(N) + 'b')):
        if b == '0':
            continue
        for k, sks in enumerate(skss):
            if j + 1 in sks:
                pMstmp[k] = not pMstmp[k]
    if all(pMstmp):
        count += 1

print(count)

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

sss = []
for _ in range(M):
    k, *ss = map(lambda x: int(x) - 1, input().split())
    sss.append(ss)
ps = list(map(lambda x: x == '0', input().split()))


cnt = 0
for i in range(2 ** N):
    lights = ps[:]
    for j, ss in enumerate(sss):
        for s in ss:
            if i >> s & 1:
                lights[j] = not lights[j]
    if all(lights):
        cnt += 1

print(cnt)

Solution (Python):
n, m = [int(i) for i in input().split()]
bulbs = []
for _ in range(m):
    bulbs.append([int(i) for i in input().split()][1:])

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


def all_on(switches):
    for idx, bulb in enumerate(bulbs):
        switched = 0
        for s in bulb:
            switched = 1 - switched if s in switches else switched
        if switched != conds[idx]:
            return 0
    return 1


def count_all_right(curr_switches, pos):
    if pos == n - 1:
        return all_on(curr_switches) + all_on(curr_switches + [pos + 1])
    return count_all_right(curr_switches + [pos + 1], pos + 1) + count_all_right(
        curr_switches, pos + 1
    )


print(count_all_right([], 0))

Solution (Python):
import numpy as np
n, m = map(int, input().split())

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

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

ans = 0

for t in range(2 ** n):
  
  on_switch_list = np.array([t >> s & 1 for s in range(n)])
  
  
  
  if p == [np.sum(on_switch_list[np.array(i) - 1]) % 2 for i in switches]:
    ans += 1
print(ans)