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 = map(int, input().split())
k_list = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for i in itertools.product([0, 1], repeat=n):
    test = True
    for j in range(m):
        count = 0
        for s in k_list[j][1:]:
            count += i[s-1]
        if count % 2 != p[j]:
            test = False
            break
    if test:
        ans += 1

print(ans)

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

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

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

for i in range(2**N):
    switch_flag=[0]*N
    for j in range(N):
        flag = 0
        switch_flag[j]=(i>>j)&1
    for k in range(M):
        total = 0
        for l in range(switch[k][0]):
            if switch_flag[switch[k][l+1]-1] == 1:
                total += 1
        if total%2 == P[k]:
            flag += 1
    if flag == 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()))
ans=0
for s in range(1<<N):
    for j in range(M):
        cnt=0
        for h in ks[j][1:]:
            h-=1
            if (s>>h)&1:
                cnt+=1
                cnt%=2
        if cnt!=p[j]:
            break
    else:
        ans+=1
print(ans)

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


bulb = []
for _ in range(M):
    enc = 0
    s = list(map(int, input().split(" ")))
    for k in range(s[0]):
        enc = enc | (1 << (s[k + 1] - 1))
    bulb.append(enc)

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

ans = 0
for s in range((1 << N)):
    count = 0
    for i, enc in enumerate(bulb):
        if bin(enc & s).count("1") % 2 == p[i]:
            count += 1
    if count == M:
        ans += 1
print(ans)

Solution (Python):

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


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

for i in range(2 ** n):
  num_list = []
  for j in range(n):
    if (i >> j) & 1:
      num_list.append(j + 1)
  
  count_flag = True
  for _index, lamp in enumerate(lamp_list):
    lamp_counter = 0
    for lamp_num in lamp[1:]:
      if lamp_num in num_list:
        lamp_counter += 1
    if lamp_counter % 2 != p[_index]:
      count_flag = False
      break
  if count_flag:
    
    counter += 1
  
print(counter)

Solution (Python):
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd 
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) 


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


ans = 0
for i in range(2**n):
    on = []
    for j in range(n):
        if ((i>>j) & 1):
            on.append(j)
    
    allon = True
    for j in range(m):
        sumv = 0
        for x in s[j]:
            if (x - 1) in on:
                sumv += 1
        
        if sumv%2 != p[j]:
            allon = False
            break
    if allon:
        ans += 1

print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import itertools
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 bit in range(1 << n):
    ptn = bin(bit)[2:].rjust(n,'0')
    light = True
    for j in range(m):
        tmp = 0
        for k in range(1, s[j][0] + 1):
            if ptn[s[j][k] - 1] == '1':
                tmp += 1
        if tmp % 2 != p[j]:
            light = False
    if light:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int, input().split())
sbit = [0] * M
for i in range(M):
  l = list(map(int, input().split()))
  bit = 0
  for j in range(1, l[0] + 1):
    bit += 1 << (l[j] - 1)
  sbit[i] =  bit
p = list(map(int, input().split()))

total = 0
for tbit in range(2 ** N):
  flg = True
  for i in range(M):
    bit = sbit[i] & tbit
    bits = 0
    while bit > 0:
      if bit & 1:
        bits += 1
      bit = bit >> 1
    if bits % 2 != p[i]:
      flg = False
      break
  if flg:
    total += 1
print(total)

Solution (Python):
from itertools import product

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


ans = 0
for c in a:  
    cnt = 0
    for i in range(M):  
        tmp = 0
        for t in s[i]:  
            tmp += c[t - 1]  
            
        if tmp % 2 == p[i]:
            cnt += 1
    if cnt == M:  
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
swl = []
ans = 0

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

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

for i in range(2**n): 
    for sw, p in zip(swl, pl):
        odd = False
        for a in sw:
            if i & 1 << (a - 1): 
                odd = not odd
        if int(odd) != p:
            break
    else:
        ans += 1

print(ans)

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

lights = []
for i in range(m):
    lights.append([int(_) for _ in input().split(' ')[1:]])

