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):
def mod2(num):
    return num % 2

def solve():
    
    N, M = list(map(int, input().split()))  
    k = [0] * M  
    s = [[0] for _ in range(M)]  
    for i in range(M):
        tmp = list(map(int, input().split()))
        k[i] = tmp[0]
        s[i] = tmp[1::]
    p = list(map(int, input().split()))

    
    count = 0
    for switch_state in range(2**N):
        p_tmp = [0] * M
        iter_num = format(switch_state, '0'+str(N)+'b')
        
        for i, s_i in enumerate(s):
            
            for s_i_j in s_i:
                if (iter_num[s_i_j-1] == '1'):
                    p_tmp[i] += 1
        if(p == list(map(mod2, p_tmp))):
            count += 1
    print(count)

if __name__ == "__main__":
    solve()

Solution (Python):

n,m=map(int,input().split())
ks=[[] for i in range(m)]
for i in range(m):
    ks[i]=list(map(int,input().split()))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    a=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            a[j]=1
    f=0
    for j in range(m):
        x=0
        for q in range(ks[j][0]):
            
            if a[ks[j][q+1]-1]==1:
                x+=1
        if x%2==p[j]:
            f+=1
    if f==m:
        ans+=1
print(ans)

Solution (Python):

n,m=map(int,input().split())
ks=[[] for i in range(m)]
for i in range(m):
    ks[i]=list(map(int,input().split()))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    a=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            a[j]=1
    f=0
    for j in range(m):
        x=0
        for q in range(ks[j][0]):
            
            if a[ks[j][q+1]-1]==1:
                x+=1
        if x%2==p[j]:
            f+=1
    if f==m:
        ans+=1
print(ans)

Solution (Python):
import numpy as np

N,M=map(int,input().split())
ks=np.array([[int(i) for i in input().split()] for _ in range(M)])
p=list(map(int,input().split()))

ans=0

for i in range(2**N):

    
    sw=[0]*N
    for j in range(N):
        if (i>>j)&1:
            sw[j]=1

    count=0
    for denkyu_no in range(M):
        if sum([sw[ks[denkyu_no][j+1]-1] for j in range(ks[denkyu_no][0])])%2 ==p[denkyu_no]:
            count +=1

    if count==M:
        ans+=1
print(ans)

Solution (Python):
import numpy as np
 
N, M = map(int, input().split())
array = np.zeros([M, N])
for i in range(M):
    l = list(map(int, input().split()))
    for j in l[1:]:
        array[i, j-1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for i in range(1<<N):
    array_i = array.copy()
    for j in range(N):
        if i&(1<<j):
            array_i[:, j-1] = 0
    if sum(array_i.sum(1)%2 == p)==M:
        count += 1
print(count)

Solution (Python):
import itertools

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


answer_count = 0
for switches in itertools.product((0, 1), repeat=N):
    on_count = 0
    for j in range(M):
        count = 0
        for i in range(N):
            if (switches[i] == 1) and (i + 1 in target_switches[j][1:]):
                count += 1
                
        if count % 2 == p[j]:
            on_count += 1
    
    if on_count == M:
        answer_count += 1

print(answer_count)

Solution (Python):
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(M)]
P=list(map(int,input().split()))
c=0
for i in range(2**N):
    A=[0]*N
    for j in range(N):
        if (i>>j&1):
            A[j]=1
    T=True
    for j in range(M):
        s=0
        for k in range(L[j][0]):
            s+=A[L[j][k+1]-1]
        if s%2!=P[j]:
            T=False
    if T:
        c+=1
print(c)

Solution (Python):
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    ss=[0]*n
    cc=0
    for j in range(n):
        if i>>j&1:
            ss[j]=1
    for j in range(m):
        c=0
        k=s[j][0]
        for l in range(1,k+1):
            c+=ss[s[j][l]-1]
        if c%2==p[j]:
            cc+=1
    if cc==m:
        ans+=1
print(ans)

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

klist = []
slist = [list() for _ in range(m)]

for i in range(m):
    k,*s = map(int,input().split())
    klist.append(k)
    slist[i] = s

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

