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



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
import numpy as np


# In[9]:


s = range(N)
cnt = 0
# N個がonになる
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))# N個onになる通り
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(l[i][0]):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
#0個on
o = list(range(N))
for i in range(M):
    sum_ = 0
    for j in range(l[i][0]):
        ind = l[i][j+1]-1
        sum_ += a[ind]
    o[i] = sum_%2==l[-1][i]
if np.all(o):
    cnt += 1
print(cnt)


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
connections=[]
for _ in range(M):
    connections.append(list(map(int,input().split())))
conditions = list(map(int,input.split()))

ans_cnt = 0
for i in range(2**N):
    condition_cnt = 0
    for j in range(M):

        cnt=0
        for k in connections[j][1:]:
            if (i >> k) & 1:
                cnt += 1
        if (cnt +conditions[j])%2 == 0:
            condition_cnt += 1
    if condition_cnt == M:
        ans_cnt += 1

print(ans_cnt)

Submission status: Runtime Error

Solution code:
import itertools
N = int(N)
M = int(M)
line_list = []
for i in range(M):
    line = input().split()
    new_list=[]
    for l in line:
        new_list.append(int(l))
    new_list.pop(0)
    line_list.append(new_list)
old_p_list = input().split()
p_list = []
for p in old_p_list:
    p_list.append(int(p))

A = []
for n in range(N):
    A.append([True,False])
pattern_list = list(itertools.product(*A))
pattern_num = 0
for pattern in pattern_list:
    ok_flug = 1
    for i, line in enumerate(line_list):
            on_num = 0
            for l in line:
                if pattern[l-1]:
                    on_num += 1
            if on_num%2 != p_list[i]:
                ok_flug = 0
    if ok_flug == 1:
        pattern_num += 1
print(pattern_num)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
connections=[]
for _ in range(M):
    connections.append(list(map(int,input().split())))
conditions = list(map(int,input.split()))

ans_cnt = 0
for i in range(2**N):
    condition_cnt = 0
    for j in range(M):

        cnt=0
        for k in connections[j][1:]:
            if (i >> k) & 1):
                cnt += 1
        if (cnt +conditions[j])%2 == 0:
            condition_cnt += 1
    if condition_cnt == M:
        ans_cnt += 1