rules = [int(_) for _ in input().split(' ')]

patterns = []
for i in range(2**n):
    tmp = ['off'] * n
    for j in range(n):
        if (i >> j & 1):
            tmp[j] = 'on'
    patterns.append(tmp)

count = 0
for p in patterns:
    bright = 0
    for i in range(m):
        on_count = 0
        for switch in lights[i]:
            if(p[switch-1] == 'on'):
                on_count += 1
        if(on_count%2 == rules[i]):
            bright += 1
    if(bright == m):
        count += 1
        
print(count)

Solution (Python):
def get_switch(i, N):
    ans = list()
    for _ in range(N):
        ans.append(i%2)
        i //= 2
    return ans

def turn_light(switch, k_s, p, N, M):
    for i in range(M):
        count = 0
        for j in range(1, k_s[i][0]+1):
            if switch[k_s[i][j]-1] == 1:
                count += 1
        
        if count % 2 != p[i]:
            return 0
    
    return 1

N, M = map(int, input().split())
k_s = list()
for i in range(M):
    k_s.append(list(map(int, input().split())))

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

ans = 0
for i in range(2**N):
    switch = get_switch(i, N)
    ans += turn_light(switch, k_s, p, N, M)

print(ans)

Solution (Python):
import sys
N, M = map(int, input().split())
k = []
s = []
for _ in range(M):
    input_list = list(map(int, sys.stdin.readline().split()))
    k.append(input_list[0])
    s.append(input_list[1:])
p = list(map(int, sys.stdin.readline().split()))

count = 0
for i in range(2 ** N):
    bin_str = format(i, 'b')
    if len(bin_str) < N:
        bin_str = '0' * (N - len(bin_str)) + bin_str
    bool = True
    for j in range(M):
        switch_count = 0
        for S in s[j]:
            if int(bin_str[S - 1]) == 1:
                switch_count += 1
        if switch_count % 2 != p[j]:
            bool = False
            break
    if bool:
        count += 1

print(count)

Solution (Python):
n, m = map(int, input().split())
s = []
k = []
for i in range(m):
    ipt = list(map(int, input().split()))
    k.append(ipt[0])
    s.append(ipt[1:])
p = list(map(int, input().split()))
cnt = 0
for sw in (list(format(i, '0{}b'.format(n))) for i in range(2 ** n)):
    for i in range(m):
        if sum([int(sw[j - 1]) for j in s[i]]) % 2 != p[i]:
            break
    else:
        cnt += 1
print(cnt)

Solution (Python):
from itertools import product

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

ans=0
for c in a:  
  cnt=0
  for i in range(M):  
    tmp=0
    for t in s[i]:
      tmp += c[t-1]
    if tmp%2==p[i]:
      cnt +=1
  if cnt==M:
    ans += 1
print(ans)

Solution (Python):


int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    n, m = MI()
    switch = [0 for _ in range(n)]
    for i in range(m):
        l = LI1()
        k = l[0]
        s = l[1:]
        
        for ss in s:
            switch[ss] = switch[ss] | (1 << i)

    
    P = 0
    for j, l in enumerate(LI()):
        P = P | (l << j)
    

    ans = 0
    for i in range(pow(2, n)):
        x = 0
        
        for j in range(n):
            
            if 1 & (i >> j):
                
                x = x ^ switch[j]
                
        if x == P:
            ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

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

num_cases = 0

for i in range(2 ** n):
    flag = 0
    num_on_e = 0
    for j, k in zip(elec, p):
        if flag:
            break
        else:
            switches = j[1:]
            num_on_switch = 0
            for s in switches:
                if i & (1 << s - 1):
                    num_on_switch += 1

            if num_on_switch % 2 == k:
                num_on_e += 1
            else:
                flag = 1
    if num_on_e == m:
        num_cases += 1
print(num_cases)

Solution (Python):


import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() 