ans = 0
for i in range(2**n):
    for j in range(m):
        cnt = 0
        for l in slist[j]:
            if (i >> (l-1))&1 ==1:
                cnt += 1
        if cnt%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):




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

res = 0
for i in range(2**N):
    b = format(i, '0' + str(N) + 'b')
    can_light_up = True
    for j in range(M):
        count = 0
        for s in k[j]:
            if b[s-1] == '1':
                count += 1
        if count % 2 != p[j]:
            can_light_up = False
    if can_light_up:
        res += 1

print(res)

Solution (Python):
import itertools
n,m = map(int,input().split())
k = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
s = []
for i in range(n):
    s.append(i)
count = 0
for i in range(n+1):
    for item in itertools.combinations(s, i):
        li = [0] * m
        onoff = [0]*n
        for j in item:
            onoff[j] = 1
        for k_i in range(m):
            c = 0
            for k_j in range(k[k_i][0]):
                if onoff[k[k_i][k_j+1]-1] == 1:
                    c += 1
            if c % 2 == p[k_i]:
                li[k_i] = 1
        if all(li):
            count += 1
print(count)

Solution (Python):
N, M = map(int,input().split())
state = []
for _ in range(M):
  lst = list(map(int, input().split()))
  state.append(lst[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  total = 0
  for j in range(M):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
    else:
      break
  if total == M:
    ans += 1
print(ans)

Solution (Python):
N, M = map(int,input().split())
state = []
for _ in range(M):
  lst = list(map(int, input().split()))
  state.append(lst[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  total = 0
  for j in range(M):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
  if total == M:
    ans += 1
print(ans)

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, m = MI()
    connected = []
    for i in range(m):
        row = LI()
        swithes = row[1:]
        connected.append(swithes)
    p = LI()
    ans = 0
    for i in range(2 ** n):
        i_str = format(i, f"0{n}b")
        is_ok = True
        for m_idx in range(m):
            sum_1 = 0
            for swith in connected[m_idx]:
                if i_str[swith - 1] == "1":
                    sum_1 += 1

            if sum_1 % 2 != p[m_idx]:
                is_ok = False
                break

        if is_ok:
            ans += 1

    print(ans)


main()

Solution (Python):


import copy

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

ks = []
for l in range(M):
    s = input().split()
    ks.append(s)
p = list(map(int, input().split()))

KS = []
for m in range(M):
    box = list()
    for n in range(len(ks[m])):
        ks[m][n] = int(ks[m][n])
        box.append(ks[m][n])
    KS.append(box)            

swich = []
for o in range(M):
    swi = list()
    for r in range(1,len(KS[o])):
        swi.append(ks[o][r])
    swich.append(swi)
           
ans = 0
for i in range(1<<N):
    SWICH = copy.deepcopy(swich)
    light_on = 0
    for j in range(N):
        mask = 1<< j
        if i & mask != 0:
            continue
        else:
            for y in range(M):
                if (j+1 in SWICH[y]) == True:
                    SWICH[y].remove(j+1)

    
    flat_SWICH = []
    for a in range(len(SWICH)):
        for b in range(len(SWICH[a])):
            flat_SWICH.append(SWICH[a][b])
            
    for x in range(M):
        if (len(SWICH[x]) % 2) == p[x]:
            light_on += 1
    if light_on == M:
        ans += 1
print(ans)

Solution (Python):
import numpy as np

N, M = map(int, input().split())
array = np.zeros([M, N])
for i in range(M):
    l = list(map(int, input().split()))
    for j in l[1:]:
        array[i, j-1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for i in range(1<<N):
    array_i = array.copy()
    for j in range(N):
        if i&(1<<j):
            array_i[:, j-1] = 0
    if sum(array_i.sum(1)%2 == p)==M:
        count += 1
print(count)

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

for i in range(M):
    switches_bulbs_connection[i] = list(map(int, input().split()))[1:]
p = list(map(int, input().split()))
count = 0
flag = 0

for i in range(2 ** N):  
    switch_on_off = [0] * N
    bulb_stat = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            switch_on_off[j] += 1  
    for k in range(M):  
        tmp = switches_bulbs_connection[k]
        for switch in tmp:
            if switch_on_off[switch-1]:
                bulb_stat[k] += 1
    for l in range(M):
        if bulb_stat[l] % 2 == p[l]:
            flag += 1
    if flag == M:
        count += 1
    flag = 0

print(count)

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

import itertools
l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

ans=0
for i in range(2**n):
  ok=[]
  for j in range(m):
    on=0
    for t in range(1,s[j][0]+1):
      e=s[j][t]
      if l[i][e-1]==1:
        on+=1
    if on%2!=p[j]:
      ok.append(False)
  if False not in ok:
    ans+=1

print(ans)

Solution (Python):
n,m=map(int,input().split())
k=[0]*m
s=[[0 for j in range(n)] for i in range(m)]
for i in range(m):
  x = list(map(int,input().split()))
  k = x[0]
  for j in range(1, k+1):
    s[i][x[j]-1] = 1
p=list(map(int,input().split()))

ans = 0
for x in range(2**n):
  for i in range(m):
    cnt = 0
    for j in range(n):
      if (x >> j & 1) and s[i][j]:
        cnt += 1
    if cnt % 2 != p[i]:
      break
  else:  
    ans += 1
print(ans)

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

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

P=["*"]+list(map(int,input().split()))

X=0
for i in range(2**N):
    Q=["*"]+[0]*M
    for x in range(N):
        if i%2:
            for k in S[x+1]:
                Q[k]=(Q[k]+1)%2
                
        i>>=1
    X+=(P==Q)
print(X)

Solution (Python):
N,M = map(int,input().split()) 
K = []; S = []
for i in range(M):
  k, *s = map(int,input().split())
  for j in range(len(s)): 
    s[j] -= 1 
  K.append(k)
  S.append(s)


P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
  Switch= [0 for _ in range(N)]
  for j in range(N): 
    if(i>>j)&1==1:
      Switch[j] = 1
  num = 0
  for k in range(M): 
    temp = 0
    for x in S[k]:
      if Switch[x] == 1:
        temp += 1
    if temp%2 == P[k]:
      num += pow(2,k)
  
  if num == pow(2,M)-1:
    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()))

res = 0

for bit in range(1 << n):
    ok = True
    
    for i in range(m):
        
        cnt = 0
        
        for v in lights[i]:
            v -= 1
            
            if bit & (1 << v):
                cnt += 1
        
        if cnt % 2 != P[i]:
            ok = False
    if ok:
        res += 1
print(res)

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

cnt = 0
for i in range(2**N):
    b = [0]*N
    for j in range(N):
        if ((i >> j) & 1):
            b[j] = 1
    
    for k in range(M):
        num = 0
        for l in range(len(light[k])-1):
            num += b[light[k][l+1]-1] 
        if num%2 != p[k]:
            break
    else: cnt += 1
print(cnt)

Solution (Python):
import numpy as np
import itertools
n,m = map(int, input().split())
sw = [[int(i) - 1 for i in input().split()] for _ in range(m)]
p = np.array([int(i) for i in input().split()])
x = np.full_like(p, -1)

s_l = itertools.product(np.array([True,False]), repeat = n)
ans = 0
for si in s_l:
    si = np.array(si)
    for mi in range(m):
        x[mi] = si[sw[mi][1:]].sum() % 2
    if np.all(p == x):
        ans += 1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
s=[]
for _ in range(M):
    s.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
ans=0
for bit in itertools.product([0,1],repeat=N):
    count=[0]*M
    for light in range(M):
        for k in s[light]:
            count[light]+=bit[k-1]
    if all (count[i]%2==p[i] for i in range(M)):
        ans+=1
print(ans)

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



N,M = map(int,readline().split())
lights = [None] * M
for i in range(M):
  lights[i] = list(map(int,readline().split()))[1:]
  
P = list(map(int,readline().split()))

ans = 0
for i in range(2 ** N):
  for j in range(len(lights)):
    
    cnt = 0
    for k in range(len(lights[j])):
      
      
      if (i >> lights[j][k] - 1) & 1:
        
        cnt += 1
    if cnt % 2 != P[j]:
      break
  else:
    ans += 1

print(ans)

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

ans = 0
for idx in range(2**n):
    switch_on = [False] * n
    for s in range(n):
        if 2**s & idx > 0:
            switch_on[s] = True

    ok = True
    
    for lamp in range(m):
        num_on_switch = 0
        for s in switches[lamp - 1][1:]:
            if switch_on[s-1] == True:
                num_on_switch += 1
        
        if num_on_switch % 2 != ps[lamp-1]:
            ok = False
        if not ok:
            break
    
    if ok:
        ans += 1

print(ans)

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

k = []
s_l = []
for _ in range(m):
    l = list(map(int, input().split()))
    k.append(l[0])
    s_l.append(l[1:])

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

ans = 0
for i in range(2**n):
    valid = 1
    for j in range(m):
        on = 0
        for s in s_l[j]:
            on += (i >> (s-1) & 1)
        if on % 2 == p[j]:
            valid *= 1
        else:
            valid *= 0
    ans += valid

print(ans)

Solution (Python):
from itertools import *
N,M = map(int,input().split())
K = [list(map(int,input().split()))[1:] for m 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 product([0,1],repeat=N)]))

Solution (Python):
N, M = map(int, input().split())
L = []
for _ in range(M):
  k, *S = map(int, input().split())
  L.append(S)
P = list(map(int, input().split()))
c = 0
for i in range(2**N):
  A = []
  for j in range(N):
    if (i>>j)&1:
      A.append(j+1)
  A = set(A)
  for i in range(M):
    if len(A&set(L[i]))%2!=P[i]:
      break
  else:
    c += 1
print(c)

Solution (Python):
n,m=map(int,input().split())
num=[]
for i in range(m):
    num.append(list(map(int,input().split())))
num3=[[] for _ in range(n)]
for i in range(m):
    for j in range(1,num[i][0]+1):
        num3[num[i][j]-1].append(i+1)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    num2=[0]*m
    num4=0
    for j in range(n):
        if (i>>j) & 1:
            for k in range(len(num3[j])):
                num2[num3[j][k]-1]+=1
    for j in range(m):
        if num2[j]%2!=p[j]:
            num4=1
            break
    if num4==0:
        ans+=1
print(ans)

Solution (Python):

def bitall(n):
    parm = []
    for i in range(1<<n): 
        on = [0 for _ in range(n)] 
        
        for j in range(n):
            if i & (1<<j): 
                on[j] = 1
                
        parm.append(on)
                
    return parm


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

swi_parms = bitall(N)
ans =0

for swi_parm in swi_parms:
    flag = 0
    for k in range(len(K)):
        cnt = 0
        
        for s in S[k]:
            
            if swi_parm[s-1] == 1: cnt += 1
        
        if cnt%2 == P[k]:
            continue
        else:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
D=[]
for i in range(M):
  D.append(list(map(int,input().split())))
  D[-1]=D[-1][1:]
L=list(map(int,input().split()))
count=0
s=[]
for i in range(2**N):
  p = True
  for j in range(M):
    tmp = 0
    for k in range(N):
      if i>>k & 1:
        if k+1 in D[j]:
          tmp+=1
    if not L[j] == tmp%2:
      p = False
      break
  if p:
    s.append(bin(i))
    count+=1
print(count)

Solution (Python):
from itertools import product


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


ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in range(M):
        j_on_cnt=0
        for k in ks[j][1:]:
            j_on_cnt+=i[k-1]
            
        if j_on_cnt%2 != p[j]:
            ok=False
            break
    if ok:
        ans+=1
print(ans)

Solution (Python):
from itertools import product


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

ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in range(M):
        j_on_cnt=0
        for k in ks[j][1:]:
            j_on_cnt+=i[k-1]
            
        if j_on_cnt % 2!=p[j]:
            ok=False
            break
    if ok:
        ans+=1
print(ans)

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




countN = 0
for Nnum in range(2**n):
    txt = bin(Nnum)[2:]
    txt = "0"*(n-len(txt))+txt
    

    for li in range(m):
        ltxt = "0"*n
        for xi in range(len(k[li])):
            point = k[li][xi]-1
            ltxt = ltxt[:point]+"1"+ltxt[point+1:]
        
        count = 0
        for xi in range(n):
            if txt[xi]=="1" and ltxt[xi]=="1":
                count += 1
        if count%2==p[li]:
            switch = True
        else:
            switch = False
            break
    if switch: countN += 1

print(countN)

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


ans = 0


for i in range(2**n):
    on_off = [False]*n
    for j in range(n):
        if ((i>>j)&1):
            on_off[j] = True
    flag = True
    for k in range(m):
        cnt = 0
        for l in dic[k]:
            if on_off[l-1]:
                cnt += 1
        if cnt % 2 != P[k]:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):






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





