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
from collections import Counter
from collections import defaultdict
import bisect

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

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

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

    
    

    ans = 0
    
    pattern = 1 << N
    for i in range(pattern):
        scope = []
        for j in range(N):
            if (i >> j) & 1:
                scope.append(j + 1)

        if len(scope) > 0:
            turn_on = True
            for j in range(len(S)):
                switches = S[j]
                c = 0
                for states in scope:
                    if states in switches:
                        c += 1
                if c % 2 != P[j]:
                    turn_on = False
                if not turn_on:
                    break
            if turn_on:
                
                ans += 1
        else:
            turn_on = True
            for j in range(len(S)):
                if P[j] != 0:
                    turn_on = False
            if turn_on:
                ans += 1


    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
n,m=map(int,input().split())
L=[]
for i in range(m):
  a,*l=map(int,input().split())
  L+=[l]
S=list(map(int,input().split()))
ans=0
for i in itertools.product([0,1], repeat=n):
  f=0
  for l,s in zip(L,S):
    ls=0
    for ll in l:
      ls+=i[ll-1]
    if ls%2==s:
      f+=1
  if f==m:
    ans+=1
print(ans)

Solution (Python):





def bin_cnt(n):
  ret = 0
  while n > 0:
    if n%2==1:
      ret += 1
    n = n//2
  return ret


N,M = map(int, input().split())
Sn = []
for i in range(M):
  ln = list(map(int, input().split()))
  s_bin = 0
  for l in ln[1:]:
    s_bin += 2**(l-1)
  Sn.append([0,s_bin])
Pn = list(map(int, input().split()))
for i in range(M):
  Sn[i][0] = Pn[i]

ans = 0
for i in range(2**N):
  chk = True
  for s in Sn:
    if s[0] != bin_cnt(i&s[1])%2:
      chk = False
  if chk:
    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(1<<n):
    val=[]
    tmp=i
    for j in range(n):
        val.append(tmp%2)
        tmp//=2
    if all(sum(val[k-1] for k in ks[j][1:])%2==p[j] for j in range(m)):
        ans+=1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = MI()
    switch_pat = []
    for i in range(M):
        k, *s = MI()
        switch_pat.append(s)
    p = LI()
    ans = 0
    for bit in range(2 ** N):
        frag = False
        for m in range(M):
            cnt = 0
            for switch in switch_pat[m]:
                if 1 << (switch-1) & bit:
                    cnt += 1
            if cnt % 2 == p[m]:
                continue
            else:
                frag = True
                break
        if not frag:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int,input().split())
k = []
s = []
for i in range(M):
    l = list(map(int,input().split()))
    k.append(l[0])
    s.append(l[1:])
p = list(map(int,input().split()))
ans = 0
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    f = True
    for i in range(M):
        sum = 0
        for j in range(k[i]):
            if n[-s[i][j]] == '1':
                sum += 1
        if sum%2 != p[i]:
            f = False
    if f:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = [0] * N
L = [0] * M
for i in range(M):
  L[i] = [int(x) - 1 for x in input().split()]
P = [int(x) for x in input().split()]
cnt = 0
for i in range(2 ** N):
  n = i
  for j in range(N):
    S[j] = n % 2
    n //= 2
  for k in range(M):
    L[k][0] = 0
    for l in L[k][1:]:
      L[k][0] ^= S[l]
  light = True
  for k in range(M):
    light &= (L[k][0] == P[k])
  cnt += 1 if light else 0
print(cnt)

Solution (Python):
import itertools


def is_bright(switch, status, p):
    count = 0
    for s in switch:
        if status[s - 1]:
            count += 1
            
    return count % 2 == p


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

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

count = 0
for status in itertools.product(*[[True, False]] * n):
    for switch, p in zip(switches, ps):
        if not is_bright(switch, status, p):
            break
    
    else:
        count += 1

print(count)

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

x = []
for i in range(2**n):
    x.append(format(i,'0b').zfill(n))

ans = 0
for i in range(2**n):
    for j in range(m):
        b = 0
        for k in range(len(s[j])-1):
            if x[i][s[j][k+1]-1]=='1':
                b+=1
        if b%2!=p[j]:
            break
        if j==m-1:
            ans += 1

print(ans)

Solution (Python):

















import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")





N, M = s_inpl()
ks = []
for _ in range(M):
    k = l_inpl()
    ks.append(k[1:])

ps = l_inpl()
cnt = 0
for i in range(2**N):
    on_ss = []
    for j in range(N):
        if ((i>>j) & 1):
            on_ss.append(j+1)
    
    flag = True
    for k, p in zip(ks, ps):
        if len(set(k)&set(on_ss)) % 2 != p:
            flag = False
            break
    if flag:
        cnt += 1