def main():
    n,m = na()
    ks = []
    swicthToLight = [[] for _ in range(n)]
    for i in range(m):
        ss = na()
        k = ss.pop(0)
        ks += [k]
        for s in ss:
            swicthToLight[s-1] += [i]
    ps = na()
    ans = 0
    for i in range(pow(2,n)):
        pstmp = [i for i in ps]
        for j in range(n):
            if ((i>>j) & 1):
                for light in swicthToLight[j]:
                    pstmp[light] += 1
                    pstmp[light] %= 2
        if sum(pstmp) == 0:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().rstrip().split(" "))
K = [[]] * M
sw = [False] * N
count = 0
check = True
ans = 0

for i in range(M):
    K[i] = list(map(int,input().rstrip().split(" ")))
P = list(map(int,input().rstrip().split(" ")))


for i in range(2 ** N):
    check = True
    for i2 in range(N):
        sw[i2] = (i >> i2) & 1
    
    for i2 in range(M):
        counter = 0
        for i3 in range(K[i2][0]):
            if sw[K[i2][i3 + 1] - 1]:
                counter += 1
        if counter % 2 != P[i2]:
            check = False
            break
    if check: ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]
t=list(map(int,input().split()))
ans=0
for i in range(2**n):
  bit=[i>>j & 1 for j in range(n)]
  for k,x in enumerate(s):
    if t[k]!=sum([bit[y-1] for y in x[1:]])%2:
      break
  else:
    ans+=1
print(ans)

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

for i in range(2**n):
    ans = [0] * m

    for j in range(n):  
        if ((i >> j) & 1): 
            for k in range(m):
                if j+1 in ks[k][1:]:
                    ans[k] += 1
    flag = True
    for j in range(m):
        if ans[j] % 2 != p[j]:
            flag = False
            break
    if flag:
        aans += 1
print(aans)

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):
    bit = [i>>j & 1 for j in range(N)]
    for k,x in enumerate(ks):
        _,*s = x
        if p[k] != sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
l = []
for i in range(M):
    ks = list(map(int, input().split()))
    k, s = ks[0], ks[1:]
    l.append(s)
    
p = list(map(int, input().split()))

ans = 0
for j in range(2**N):
    n = 0  
    for m in range(M):
        t = 0
        for sw in l[m]:
            if (j>>(sw-1)&1):
                t += 1
        if t%2 == p[m]:
            n += 1
        else:
            break
    if n == M:
        ans += 1
print(ans)

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

count = 0
for i in range(2 ** n):
    on_light = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in switch[k]:
                    on_light[k] += 1
    if all((on_light[i] % 2 == p[i]) for i in range(m)):
        count += 1

print(count)

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

s = [list(map(int, input().split())) for _ in range(m)]
k = [0] * m
for i in range(m):
    k[i] = s[i][0]
    del s[i][0]
p = list(map(int,input().split()))
ans = 0
for b in range(2 ** n):
    sum = 0
    cnt = [0] * m 
    flag = [False] * m
    for j in range(n):
        if b >> j & 1:
            for k in range(m):
                if (j + 1) in s[k]:
                    cnt[k] += 1
    
    for i in range(m):
        if cnt[i] % 2 == p[i]:
            flag[i] = True
    
    if all(flag[i] == True for i in range(m)):
        """
        print(b)
        print(flag)
        """
        ans += 1
print(ans)

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

ans=0

for i in range(2**N):
    swi=bin(i)[2:].rjust(N, "0")
    lights=1

    for j in range(M):
        cnt=0
        for k in range(1, s[j][0]+1):
            if swi[s[j][k] -1] == "1":
                cnt+=1

        if cnt%2 != p[j]:
            lights=0
    
    if lights==1:
        ans+=1

print(ans)

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

ans=0

for i in range(2**N):
    swi=bin(i)[2:].rjust(N, "0")
    lights=1

    for j in range(M):
        cnt=0
        for k in range(1, s[j][0]+1):
            if swi[s[j][k] -1] == "1":
                cnt+=1

        if cnt%2 != p[j]:
            lights=0
    
    if lights==1:
        ans+=1

print(ans)

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

ans=0