ans = 0
for s in range(2**N):
    s_bit = format(s,"010b")
    for i,item in enumerate(ks):
        cnt = 0
        for x in item[1:]:
            if s_bit[10-x] == "1":
                cnt += 1
        if cnt%2 != p[i]:
            break
    else:
        ans += 1
        continue
print(ans)

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

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

count = 0

for i in range(2**n):
    b = bin(i)
    sw = [False] * n
    for j in range(n):
        if (i >> j) & 1:
            sw[j] = True

    boollist = []
    for j in range(m):
        k = lis[j][0]
        sl = lis[j][1:]
        total = 0

        for x in sl:
            if sw[x-1]:
                total += 1
        
        if total % 2 == p[j]:
            boollist.append(1)
        else:
            boollist.append(0)
    
    if all(boollist):
        count += 1

print(count)

Solution (Python):
n, m = map(int,input().split())
s_list = []
p_list = []

for i in range(m):
    tmp = []
    tmp = list(map(int,input().split()))
    s_list.append(tmp)

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

ans = 0

for i in range((2**n)):
    bin_i = [int(x) for x in bin(i)[2:]]
    while len(bin_i) != n:
        bin_i.insert(0,0)
    flag = 0
    for j in range(m):
        tmp = 0
        for k in range(1,s_list[j][0]+1):
            tmp += bin_i[s_list[j][k]-1]
        if tmp%2 != p_list[j]:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

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