print(cnt)

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


dic_connect={}

for _ in range(M):
    X=list(map(int,input().strip().split(' ')))
    X=X[1:]
    for x in X:
        if x in dic_connect:
            dic_connect[x]+=[_+1]
        else:
            dic_connect[x]=[_+1]    


P=[-1]+list(map(int,input().strip().split(' ')))
count=0

def check(s,N,M):
    count_bulbs=[0]*(M+1)
    for i in range(len(s)):
        if s[i]=='1':
            switch=i+1
            if switch in dic_connect:
                for b in dic_connect[switch]:
                    count_bulbs[b]+=1
    
    for i in range(1,M+1):
        if (count_bulbs[i]-P[i])%2!=0:
            return 0
    
    return 1



for i in range(2**N):
    s="0"*(N-len(bin(i)[2:]))+bin(i)[2:]
    count+=check(s,N,M)
print(count)

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


p = list(map(int,input().split()))
ans = 0  
for k in range(2**n):
  f = 1
  b = format(k, '010b')[::-1]
  for i in range(m):
    c = p[i]
    for j in s[i]:
      c += int(b[j])
    if c%2 == 1:
      f = 0
      break
  ans += f
      
print(ans)

Solution (Python):
from itertools import product

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

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

res = 0

for i in product(range(2), repeat=N) :
    flag = True
    for j in range(M) :
        tmp = 0
        for s in ks[j][1:] :
            tmp += i[s-1]
        
        if tmp % 2 != p[j] :
            flag = False
            break
    if flag :
        res += 1

print(res)

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,m = map(int,input().split())
kss=[]
ans = 0
for i in range(m):
    ks = list(map(int,input().split()))
    kss.append(ks)
p = list(map(int,input().split()))
for i in range(2**n):
    switch = set()
    for j in range(n):
        if (i>>j)&1:
            switch.add(j+1)

    bool = True
    for k in range(m):
        if len(set(kss[k][1:])&switch)%2 == p[k]:
            continue
        else:
            bool = False
    if bool:
        ans += 1
print(ans)

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

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

total = 0
import itertools
for p in itertools.product([0, 1], repeat=N):
    good = True
    for i, switch in enumerate(switches):
        ons = 0
        for si in switch:
            ons += p[si-1]
        if ons % 2 != mods[i]:
            good = False
            break
    if good:
        total += 1

print(total)

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

for mm in range(m):
  ks = list(map(int, input().split()))
  k = ks[0]
  s = ks[1:]
  kss.append(s)
ps = list(map(int, input().split()))

ok_count = 0
combs = [[0,1]]*n
for state in itertools.product(*combs):
  ok = True
  for mm in range(m):
    sm = 0
    for s in kss[mm]:
      sm += state[s-1]
    if sm % 2 != ps[mm]:
      ok = False
      break
  if ok:
    ok_count += 1
print(ok_count)

Solution (Python):
import sys

from fractions import gcd





from itertools import accumulate













input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())



MOD = 2  


if __name__ == '__main__':
    N, M = mi()
    s = []
    k = [0]*M
    for i in range(M):
        k[i], *tmp = lmi()
        
        s.append(tmp)
    
    p = lmi()
    cnt = 0
    for i in range(2 ** N):
        flag = True
        for num in range(M):
            tmp_cnt = 0
            for sw in s[num]:
                if ((i >> sw - 1) & 1):
                    tmp_cnt += 1
            if tmp_cnt % 2 == p[num]:
                continue
            else:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)

Solution (Python):

"""



"""
import sys


from itertools import product

def solve(N, M, lights, P):
    ans = 0
    for p in product([0, 1], repeat=N):
        on_light = 0
        for i, l in enumerate(lights, start=1):
            on = 0
            for ll in l[1:]:
                if p[ll-1]:
                    on += 1
            if on % 2 == P[i-1]:
                on_light += 1
        if on_light == M:
            ans += 1
    return ans



def main(args):
    N, M = map(int, input().split())
    lights = [[int(i) for i in input().split()] for _ in range(M)]
    P = [int(p) for p in input().split()]
    ans = solve(N, M, lights, P)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

import itertools as it

N, M = map(int, input().split())
xss = [[int(s) for s in input().split()][1:] for _ in range(M)]
ps = [int(s) for s in input().split()]

iterable = it.product([0, 1], repeat=N)
cnt = 0
for switches in iterable:
    res = True
    for xs, p in zip(xss, ps):
        selected = [switches[x - 1] for x in xs]
        is_on = (sum(selected) % 2) == p
        res = res and is_on

    if res:
        cnt += 1