for i in range(2**N):
    swi=bin(i)[2:].rjust(N, "0")
    lights=1

    for j in range(M):
        cnt=0
        for k in range(1, s[j][0]+1):
            if swi[s[j][k] -1] == "1":
                cnt+=1

        if cnt%2 != p[j]:
            lights=0
    
    if lights==1:
        ans+=1

print(ans)

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

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

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

ans = 0

for i in range(2**n): 
    for sw, p in zip(l, pl):
        odd = False
        for a in sw:
            if i & 1 << (a - 1): 
                odd = not odd 
        if int(odd) != p: 
            break
    else: 
        ans += 1
print(ans)

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

for i in range(2**n):
    switches_on = [0 for _ in range(m)]
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j+1 in s[k]:
                    switches_on[k] += 1
    light_on = [0 for _ in range(m)]
    for j in range(m):
        if (switches_on[j]%2) != (p[j]%2):
            light_on[j] = False
        else:
            light_on[j] = True
    if all(light_on):
        ans += 1
print(ans)

Solution (Python):



def solve():
    N, M = list(map(int, input().split()))
    denkyu = []
    for i in range(M):
        inputs = list(map(int, input().split()))
        k, Ss = inputs[0], inputs[1:]
        denkyu.append(Ss)
    Ps = list(map(int, input().split()))

    
    ans = 0
    for bits in range(2**N): 
        light = 0  
        for j in range(M): 
            total = 0
            for sw in denkyu[j]: 
                if (bits>>(sw-1)&1):
                    total += 1
            if total%2 == Ps[j]:
                light += 1
            else:
                break
        if light == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
N, M = map(int, input().split())
switch = list()
for i in range(M): 
  x = list(map(int, input().split()))
  switch.append(x[1:])
mod = list(map(int, input().split()))

ans = 0
for n in range(2**N):
  flag = 1
  useswitch = list()
  cnt = [0] * M
  for i in range(N):
    if n>>i & 1 == 1:
      useswitch.append(i+1)
      
  for m in range(M):
    for s in useswitch:
      if s in switch[m]:
        cnt[m] = (cnt[m]+1)%2
        
  
  for i in range(M):
    if(cnt[i] != mod[i]):
      flag = 0
      
  if(flag == 1):
    ans += 1
  
    
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    s=[]
    for i in range(m):
        ss=[int(_) for _ in input().split()]
        s.append(ss[1:])
    P=[int(_) for _ in input().split()]
    ans=0
    for j in range(2**n):
        i=0
        nn=j
        Q=[0]*m 
        while nn>0:
            if ((nn&1)==1):
                for x,ss in enumerate(s):
                    if i+1 in ss:
                        Q[x]+=1
            nn>>=1
            i+=1
        for x,q in enumerate(Q):
            if q%2!=P[x]:
                break
        else:
            ans+=1
    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    s=[]
    for i in range(m):
        ss=[int(_) for _ in input().split()]
        s.append(ss[1:])
    P=[int(_) for _ in input().split()]
    ans=0
    for j in range(2**n):
        i=0
        nn=j
        Q=[0]*m 
        while nn>0:
            if ((nn&1)==1):
                for x,ss in enumerate(s):
                    if i+1 in ss:
                        Q[x]+=1
            nn>>=1
            i+=1
        for x,q in enumerate(Q):
            if q%2!=P[x]:
                break
        else:
            ans+=1
    print(ans)


if __name__=='__main__':
    main()

Solution (Python):
n, m = [int(x) for x in input().split()]

light_list = [0] * m
for i in range(m):
    temp = [int(x) for x in input().split()]
    light = 0
    for j in range(1, temp[0] + 1):
        light |= 1 << (temp[j] - 1)
    light_list[i] = light

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

def popcount(x):
    x = x - ((x >> 1) & 0x5555)
    x = (x & 0x3333) + ((x >> 2) & 0x3333)
    x = (x + (x >> 4)) & 0x0f0f
    x = x + (x >> 8)
    return x & 0xf