print(ans_cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
p = []
matrix = np.zeros((M, N))

for m in range(M):
    row = [int(v)-1 for v in input().split()]
    row = row[1:]
    for n in range(N):
        if n in row: matrix[m, n] = 1

p = [int(v) for v in input().split()]
p = np.array([p]).T
matrix = np.hstack([matrix, p])
rank = np.linalg.matrix_rank(matrix)

if N < rank:
    print(0)
elif not any(a):
    print(1)
else:
    print(2**(N-rank))

Submission status: Runtime Error

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

klist = []
sdict = {}
for m in range(M):
    tmp = list(map(int, input().split()))
    klist.append(tmp[0])
    sdict[m] = tmp[1:]
plist = list(map(int, input().split()))

def solve(N, plist, switch_num):
    global M
    num = 0

    if N == 1:
        idx = []
        idx2 = []
        for m in range(M):
            if switch_num in sdict[m]:
                idx.append(plist[m])
            else:
                idx2.append(plist[m])
        if sum(idx) == len(idx):
            if sum(idx2) == 0:
                return 1
            else:
                return 0
        elif sum(idx) == 0:
            if sum(idx2) == 0:
                return 2
        else:
            return 0

    # switch1 == OFF
    new_plist = plist
    num += solve(N-1, new_plist, switch_num+1)
    
    # switch1 == ON
    new_plist = []
    for i in range(M):
        if switch_num in sdict[i]:
            new_plist.append(1 - plist[i])
        else:
            new_plist.append(plist[i])
    num += solve(N-1, new_plist, switch_num+1)

    return num

print(solve(N, plist, 1))

Submission status: Runtime Error

Solution code:
N = int(N)
M = int(M)
line_list = []
for i in range(M):
    line = input().split()
    new_list=[]
    for l in line:
        new_list.append(int(l))
    new_list.pop(0)
    line_list.append(new_list)
old_p_list = input().split()
p_list = []
for p in old_p_list:
    p_list.append(int(p))
#　スイッチ組み合わせ
import itertools
A = []
for n in range(N):
    A.append([True,False])
pattern_list = list(itertools.product(*A))
pattern_num = 0
for pattern in pattern_list:
    ok_flug = 1
    for i, line in enumerate(line_list):
            on_num = 0
            for l in line:
                if pattern[l-1]:
                    on_num += 1
            if on_num%2 != p_list[i]:
                ok_flug = 0
    if ok_flug == 1:
        pattern_num += 1
print(pattern_num)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = []
for i in range(m):
    s.append(list(map(int,input().split())))
    
p = list(map(int,input().split()))
ans = 0
for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        switches = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        flag_temp = 0
                                        for i in range(m):
                                            temp = 0
                                            for l in range(s[i][0]):
                                                temp += switches[s[i][l+1]-1]
                                            if temp % 2 == p[i]:
                                                flag = 1
                                                flag_temp += 1
                                        if flag == 1 and flag_temp == m:
                                            ans += 1
if ans ==0:
    print(ans)
else:
    print(int(ans/2**(10-n)))

Submission status: Runtime Error

Solution code:
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

is_ok = 0
for patterns in itertools.product((0, 1), repeat=M):
    patterns = list(patterns)
    on_light = 0
    for i, light in enumerate(connected_switches):
        turned_sw = 0
        for switch_id in light:
            turned_sw += patterns[switch_id]
        if turned_sw % 2 == conditions[i] if i in conditions else -1:
            on_light += 1
    if on_light == M:
        is_ok += 1

print(is_ok)

Submission status: Runtime Error

Solution code:
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

is_ok = 0
for patterns in itertools.product((0, 1), repeat=M):
    patterns = list(patterns)
    on_light = 0
    for i, light in enumerate(connected_switches):
        turned_sw = 0
        for switch_id in light:
            turned_sw += patterns[switch_id]
        if turned_sw % 2 == conditions[i]:
            on_light += 1
    if on_light == M:
        is_ok += 1

print(is_ok)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = []
for i in range(m):
    s.append(list(map(int,input().split())))
    
p = list(map(int,input().split()))
ans = 0
for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        switches = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        flag_temp = 0
                                        for i in range(m):
                                            temp = 0
                                            for l in range(s[i][0]):
                                                temp += switches[s[i][l+1]-1]
                                            if temp % 2 == p[i]:
                                                flag = 1
                                                flag_temp += 1
                                        if flag == 1 and flag_temp == m:
                                            ans += 1
                                            
print(int(ans/2**(10-n)))

Submission status: Runtime Error

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

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

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

cnt = 0
for i in range(2**N): # スイッチの組み合わせ
    light = 0
    switch = format(i, f'0{N}b')
    for j in range(M): # j番目の電球はどうなってる？
        pj = p[j]
        kj = ks[j][0]
        on = 0
        for l in range(1, kj+1): # 指定されたスイッチ番号はon?
            if switch[ks[j][l]-1] == '1':
                on += 1
        if on % 2 == pj:
            light += 1
        else:
            break
    if light == M:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = raw_input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = raw_input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = raw_input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0

# print(my_list)

for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
S = []
count = [0] * n
for i in range(n):
    a, b = input().split()
    S.append([a, int(b), i + 1])

S.sort()

for i in range(n - 1):
    if S[i][0] != S[i + 1][0]:
        count[i] = 1

for j in range(n-1):
    for i in range(n - 1):
        if S[i][1] < S[i + 1][1] and count[i + 1] - count[i] >= 0:
            a = S[i][:]
            S[i][:] = S[i + 1][:]
            S[i + 1][:] = a
        if count[i + 1] - count[i] < 0:
            continue

for i in range(n):
    print(S[i][2])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

from itertools import combinations_with_replacement, permutations

INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_FLOAT(): return float(INPUT())
def MULTIPLE_FLOAT_LIST(): return list(map(float, INPUT().split()))
def MULTIPLE_FLOAT_MAP(): return map(float, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

n_switches, n_bulbs = MULTIPLE_INT_MAP()
bulbs = np.zeros((n_bulbs, n_switches))
targets = []

for i in range(n_bulbs):
    ipt = MULTIPLE_INT_LIST()

    for j in ipt[1:]:
        bulbs[i, j-1] = 1

targets = MULTIPLE_INT_LIST()

done = set()
ans = 0
for iter1 in combinations_with_replacement([0,1], n_switches):
    
    for iter2 in permutations(iter1):

        current = tuple(iter2)

        if current in done:
            continue

        done.add(current)
        arr = np.array(current)

        for i in range(n_bulbs):
            if targets[i] != np.sum(arr[np.where(bulbs[i])]) % 2:
                flag = False
                break
        
        if flag:
            ans += 1
        else:
            flag = True

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
for _ in range(m):
    kari=list(map(int,input().split()))
    l.append(kari)
p=list(map(int,input().split()))
num2=[]
def deal1():
    ans=0
    for a in range(2):
        w=[a]
        all=0
        for k in range(m):
            cnt==0
            for q in range(l[k][0]):
                if w[l[k][q+1]-1]==1:
                    cnt+=1
            if p[k]==cnt%2:
                all+=1
        if all==m:
            ans+=1
    return ans
def deal2():
    ans=0
    for a in range(2):
        for b in range(2):
            w=[a,b]
            all=0
            for k in range(m):
                cnt=0
                for q in range(l[k][0]):
                    if w[l[k][q+1]-1]==1:
                        cnt+=1
                if p[k]==cnt%2:
                    all+=1
            if all==m:
                ans+=1
    return ans
def deal3():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                w=[a,b,c]
                all=0
                for k in range(m):
                    cnt=0
                    for q in range(l[k][0]):
                        if w[l[k][q+1]-1]==1:
                            cnt+=1
                    if p[k]==cnt%2:
                        all+=1
                if all==m:
                    ans+=1
    return ans
def deal4():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    w=[a,b,c,d]
                    all=0
                    for k in range(m):
                        cnt=0
                        for q in range(l[k][0]):
                            if w[l[k][q+1]-1]==1:
                                cnt+=1
                        if p[k]==cnt%2:
                            all+=1
                    if all==m:
                        ans+=1
    return ans
def deal5():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        w=[a,b,c,d,e]
                        all=0
                        for k in range(m):
                            cnt=0
                            for q in range(l[k][0]):
                                if w[l[k][q+1]-1]==1:
                                    cnt+=1
                            if p[k]==cnt%2:
                                all+=1
                        if all==m:
                            ans+=1
    return ans
def deal6():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            w=[a,b,c,d,e,f]
                            all=0
                            for k in range(m):
                                cnt=0
                                for q in range(l[k][0]):
                                    if w[l[k][q+1]-1]==1:
                                        cnt+=1
                                if p[k]==cnt%2:
                                    all+=1
                            if all==m:
                                ans+=1
    return ans
def deal7():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                w=[a,b,c,d,e,f,g]
                                all=0
                                for k in range(m):
                                    cnt=0
                                    for q in range(l[k][0]):
                                        if w[l[k][q+1]-1]==1:
                                            cnt+=1
                                    if p[k]==cnt%2:
                                        all+=1
                                if all==m:
                                    ans+=1
    return ans
def deal8():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    w=[a,b,c,d,e,f,g,h]
                                    all=0
                                    for k in range(m):
                                        cnt=0
                                        for q in range(l[k][0]):
                                            if w[l[k][q+1]-1]==1:
                                                cnt+=1
                                        if p[k]==cnt%2:
                                            all+=1
                                    if all==m:
                                        ans+=1
    return ans
def deal9():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        w=[a,b,c,d,e,f,g,h,i]
                                        all=0
                                        for k in range(m):
                                            cnt=0
                                            for q in range(l[k][0]):
                                                if w[l[k][q+1]-1]==1:
                                                    cnt+=1
                                            if p[k]==cnt%2:
                                                all+=1
                                        if all==m:
                                            ans+=1
    return ans

def deal10():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        for j in range(2):
                                            w=[a,b,c,d,e,f,g,h,i]
                                            all=0
                                            for k in range(m):
                                                cnt=0
                                                for q in range(l[k][0]):
                                                    if w[l[k][q+1]-1]==1:
                                                        cnt+=1
                                                if p[k]==cnt%2:
                                                    all+=1
                                            if all==m:
                                                ans+=1
    return ans
if n==1:
    print(deal1())
if n==2:
    print(deal2())
if n==3:
    print(deal3())
if n==4:
    print(deal4())
if n==5:
    print(deal5())
if n==6:
    print(deal6())
if n==7:
    print(deal7())
if n==8:
    print(deal8())
if n==9:
    print(deal9())
if n==10:
    print(deal10())

Submission status: Runtime Error

Solution code:
ans = 0
n,m = map(int, input().split())
s_list = []
s_count_list = []
for _ in range(m):
    s = list(map(int,input().split()))
    s_count_list.append(s[0])
    s_list.append(s[1:])
oe = list(map(int,input().split()))   
seq = list(range(1, n+1))
for i in range(1, n+1):
    cmb = list(itertools.combinations(seq,i))
    for j in range(len(cmb)):
        ansv = []
        for k in range(m):
            ss = []
            for l in range(len(s_list[k])):
                if s_list[k][l] in list(cmb[j]):
                    ss.append(s_list[k][l])
            if len(ss)%2 == oe[k]:
                ansv.append(True)
            else:
                ansv.append(False)
        if all(ansv):
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
K = [IL() for i in range(M)]
p = IL()

data = []
for i in range(2**M):
    d = []
    for j in range(M):
        if ((i >> j) & 1) == 1:
            d.append(K[j])
    else:
        data.append(d)

ans = 0
for s in data:
    cnt = [0]*M
    for i in s:
        for j in i[1:]:
            cnt[j-1] += 1
    else:
        for k in range(M):
            if cnt[k]%2 == p[k]:
                continue
            else:
                break
        else:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools


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

lights = []
for i in range(M):
    lights.append([int(x) - 1 for x in input().split()[1:]])

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

is_ok = 0
for mode in itertools.product((0, 1), repeat=M):
    mode = list(mode)
    on = 0
    for i, light in enumerate(lights):
        sw = 0
        for x in light:
            sw += mode[x]
        if sw % 2 == patterns[i]:
            on += 1
    if on == M:
        is_ok += 1

print(is_ok)

Submission status: Runtime Error

Solution code:
def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = raw_input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = raw_input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = raw_input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0

# print(my_list)                                                                                                                                                                                                              

for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)

Submission status: Runtime Error

Solution code:
#from operater import itemgetter
from collections import Counter
import numpy as np
N=int(input())
c=[]
v=[]
ans=[]
c_v={}
for i in range(N):
    tmp=input().split()
    ans.append(tmp)
    c.append(tmp[0])
    v.append(int(tmp[1]))
    if tmp[0] in c_v.keys():
        c_v[tmp[0]].append(int(tmp[1]))
    else:
        c_v[tmp[0]]=[int(tmp[1])]
    
hoge=np.array(list(Counter(c).keys()))
huga=np.argsort(np.array(c))
for i in range(N):
    city=ans[i][0]
    if len(c_v[city])==1:
        print(huga[np.where(hoge==ans[i][0])][0]+1)
    else:
        tmp=np.array(c_v[city])
        h=np.argsort(tmp)[::-1]
        print(huga[np.where(hoge==ans[i][0])][0]+h[c_v[city].index(int(ans[i][1]))]+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
import numpy as np


# In[7]:


s = range(N)
cnt = 0
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))
    #print(c)
    #print(c)
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(len(l[i][1:])):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
print(cnt)


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""