print(cnt)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

ks = [LIST() for _ in range(M)]

p = LIST()

ans = 0
for i in range(1<<N):  
	i = list("{:b}".format(i).zfill(N))
	flag = True
	for j, lis in enumerate(ks):
		lis = lis[1:]
		tmp = 0
		for l in lis:
			if i[l-1] == '1':
				tmp += 1
		if tmp % 2 != p[j]:
			flag = False
			break
	if flag:
		ans += 1
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))

def main():
    N,M = ints_raw()
    SS =[0]*(N+1)
    for midx in range(M):
        ks = ints_raw()
        for j in ks[1:]:
            SS[j-1] += 1<<midx
    p = 0
    pis = ints_raw()
    for midx in range(M):
        pi = pis[midx]
        if pi>=2:
            return 0
        if pi ==1:
            p+=1<<midx
    ans = 0
    for dbit in range(2**N):
        tmp = 0
        for j in range(N):
            if (dbit & (1<<j)):
                tmp = tmp^SS[j]
        if tmp == p:
            ans+=1
    return ans

print(main())

Solution (Python):

def main():
    nn, m = map(int, raw_input().split())
    ss = []
    for _ in xrange(m):
        n = 0
        for s in map(int, raw_input().split()[1:]):
            n |= 1 << (s - 1)
        ss.append(n)
    pp = map(int, raw_input().split())
    ans = 0
    for sw in xrange(2 ** nn):
        for s, p in zip(ss, pp):
            if bin((sw & s)).count('1') % 2 != p:
                break
        else:
            ans += 1
    print ans


if __name__ == '__main__':
    main()

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

light_num = [0] * (m+1)
for i in range(2**n):
    light = 0
    for j in range(m):
        val = 0
        for k in ks[j]:
            if i & 1 << (k-1):
                val += 1
        if val % 2 == p[j]:
            light += 1
    light_num[light] += 1
print(light_num[m])

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

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

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

for i in range(2**n):
    flag = 0
    for j in range(m):
        count = 0
        for sj in s[j]:
            if (1 << (sj-1)) & i:
                count += 1
        if count % 2 != p[j]:
            flag = 1
            break
    if flag:
        continue
    ans += 1

print(ans)

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()))
ans=0
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  f=True
  for j in range(m):
    x=k[j]
    c=0
    for h in x:
      if s[h-1]=="0":c+=1
    if c%2!=p[j]:f=False
  if f:ans+=1
print(ans)

Solution (Python):
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

n,m = map(int,input().split())
bulb = []

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

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




ans = 0

for i in range(2**n):
    sw = bin(i)[2:].zfill(n)
    sw = list(map(int,list(sw)))
    
    on = 0
    for j in range(m):
        temp = 0
        for b in bulb[j]:
            if sw[b-1] == 1:
                temp += 1
        if temp % 2 == p[j]:
            on += 1
    if on == m:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
li = [[] for _ in range(N)]
for i in range(M):
    for ma in s[i]:
        li[ma - 1].append(i)
ans = 0
for i in range(2 ** N):
    l = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for r in li[j]:
                l[r] ^= 1
    if l == p:
        ans += 1
print(ans)

Solution (Python):
from itertools import product
n,m=map(int,input().split())
a=[]
for i in range(m):
     a.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
x=[0,1]
x=list(product(x,repeat=n))
c=0
for k in x:
     f=True
     for i in range(m):
          a_=a[i]
          cnt=0
          for j in a_:
               cnt+=k[j-1]
          cnt%=2
          if cnt!=p[i]:
               f=False
               break
     c+=f
print(c)

Solution (Python):



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

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

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

import itertools