answer = 0
from itertools import product

for sw in product([0, 1], repeat=N):
    for p, ks in zip(P, KS):
        K = ks[0]
        S = ks[1:]
        if sum([sw[s - 1] for s in S]) % 2 != p % 2:
            break
    else:
        answer += 1

print(answer)

Solution (Python):
def solve(Switch, K, P):
    count = 0
    for l_1 in K:
        total = 0
        for i_1 in l_1:
            total += Switch[i_1-1]
        if total % 2 != P[count]:
            return False
        count += 1
    return True

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

ans = 0

for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) &1):
            switch[j] = 1
    if solve(switch, k, p):
        ans+=1

print(ans)

Solution (Python):
n, m = map(int, input().split())
state = []
for _ in range(m):
  lst = list(map(int, input().split()))
  state.append(lst[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
  total = 0
  for j in range(m):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
  if total == m:
    ans += 1
print(ans)

Solution (Python):
from itertools import combinations
n,m = map(int,input().split())
l = []
for i in range(m):
    u = list(map(int,input().split()))
    u = u[1:]
    l.append(u)

p = list(map(int,input().split()))
v = []
for i in range(1,n+1):
    v.append(i)

c = []
for i in range(n+1):
    a = combinations(v,i)
    for k in a:
        c.append(k)

ans = 0
for ele in c:
    s = set(ele)
    f = 0
    for i in range(len(l)):
        x = l[i]
        cnt = 0
        for j in x:
            if j in s:
                cnt = cnt+1

        if cnt%2 != p[i]:
            f = 1
            break

    if f == 0:
        ans = ans+1

print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
V = [list(map(lambda x: int(x) - 1, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
res = 0
for i in range(1 << N):
    B = format(i, f'0{N}b')[::-1]
    flg = True
    for j in range(M):
        cnt = 0
        for s in V[j]:
            if B[s] == '1':
                cnt += 1
        if cnt % 2 != P[j]:
            flg = False
    res += int(flg)
print(res)

Solution (Python):









import os
import sys




def main():
    n, m = map(int, input().split())
    switch_list = []
    for _ in range(m):
        command = list(map(int, input().split()))
        _ = command[0]
        switch_list.append(command[1:])
    p = list(map(int, input().split()))
    ans = 0
    for i in range(1 << n):
        flag = 1
        for j, switch in enumerate(switch_list):
            cnt = 0
            for s in switch:
                if 1 & i >> (s-1):
                    cnt += 1
            if cnt % 2 != p[j]:
                flag = 0
                break
        if flag == 1:
            ans += 1

    print(ans)






if __name__ == "__main__":
    main()

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        
        swich[s[j] - 1] ^= 1 << (i)
        
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    if p_list[i] == 1: 
        p += 1 << i
    



ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    
print(ans)

Solution (Python):

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        swich[s[j] - 1] += 1 << (i)
        
        
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    if p_list[i] == 1: 
        p += 1 << i
    



ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    
print(ans)

Solution (Python):

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        
        
        swich[s[j] - 1] |= 1 << (i)
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    
    
    p |= p_list[i] << i 



ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    
print(ans)

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

switch = []
for i in range(m):
    line = list(map(int, input().split()))
    k, s = line[0], line[1::]
    switch.append(s)

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


res = 0
for i in range(1 << n):
    on_off_state = []
    for index in range(n):
        if i >> index & 1 == 1:
            on_off_state.append("on")
        else:
            on_off_state.append("off")
    for ki in range(m):
        on_off_counter = 0
        for i_switch in switch[ki]:
            if on_off_state[i_switch - 1] == "on":
                on_off_counter += 1
        if on_off_counter % 2 != is_on_off[ki]:
            break
    else:
        res += 1
    

print(res)

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


num = 0
limit = 2**n
ans = 0
while(num < limit):
    
    isOK = True
    for i in range(m):
        cnt = 0
        for x in l[i]:
            if((num >> (x-1)) & 1):
                cnt += 1
        
        if(cnt%2!=odd_even[i]):
            isOK = False
            break        
        
    if(isOK):
        ans += 1    
    
    num += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
K = [0]*m
S = [[] for _ in range(m)]
for i in range(m):
    K[i], *S[i] = map(lambda x:int(x)-1, input().split())
    K[i] += 1
P = list(map(int, input().split()))

ans = 0
for i in range(pow(2,n)):
    B = bin(i)[2:].zfill(n)
    D = {j:True if b=='1' else False for j,b in enumerate(B)}
    _P = []
    for j,s in enumerate(S):
        _P.append(sum(D[_s] for _s in s)%2 == P[j])
    if all(_P):
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    ks = list(map(int, input().split()))
    _k = ks[0]
    _s = [ks[i] for i in range(1, len(ks))]
    k.append(_k)
    s.append(_s)
p = list(map(int, input().split()))

def get_bits_pattern(n):
    bits_pattern = []
    for i in range(2**n):
        bits = [False]*n

        for j in range(n):
            if i >> j & 1:
                bits[j] = True
        bits_pattern.append(bits)
    return bits_pattern

bits_pattern = get_bits_pattern(n)

pattern_counter = 0
for bits in bits_pattern:
    is_on = True
    for _s, _p in zip(s, p):
        counter = 0
        for __s in _s:
            if bits[__s-1]:
                counter += 1
        if _p != counter % 2:
            is_on = False
    if is_on:
        pattern_counter += 1

print(pattern_counter)

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

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

ans = 0

for switch in range(2**n):
    check = [0] * m
    for i, bulb in enumerate(bulbs):
        cnt = 0
        for b in bulb:
            if switch >> (b-1) & 1:
                cnt += 1
            
        if cnt % 2 == p[i]:
            check[i] = True
        else:
            check[i] = False
    
    if  all(check):
        ans += 1

print(ans)

Solution (Python):
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=0
for i in range(2**n):
  bit=format(i,'0'+str(n)+'b')
  bit=list(map(int,bit))
  on_den=0
  for den in range(m):
    on_swi=0
    for s in S[den]:
      on_swi+=bit[s-1]
    if on_swi%2==P[den]:
      on_den+=1
  if on_den==m:
    ans+=1
print(ans)