Submission status: Runtime Error

Solution code:
import itertools

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

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

A = [0, 1]
ans = 0
for i in itertools.product(A, repeat = N):
    flag = 0
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i[s - 1] == 1:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1
        
print(ans)

Submission status: Runtime Error

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

data=[]
for i in range(M):
    K,*S = list(map(int,input().split()))
    data.append(S)
p = list(map(int,input().split()))

counter = 0

for i in range(2**M):
    light = [0]*M
    for j in range(M):
        if i%2**j:
            for k in data[j]:
                light[k-1] = light[k-1]+1
    light = [x%2 for x in light]
    if light == p:
        counter += 1

print(str(counter))

Submission status: Runtime Error

Solution code:
N=int(input())
lis=[]
for i in range(N):
    A,B=input().split()
    #print(A,B)
    B=str(999-int(B))
    #print(B)
    lis.append(A+B+'_'+str(i))
               
lis=sorted(lis)
for i in range(N):
    print(int(lis[i].split('_')[1])+1)

Submission status: Runtime Error

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

data=[]
for i in range(M):
    K,*S = list(map(int,input().split()))
    data.append(S)
p = list(map(int,input().split()))

counter = 0

for i in range(2**M):
    light = [0]*M
    for j in range(M):
        if i%2**j:
            for k in data[j]:
                light[k-1] += 1
    light = [x%2 for x in light]
    if light == p:
        counter += 1

print(str(counter))

Submission status: Runtime Error

Solution code:
import itertools

N, M = list(map(int, input().split()))
S = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
cnt = 0
for pattern in itertools.product(*8*[[0, 1]]):
    for i in range(M):
        s = S[i]
        active_swtiches = []
        for switch_n in s:
            active_swtiches += pattern[switch_n]
        if active_swtiches // 2 != p[i]:
            break
        if i == M - 1:
            cnt += 1
print(cnt)

Submission status: Runtime Error

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

l = max(max(ks))

lis_swi = s = [[] for i in range(l)]

for m in range(M):
    for s in ks[m][1:]:
        lis_swi[s-1].append(m)


ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in lis_swi[j]:
                cnt_on[m] +=1

    f = True
    for m in range(M):
        if cnt_on[m]%2 != p[m]:
            f = False
            break
    
    if f:
        ans += 1


print(ans)