answer = 0
for tpl in itertools.product([0,1],repeat=N):
  bl = True
  for i in range(M):
    
    s = sum([tpl[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    answer += 1
print(answer)

Solution (Python):
def bi(x,n):
    o = [0]*n
    c = 0
    while x > 0:
        o[c] = x % 2
        c += 1
        x //= 2
    return o

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

c = 0
for j in range(2**N):
    o = bi(j,N)
    a = True
    for i in range(M):
        a = a and sum([o[x-1] for x in s[i]])%2 == p[i]
    c += a

print(c)

Solution (Python):
import itertools
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(M)]
P=list(map(int,input().split()))
ans=0
for item in itertools.product(range(2),repeat=N):
  if all(sum(item[x-1] for x in L[i][1:])%2==P[i] for i in range(M)):
    ans+=1
print(ans)

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

ans = 0
for perm in product([0, 1], repeat=(N + 1)):
    on_light = 0
    for i, s in enumerate(S):
        on_switch = 0
        for si in s:
            if perm[si] == 1:
                on_switch += 1

        if on_switch % 2 == P[i]:
            on_light += 1

    if on_light == M:
        ans += 1

print(ans // 2)

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

flag_list = []
for i in range(M):
    l=list(map(int,input().split()))
    flag = [False for s in range(N)]
    for j in l[1:]:
        flag[j-1]=True
    flag_list.append(flag)

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

count = 0
for i in range(2**N):
    
    flg=True
    for k in range(M):
        parit=0
        val = i
        for j in range(N):
            decode=val%2
            if flag_list[k][j]:
                parit+=decode
            val = val//2
        if parit%2!=p[k]:
            flg=False
            break
    if flg:
        count+=1

print(count)

Solution (Python):
N, M = map(int, input().split(" "))
lines = []
for i in range(M):
    line = list(map(int, input().split(" ")))
    lines.append(set(line[1:]))

P = list(map(int, input().split(" ")))
ans = 0
for i in range(1 << N):
    on = set()
    for j in range(N):
        if ((i >> j) & 1) == 1:
            on.add(j+1)

    flag = True
    for k, switches in enumerate(lines):
        if len(on & switches) % 2 == P[k]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
def getN():
    return int(input())

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

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

n, m = getMN()

sws = []
for i in range(m):
    sw = getlist()
    sws.append(sw[1:])
ans = 0
mods = getlist()

for i in range(2**n):
    flags = bin(i)[2:]
    flags = "0"*(n-len(flags)) + flags

    
    right = 0
    for idx, sw in enumerate(sws):
        tmp = 0
        
        for s in sw:
            if flags[s-1] == "1":
                tmp +=1

        if tmp % 2 == mods[idx]:
            right += 1

        if right == m:
            ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
s = [list(map(int, input().split()[1:])) for _ in range(m)]
p = list(map(int, input().split()))
ret = 0
for b in range(1 << n):
    if all(sum((b >> (i - 1)) & 1 for i in s[j]) % 2 == p[j] for j in range(m)):
        ret += 1
print(ret)

Solution (Python):
N, M = list(map(int, input().split(" ")))
sws = []
for i in range(M):
    tmp = list(map(int, input().split(" ")))[1:]
    sws.append(sum(2 ** (i - 1) for i in tmp))
p = list(map(int, input().split(" ")))

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

Solution (Python):


def to_b(arr):
    ret = 0
    for i in arr:
        ret |= (1<<(i-1))
    return ret

def bc(num):
    return bin(num).count("1")

def main():
    N,M = [int(a) for a in input().split()]
    KS = [[int(a) for a in input().split()] for i in range(M)]
    P = [int(a) for a in input().split()]
    
    masks = [to_b(ks[1:]) for ks in KS]
    ans = 0
    for i in range(2**N):
        if all([bc(i&mask)%2==p for mask, p in zip(masks, P)]):
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M = (int(x) for x in input().split())

S_arr_arr = []
for _ in range(M):
    S_arr = [int(x) for x in input().split()][1:]
    S_arr_arr.append(S_arr)
P_arr = [int(x) for x in input().split()]

ans = 0
for i in range(1 << N):
    success_flag = True
    for S_arr, P in zip(S_arr_arr, P_arr):
        s_count = 0
        for S in S_arr:
            if i & (1 << (S-1)) != 0:
                s_count += 1
        if s_count % 2 != P:
            success_flag = False
            break
    if success_flag:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
s = []
for i in range(M):
    s.append([int(i) for i in input().split()])
p = [int(i) for i in input().split()]
ans = 0
for i in range(2 ** N):
    sw = [(i >> j) & 1 for j in range(N)]
    for k, e in enumerate(s):
        c = 0
        for l in e[1:]:
            c += sw[l - 1]
        if c % 2 != p[k]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, raw_input().split())
s = [[int(t)-1 for t in raw_input().split()[1:]] for _ in range(M)]
p = map(int, raw_input().split())

ans = 0
for b in range(1<<N):
  ok = True
  for i in range(M):
    c = 0
    for t in s[i]:
      if b>>t&1:
        c += 1
    if c%2!=p[i]:
      ok = False
  if ok:
    ans += 1
print ans

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

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

res = 0

for i in range(2**n):
    s = []
    for j in range(n):
        if i>>j&1==1:
            s.append(j+1)
    flag = True
    for mi in range(m):
        cnt = 0
        for si in s:
            if si in sl[mi]:
                cnt += 1
        if cnt%2!=p[mi]:
            flag = False
        if not flag:
            break
    if flag:
        res += 1

print(res)

Solution (Python):
import itertools


def main():
    N, M = map(int, input().split())
    connect = [set() for _ in range(N)]
    for i in range(M):
        tmp = list(map(int, input().split()))
        for s in tmp[1:]:
            connect[s-1].add(i)
    P = list(map(int, input().split()))
    ans = 0
    for x in itertools.product([True, False], repeat=N):
        cnt = [0] * M
        for i in range(N):
            if x[i]:
                for c in connect[i]:
                    cnt[c] += 1
        ok = True
        for i in range(M):
            if cnt[i] % 2 != P[i]:
                ok = False
        if ok:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


n,m = [int(i) for i in input().split()]
sw = []
for j in range(m):
    k,*l = [int(i)-1 for i in input().split()]
    sw.append(l)
p = [int(i) for i in input().split()]


ans = 0
for i in range(2**n):
    ok=1
    for j in range(m): 
        a=0
        for c in sw[j]:
                a += (1 if i&(2**c) else 0)

        if a%2 != p[j]:
            ok=0
            break

    if ok:
        ans += 1

            
print(ans)

Solution (Python):
def count(state: int, ss: list):
    res = 0
    for s in ss:
        res += ((state >> s) & 1)
    return res


assert count(0b011, [0, 1]) == 2
assert count(0b011, [2]) == 0


def is_on(state: int, p: int, ss: list):
    return count(state, ss) % 2 == p


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

    sss = [
        list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(M)
    ]

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

    cnt = 0
    for state in range(0, 2**N):
        cnt += all(map(lambda x: is_on(state, x[0], x[1]), zip(ps, sss)))
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd
readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

MOD = 2  


def main():
    N, M = readIntN()
    ks = []
    ss = []
    for i in range(M):
        tmp = readIntN()
        ks.append(tmp[0])
        ss.append(tmp[1:])
    ps = readIntN()

    qs = [] 
    for s in ss:
        q = 0
        for c in s:
            q |= (1 << (c - 1))
        qs.append(q)

    ret = 0
    for i in range(1 << N):
        ok = True
        for q, p in zip(qs, ps):
            ok &= (bin(i & q).count('1') % MOD) == p
        if ok:
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Solution (Python):

N, M = [int(n) for n in input().split()]
ss = [0 for i in range(M)]
for i in range(M):
    ss[i] = set([int(n)-1 for n in input().split()][1:])
p = [int(n) for n in input().split()]
ans = 0
for pt in range((1 << N)):
    each = [0]*M
    for i in range(N):
        if (1 << i) & pt:
            for iss in range(len(ss)):
                if i in ss[iss]:
                    each[iss] +=1
    OK = True

    for i in range(len(each)):
        if each[i]%2 != p[i]:
            OK = False
    if OK:
        ans+=1
print(ans)

Solution (Python):
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    N, M = map(int, line_input())
    ks = [[int(i) for i in line_input()] for j in range(M)]
    p = [int(i) for i in line_input()]
    ans = 0
    for i in range(2 ** N):
        onoff = str(format(i, "b").zfill(N))
        for m in range(M):
            onnum = 0
            for k in ks[m][1:]:
                if onoff[k-1] == "1": onnum += 1
            if onnum % 2 != p[m]: break
        else: ans += 1
    print(ans)
        
    return 0
  
if __name__ == "__main__":
    solve()

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

sws = []

for _ in range(M):
	items = list(map(int, input().split(" ")))
	sws.append([items[i + 1] - 1 for i in range(items[0])])

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

def check(sw):
	for i in range(M):
		items = sws[i]
		c = 0
		for j in items:
			c += sw[j]
		if c % 2 != plist[i]:
			return False
	return True

f = "{:0" + str(N) + "b}"
count = 0
for i in range(2 ** N):
	sw = [s == "1" for s in f.format(i)]
	if check(sw):
		count += 1
print(count)

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

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append([int(i) for i in input().split()[1:]])
p=[int(i)*(-2)+1 for i in input().split()]
ans=0
for state in range(2**n):
    chk=True
    for j in range(m):
        ll=l[j]
        test=1
        for i in ll:
            test*=-2*((state>>(i-1))&1)+1
        if test!=p[j]:
            chk=False
    if chk:
        ans+=1
print(ans)

Solution (Python):


from itertools import product

n, m = [int(x) for x in input().split()]
s = [[int(x) - 1 for x in input().split()][1:] for i in range(m)]
p = [int(x) for x in input().split()]

ans = 0

for ss in product((0, 1), repeat=n):
    for st, par in zip(s, p):
        if (sum(ss[sti] for sti in st) & 1) != par:
            break
    else:
        ans += 1

print(ans)