ans = 0
for i in range(2 ** n):
    temp = 0
    for j in range(m):
        if popcount(i & light_list[j]) % 2 != p_list[j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
cin = open(0).read().split('\n')

n, m = map(int, cin[0].split(' '))
s = []
for row in cin[1:1+m]:
    s.append(list(map(int, row.split(' ')[1:])))
p = list(map(int, cin[1+m].split(' ')))

ret = 0
for ai in range(2**n):
    flg = True
    for idx, si in enumerate(s):
        on_cnt = 0
        for sii in si:
            if (ai >> (sii-1)) & 1:
                on_cnt += 1
        if on_cnt % 2 != p[idx]:
            flg = False
    if flg:
        ret += 1

print(ret)

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

s = [[] for _ in range(M)]
for i in range(M):
    temp = list(map(int, input().split()))
    s[i] = temp[1:]
p = list(map(int, input().split()))
ans = 0


for i in range(2 ** N):
    on = [0 for _ in range(M)]
    for j in range(N): 
        if (i >> j) & 1:
            for k in range(M):
                if j+1 in s[k]:
                    on[k] += 1
    tf = []
    for on_n, p_n in zip(on, p):
        if on_n % 2 == p_n:
            tf.append(True)
        else:
            tf.append(False)
    if all(flg for flg in tf):
        ans += 1

print(ans)

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

s = [[] for _ in range(M)]
for i in range(M):
    temp = list(map(int, input().split()))
    s[i] = temp[1:]
p = list(map(int, input().split()))
ans = 0


for i in range(2 ** N):
    on = [0 for _ in range(M)]
    for j in range(N): 
        if (i >> j) & 1:
            for k in range(M):
                if j+1 in s[k]:
                    on[k] += 1
    tf = []
    for on_n, p_n in zip(on, p):
        if on_n % 2 == p_n:
            tf.append(True)
        else:
            tf.append(False)
    if all(flg for flg in tf):
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
s = [0] * M
for i in range(M):
    s[i] = list(map(int, input().split()))[1:]
    s[i] = [v - 1 for v in s[i]]

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

ans = 0
for i in range(1 << N):
    all_lit = True
    for j in range(M):
        n = 0
        for k in s[j]:
            n += bool(i & (1 << k))
        if n % 2 != p[j]:
            all_lit = False
            break
    ans += all_lit

print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        if p[j]!=sum([bit[y-1] for y in x[1:]])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        k,*s = x
        if p[j]!=sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        k,*s = x
        if p[j]!= sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
S=[]
K=[]
for i in range(M):
  s=list(map(int,input().split()))
  k=s[0]
  s.remove(s[0])
  K.append(k)
  S.append(s)
P=list(map(int,input().split()))
cnt=0
for i in range(2**N):
  d=[]
  for j in range(M):
    a=0
    for k in S[j]:
      a+=2**(k-1)
    if bin(a&i)[2:].count('1')%2==P[j]:
      d.append(1)
    else:
      d.append(0)
  if not 0 in d:
    cnt+=1
print(cnt)

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

lights = []

for _ in range(M):
  args = [int(x) - 1 for x in input().split()]
  args.pop(0)  
  switches = 0
  for i in args:
    switches |= (1 << i)
  lights.append(switches)
  
P = [int(x) for x in input().split()]

count = 0


for mask in range(1 << N):
  if all(bin(mask & s).count('1') % 2 == P[i] for i, s in enumerate(lights)):
    count += 1
      
print(count)

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

ans = 0
for i in range(2 ** N):
    ok = True
    bit = list(map(int, list(bin(i)[2:].rjust(N, "0"))))
    for S, p in zip(D, P):
        c = len([j for j in range(S[0]) if bit[S[1:][j]-1] == 1])
        if ok and c % 2 != p:
            ok = False
    if ok:
        ans += 1

print(ans)

Solution (Python):
from itertools import product as prod

n, m = map(int, input().split())
ks = [tuple(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0

for pattern in (prod((0, 1), repeat=n)):
    tmp = []
    for i in range(len(ks)):
        rep = 0
        for j in ks[i][1:]:
            if pattern[j - 1] == 1:
                rep += 1
        if (rep & 1) == p[i]:
            tmp.append(True)
        else:
            tmp.append(False)
    if all(tmp):
        ans += 1
print(ans)

Solution (Python):

import sys
import itertools


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


def check(sws):
    on_list = []
    for i in range(M):
        on = 0
        for s in d_dict[i + 1]:
            on += sws[s]
        if on % 2 == p_list[i]:
            on_list.append(True)
        else:
            on_list.append(False)

    return all(on_list)


ans = 0


def dfs(depth, sws):
    global ans

    if depth == 0:
        return check(sws) * 1

    for i in range(2):
        t_sws = sws
        t_sws[depth] = i
        on = dfs(depth - 1, t_sws)
        ans += on

    return 0


N, M = lr()
d_dict = {}
for i in range(M):
    s_list = lr()
    d_dict[i + 1] = s_list[1:]

p_list = lr()

sw_list = [0] * (N + 1)
dfs(N, sw_list)
print(ans)

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


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


sumans = 0

for bit in range(1 << n):
    
    
    flag = True
    for i in range(m):
        sum = 0
        
        for j in lista[i]:
            if bit & (1 << (j - 1)):
                sum += 1
        if sum % 2 != p[i]:
            flag = False
    if flag:
        sumans += 1
print(sumans)

Solution (Python):

inp = input()
switch_num = int(inp.split()[0]) 
light_num = int(inp.split()[1]) 
switch_info = [input() for i in range(light_num)]
p_info = input()


k_list = []
for l in switch_info:
    k_list.append(int(l.split()[0]))
s_list = []
for l in switch_info:
    l_list = [int(i) for i in l.split()[1:]]
    s_list.append(l_list)
p_list = [int(l) for l in p_info.split()]


bit_list = []
for i in range(2 ** switch_num):
    c = format(i,'b').zfill(switch_num)
    bit_list.append(c)
bit_list = [list(i) for i in bit_list]


result = 0
for bit in bit_list:
    on_num = 0
    for i in range(light_num):
        on_light = sum([int(bit[s-1]) for s in s_list[i]])
        
        if p_list[i] == (on_light%2):
            on_num += 1
    if on_num == light_num:
        result += 1

print(result)

Solution (Python):
N,M = map(int,input().split())
lis = [None]*M
for i in range(M):
    lis[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
answer = 0

for bit in range(1<<N):
    count =[]
    for i in range(N): 
        mask = 1<<i
        if mask&bit:
            count.append(1)
        else:
            count.append(0)
        
    for j in range(M):
        temp = 0
        for k in range(lis[j][0]):
            temp+=count[lis[j][k+1]-1]
        if temp%2 != p[j]:
            break
    else:
        answer+=1
print(answer)

Solution (Python):
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 i in range(2 ** N):
    cntFlg = True
    
    for m in range(M):
        
        onSwCnt = 0
        for j in range(L[m][0]):
            
            if (i >> L[m][j+1] - 1) & 1:
                onSwCnt += 1
        if not P[m] == onSwCnt % 2:
            cntFlg = False

    if cntFlg:
        ans += 1

print(ans)

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


ans = 0
for item in itertools.product([0, 1], repeat=n):
    flag = True
    for i, switch in enumerate(switches):
        on_count = 0
        for s in switch:
            on_count += item[s-1]
        if on_count % 2 != p[i]:
            flag = False
    if flag: ans += 1
print(ans)

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

pattern = []
for bit in range(1<<n):
    stock = []
    for i in range(n):
        mask = 2**(n-i-1)
        if mask & bit:
            stock.append(1)
        else:
            stock.append(0)
    pattern.append(stock)

count = 0
for on_off in pattern:
    truf = True
    for j in range(m):
        count_s = 0
        for k in switch_wiring[j]:
            if on_off[k-1] == 1:
                count_s += 1
        if count_s % 2 != p[j]:
            truf = False
            break
    if truf:
        count += 1

print(count)