Problem:
 Score : 300 points    Problem Statement There are N people numbered 1 to N . Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.  Person i gives A_i testimonies. The j -th testimony by Person i is represented by two integers x_{ij} and y_{ij} . If y_{ij} = 1 , the testimony says Person x_{ij} is honest; if y_{ij} = 0 , it says Person x_{ij} is unkind.  How many honest persons can be among those N people at most?      Constraints  All values in input are integers.  1 \leq N \leq 15  0 \leq A_i \leq N - 1  1 \leq x_{ij} \leq N  x_{ij} \neq i  x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)  y_{ij} = 0, 1         Input Input is given from Standard Input in the following format:  N  A_1  x_{11}  y_{11}  x_{12}  y_{12}  :  x_{1A_1}  y_{1A_1}  A_2  x_{21}  y_{21}  x_{22}  y_{22}  :  x_{2A_2}  y_{2A_2}  :  A_N  x_{N1}  y_{N1}  x_{N2}  y_{N2}  :  x_{NA_N}  y_{NA_N}       Output Print the maximum possible number of honest persons among the N people.        Sample Input 1 3
1
2 1
1
1 1
1
2 0      Sample Output 1 2  If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.       Sample Input 2 3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0      Sample Output 2 0  Assuming that one or more of them are honest immediately leads to a contradiction.       Sample Input 3 2
1
2 0
1
1 0      Sample Output 3 1

Solution (Python):
import itertools

N = int(input())

xy_ls = []
for i in range(N):
    A = int(input())
    xy = [list(map(int,input().split())) for j in range(A)]
    xy_ls.append(xy)

ans_ls = list(itertools.product([0,1], repeat=N))

max_ans = 0
for ans in ans_ls:
    flg = True
    for i in range(len(ans)):
        if ans[i]==1:
            for xy in xy_ls[i]:
                if ans[xy[0]-1] == xy[1]:
                    pass
                else:
                    flg = False
                    break
    if flg == True:
        max_ans = max(max_ans,sum(ans))

print(max_ans)

Solution (Python):
N = int(input())
ListN=[0]
List = []
res =0
flag = True
mid =0
n =0
for i in range(N):
  k = int(input())
  n += k
  ListN.append(n)
  for j in range(k):
    List.append(list(map(int, input().split())))

for bits in range(2**N):
  mid=0
  flag= True
  for j in range(N):
    
    if((bits>>j) & 1): 
      mid+= 1
      
      for k in range(ListN[j],ListN[j+1]):
        mynum = bits
        
        if ((mynum>>List[k][0]-1)&1) != List[k][1]:
          flag = False
          break
  
  if flag:
    res = max(res,mid)
print(res)

Solution (Python):
from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if flag == False:
      break
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            
            if c[i][j]!=int(two[j]):
              flag =False
              break
          if flag ==False:
            break
        if flag == False:
          break
    
    else:
      break
  if flag == True:
    
    max_num = max(max_num,two.count("1"))  
print(max_num)

Solution (Python):
N = int(input())
A = []
for i in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for _ in range(a)]
    A.append([a, xy])






ans = 0
for i in range(2**N):
    for j in range(N):
        flag = 0
        if (i >> j) & 1:
            for k in range(A[j][0]):
                l = A[j][1][k][0]
                m=A[j][1][k][1]
                
                if not (i >> (l-1)) & 1 == A[j][1][k][1]:
                    flag = 1
                    break
            if flag == 1:
                break
    else:
        
        ct = 0
        for l in range(N):
            ct += ((i >> l) & 1)
        ans = max(ans, ct)
print(ans)

Solution (Python):
N = int(input())
query = []
ans = 0

for i in range(N):
    A = int(input())
    query.append([list(map(int, input().split())) for j in range(A)])

for i in range(1<<N):
    count = 0
    FLG = True
    for j in range(N):
        if (i >> j) & 1:
            count += 1
            for x, y in query[j]:
                if (i >> (x - 1)) & 1 != y:
                    FLG = False
                    break   
        if not FLG:
            break
    else:
        ans = max(ans, count)

print(ans)

Solution (Python):
from itertools import product

n = int(input())
l1 = []
for _ in range(n):
    l2 = []
    for _ in range(int(input())):
        l2.append(list(map(int, input().split())))
    l1.append(l2)

ans = 0
for k in product([1, 0], repeat=n):
    check = True
    for i, j in enumerate(l1):
        if k[i] == 0:
            continue
        for x in j:
            if k[x[0] - 1] != x[1]:
                check = False
    if check:
        ans = max(ans, sum(k))
print(ans)

Solution (Python):
from itertools import product

n = int(input())
l1 = []
for _ in range(n):
    l2 = []
    for _ in range(int(input())):
        l2.append(list(map(int, input().split())))
    l1.append(l2)

ans = 0
for k in product([1, 0], repeat=n):
    ng_check = False
    for i, j in enumerate(l1):
        if k[i] == 0:  
            continue
        for x in j:  
            if k[x[0] - 1] != x[1]:
                ng_check = True  
                break
        if ng_check:  
            break
    else:
        ans = max(ans, sum(k))
print(ans)

Solution (Python):
n = int(input())

memo = {}
for i in range(n):
    man_idx = i
    count = int(input())
    comment = [ list(map(int,input().split())) for _ in range(count) ]
    memo[man_idx] = comment

ans = 0
for i in range(2**n):
    sub_ans = 0
    is_true = True
    for j in range(n):
        if i >> j & 1:
            sub_ans += 1
            for x, y in memo[j]:
                if (i >> (x-1) & 1)  !=  int(y):
                    is_true = False
                    break
    if is_true:
        ans = max(sub_ans, ans)
print(ans)

Solution (Python):
from itertools import *
N = int(input())
H = []
A = []

for i in range(N):
  for j in range(int(input())):
    x,y = map(int, input().split())
    H+=[[i,x-1,y]]

for P in product([0,1],repeat=N):
  for h in H:
    if P[h[0]]==1 and P[h[1]]!=h[2]:
      break
  else:
    A+=[sum(P)]

print(max(A))

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

n = int(input())


honest_thought = [[] for _ in range(n+1)] 
unkind_thought = [[] for _ in range(n+1)] 

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = list(map(int, input().split()))
        if y == 0:
            unkind_thought[i].append(x)
        else:
            honest_thought[i].append(x)


ans = 0

for i in range(2 ** n):
    
    flag = True

    
    honest = [False] * (n+1)
    unkind = [False] * (n+1)

    q = deque()
    for j in range(n):  
        if ((i >> j) & 1):  
            honest[j+1] = True
            q.append(j)

    while len(q) > 0 and flag:
        v = q.popleft()
        for x in unkind_thought[v]:
            if honest[x]:
                flag = False
                break
            elif not unkind[x]:
                unkind[x] = True
        for x in honest_thought[v]:
            if unkind[x]:
                flag = False
                break
            elif not honest[x]:
                flag = False
                break

    if flag:
        ans = max(ans, honest.count(True))


print(ans)

Solution (Python):
import itertools
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ans=0
    n=INT()
    A=[]
    for i in range(n):
        a=INT()
        A.append([])
        for k in range(a):
            x,y=INTM()
            x-=1
            A[i].append([x,y])

    

    for i in itertools.product([0,1], repeat=n):
        
        flg=True
        for k in range(n):
            if i[k]==1:
                for j in A[k]:
                    if i[j[0]]!=j[1]:
                        flg=False
                        break
        
        if flg:
            ans=max(ans,sum(i))

    print(ans)


if __name__=='__main__':
    do()

Solution (Python):
N = int(input())
A = []
for i in range(N):
    a  = int(input())
    Alst = []
    for j in range(a):
        x,y = map(int,input().split())
        Alst.append([x-1,y])
    A.append(Alst)

honest = 0
  
for i in range(2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1:
            for x,y in A[j]:
                if (i>>x)&1 != y: 
                    flag = 1
                    break
    if flag == 0:  
        honest = max(honest, bin(i)[2:].count('1'))  
print(honest)

Solution (Python):
n=int(input())
s=[]
ans=0
for i in range(n):
    a=int(input())
    s.append([list(map(int,input().split())) for _ in range(a)])
for i in range(2**n):
    bit=bin(i)[2:].zfill(n)
    flag=1
    for j in range(n):
        if bit[j]=='0':
            continue
        for sh in s[j]:
            if int(bit[sh[0]-1])!=sh[1]:
                flag=0
    if flag:
        ans=max(ans,bit.count('1'))
print(ans)

Solution (Python):
import itertools
N=int(input())
A=[]
Z=[]
for _ in range(N):
    a_i=int(input())
    z_i=[]
    A.append(a_i)
    for i in range(a_i):
        a,b=map(int,input().split())
        z_i.append([a-1,b])
    Z.append(z_i)
ans=0
for bit in itertools.product([0,1],repeat=N):
    f=True
    for j in range(N):
        if bit[j]==1:
            for k in range(A[j]):
                if bit[Z[j][k][0]]!=Z[j][k][1]:
                    f=False
                    break
    if f:
        ans=max(ans,bit.count(1))
print(ans)

Solution (Python):
N = int(input())
Assertions = []
ansnum = 0

for i in range(N):
    b = []
    n = int(input())
    for j in range(n):
        xi,yi = map(int,input().split())
        b.append([xi-1,yi])
    Assertions.append(b)

for i in range(2**N):
    select = []
    
    ans = [0 for _ in range(N)]
    index = []
    flag = True
    
    for j in range(N):
        if ((i >> j) & 1):
            select.append(Assertions[j])
            
            index.append(j)
            
            ans[j] = 1
            
    
    for idx in index:
        for Assert in Assertions[idx]:
            if ans[Assert[0]] != Assert[1]:
                flag = False
                break
    
    if flag:
        ansnum = max(ansnum,len(index))

print(ansnum)

Solution (Python):
n=int(input())
ans=[]
tes=[[] for _ in range(n)]

for j in range(n):
    a=int(input())
    for h in range(a):
        x,y=map(int,input().split())
        tes[j].append(x)
        tes[j].append(y)

for i in range(2**n):
    f=0
    m=0
    rel=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            rel[j]=1
            m+=1
            
    
    for j in range(n):
        
        for q in range(len(tes[j])//2):
            if rel[j]==1 and tes[j][2*q+1]!=rel[tes[j][2*q]-1]:
                f=1
    if f==0:
        ans.append(m)
print(max(ans))

Solution (Python):
n=int(input())
ans=[]
tes=[[] for _ in range(n)]

for j in range(n):
    a=int(input())
    for h in range(a):
        x,y=map(int,input().split())
        tes[j].append(x)
        tes[j].append(y)

for i in range(2**n):
    f=0
    m=0
    rel=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            rel[j]=1
            m+=1
            
    
    for j in range(n):
        
        for q in range(len(tes[j])//2):
            if rel[j]==1 and tes[j][2*q+1]!=rel[tes[j][2*q]-1]:
                f=1
    if f==0:
        ans.append(m)
print(max(ans))

Solution (Python):
from itertools import product
N = int(input())
A = []
XY = []
for i in range(N):    
    a = int(input())
    A.append(a)
    xy = [list(map(int,input().split())) for _ in range(a)]
    XY.append(xy)
flag = 0
ans = 0
for i in product((0,1), repeat=N):
    for idx, j in enumerate(i):
        if j:
            for x, y in XY[idx]:
                if i[x-1] != y:
                    flag = 1
                if flag:
                    break
        if flag:
            break
    if flag == 0:
        ans = max(ans, sum(i))
    if flag:
        flag = 0
print(ans)

Solution (Python):

n = int(input())
L = [[]*n for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        x-=1
        L[i].append((x,y))

ans = 0
for i in range(1<<n):
    bit = [(i>>j)&1 for j in range(n)]
    
    flag = True
    for j in range(n):
        if bit[j]:
            for x,y in L[j]:
                if bit[x] != y:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        ans = max(ans,sum(bit))
print(ans)

Solution (Python):

n = int(input())
L = [[]*n for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        x-=1
        L[i].append((x,y))

ans = 0
for i in range(1<<n):
    bit = [(i>>j)&1 for j in range(n)]
    
    flag = True
    for j in range(n):
        if bit[j]:
            for x,y in L[j]:
                if bit[x] != y:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        ans = max(ans,sum(bit))
print(ans)

Solution (Python):

N = int(input())
X = []
Y = []
for _ in range(N):
    a = int(input())
    tmp = []
    for _ in range(a):
        tmp.append(list(map(int, input().split())))

    X.append(a)
    Y.append(tmp)

ans = 0
for bit in range(2 ** N):
    flag = True
    for i in range(N):
        if bit >> i & 1:
            for x, y in Y[i]:
                flag &= (bit >> (x - 1) & 1) == y

    if flag:
        ans = max(ans, bin(bit).count("1"))

print(ans)

Solution (Python):
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    xy.append([list(map(int, input().split())) for i in range(a[-1])])
ans = 0
for i in range(2**n):
    x = [1] * n
    for j in range(n):
        if (i>>j)&1:
            x[j] = 0
    flag = False
    for j in range(n):
        for k in range(a[j]):
            if x[j] == 1:
                if x[xy[j][k][0]-1] != xy[j][k][1]:
                    flag = True
                    break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, x.count(1))
print(ans)

Solution (Python):
from itertools import product

N=int(input())
datas=[]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        datas.append((i,x-1,y)) 



ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in datas:
        if i[j[0]]==1 and i[j[1]]!=j[2]:
            ok=False
            break
    if ok:
        ans=max(ans,sum(i))
print(ans)

Solution (Python):
from itertools import product

N=int(input())
datas=[]
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        datas.append((i,x-1,y))



ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in datas:
        if (i[j[0]]==1 and i[j[1]]!=j[2]):
            ok=False
            break
    if ok:
        ans=sum(i)
print(ans)

Solution (Python):
N = int(input())

l = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
    
    a = int(input())
    
    for _ in range(a):
        x, y = map(int, input().split())
        l[i][x - 1] = y

ans = 0



for i in range(2**N):
    
    d = [0 for _ in range(N)]
    
    for j in range(N):
        if i >> j & 1:
            d[j] = 1
    """
    ex. N=3の時、
    i = 0,1,2,3,4,5,6,7 この時、dはそれぞれ 
    [0, 0, 0],[1, 0, 0],[0, 1, 0],[1, 1, 0],
    [0, 0, 1],[1, 0, 1],[0, 1, 1],[1, 1, 1]
    """

    flag = True

    
    for j in range(N):
        
        for k in range(N):
            
            if d[j] == 1:
                
                if l[j][k] == -1:
                    continue
                
                if l[j][k] != d[k]:
                    flag = False
                    break

    
    
    if flag == True:
        ans = max(ans, sum(d))

print(ans)

Solution (Python):
from itertools import product
datas=[]
num=0

N=int(input())
for i in range(N):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        datas.append((num,x-1,y))
    num+=1


ans=0
for i in product([0,1],repeat=N):
    ok=True
    cnt=0
    for j in datas:
        if (i[j[0]]==1 and i[j[1]]!=j[-1]):
            ok=False
            break
    if ok:
        cnt=sum(i)
        ans=max(ans,cnt)
    
print(ans)

Solution (Python):
N = int(input())

numbers_of_testimonies =[]
contents_of_testimonies =[]

for n in range(N):
  testimony = []
  x = int(input())
  numbers_of_testimonies.append(x)
  for _ in range(x):
    testimony.append(list(map(int,input().split())))
  contents_of_testimonies.append(testimony)

numbers_of_testimonies.insert(0,"x")
contents_of_testimonies.insert(0,"x")
ans = 0

for i in range(2**N):
  hypothesis = [0 for _ in range(N)]
  
  for j in range(N):
    if (i>>j) & 1:
      hypothesis[j] = 1
  hypothesis.insert(0,9)
  flag = True
  

  for k in range(1,N+1):
    if hypothesis[k] == 1:

      for l in range(numbers_of_testimonies[k]):
        if contents_of_testimonies[k][l][1] != hypothesis[contents_of_testimonies[k][l][0]]:
          flag = False

  if flag == True:
    ans = max(ans,hypothesis.count(1))
print(ans)

Solution (Python):
from itertools import product

N=int(input())
data=[]
for i in range(N):
    for j in range(int(input())):
        x,y=map(int,input().split())
        data.append((i,x-1,y)) 


ans=0
for i in product([0,1],repeat=N):
    ok=True
    for j in data:
        if i[j[0]]==1 and i[j[1]]!=j[2]:
            ok = False
            break
    if ok:
        ans=max(ans,sum(i))
print(ans)

Solution (Python):
n=int(input())
l=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y = map(int,input().split())
    l[i][x-1]=y

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

  flag=1

  for j in range(n):
    for s in range(n):
      if d[j]==1:
        if l[j][s]==-1:
          continue
        
        if l[j][s]!=d[s]:
          flag=0
          break
          
  if flag:
    ans=max(ans,sum(d))

print(ans)

Solution (Python):
def main():
    import sys

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

    n = int(input())

    tf = [[] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            tf[i].append((x-1, y))

    ans = 0
    for i in range(1 << n):
        tmp = format(i, 'b').count('1')
        for j in range(n):
            if (i>>j)&1:
                for x, y in tf[j]:
                    if (i>>x)&1 != y:
                        break
                else:
                    continue
                break
        else:
            ans = max(ans, tmp)
    print(ans)


            



if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import itertools
n = int(input())
ixy = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int, input().split())
        ixy.append([i,x-1,y])

ans = 0
ixy = np.array(ixy)
p = itertools.product([True,False], repeat=n)
for p_i in p:
    f = True
    for i,x,y in ixy:
        if not p_i[i]:
            continue
        else:
            if p_i[x] != y:
                f = False
                break
    if f:
        ans = max(sum(p_i), ans)
print(ans)

Solution (Python):
(n,),*axy = [list(map(int, s.split())) for s in open(0)]

from itertools import product
from collections import defaultdict
d = defaultdict(defaultdict)

i = 0
for elm in axy:
    if len(elm) == 1:
        i += 1
    else:
        x,y = elm
        d[i][x] = y
del i

ans = 0
for flgs in product([0,1], repeat=n):
    honest = [i for i, v in zip(range(1, n+1), flgs) if v]
    valid = True
    for i in honest:
        if not valid:
            break
        if not i in d:
            continue
        for j in d[i]:
            if (j in honest and not d[i][j]) or (j not in honest and d[i][j]):
                valid = False
                break
    if valid:
        ans = max(ans, len(honest))

print(ans)

Solution (Python):
n = int(input())
m = []
a = [[] for i in range(n)]
for i in range(n):
    tmp = int(input())
    m.append(tmp)
    for j in range(tmp):
        a[i].append(list(map(int,input().split())))

ans = 0

for i in range(2**n):
    cnt = 0
    for j in range(n):
        flg = True
        if i >> j & 1:
            cnt += 1
            for k in range(m[j]):
                kj = (i >> (a[j][k][0]-1)) & 1
                if a[j][k][1] != kj:
                    flg = False
                    break
            if not flg:
                break
    if flg:
        ans = max(ans, cnt)

print(ans)

Solution (Python):
def max2(x,y):
    return x if x > y else y

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for n in range(1 << N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if (n>>i)&1 == 1:
                if (n>>x)&1 != y:
                    flg = True
                    break
        if flg:
            break
        if i == N-1:
            res = max2(res, popcnt(n))
print(res)

Solution (Python):
def max2(x,y):
    return x if x > y else y

def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for n in range(1 << N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if (n>>i)&1 == 1:
                if (n>>x)&1 != y:
                    flg = True
                    break
        if flg:
            break
        if i == N-1:
            res = max2(res, popcnt(n))
print(res)

Solution (Python):
from itertools import product

N = int(input())
testimony_by = []   
for i in range(N):
    a = int(input())
    li = []   
    for j in range(a):
        li.append(list(map(int, input().split())))
    testimony_by.append(li)
ans = 0
for bit_li in product([0, 1], repeat=N):
    is_ok = True    
    for i in range(N):
        if bit_li[i] == 1:
            for li in testimony_by[i]:
                x, y = li
                x -= 1
                if bit_li[x] != y:
                    is_ok = False
                    break

        if not is_ok:
            break
    if is_ok:
        ans = max(ans, sum(bit_li))
print(ans)

Solution (Python):
from itertools import product

def max2(x,y):
    return x if x > y else y

N = int(input())
data = [[] for _ in range(N)]
res = 0
for i in range(N):
    for _ in range(int(input())):
        data[i].append(tuple(map(int, input().split())))
for a in product((0,1), repeat=N):
    flg = False
    for i in range(N):
        for x, y in data[i]:
            x -= 1
            if a[i] == 1:
                if a[x] != y:
                    flg = True
                    break
        if flg:
            break
        if i == N-1:
            res = max2(res, sum(a))
print(res)

Solution (Python):
n=int(input())
said=[]
for i in range(n):
    a=int(input())
    said.append([list(map(int,input().split())) for _ in range(a)])
ans=0
for i in range(2**n):
    l=[0]*n
    for j in range(n):
        if (i>>j&1):
            l[j]=1
    flag=True
    for k in range(n):
        if l[k]==1 and (not all(said[k][x][1]==l[said[k][x][0]-1] for x in range(len(said[k])))):
            flag=False
            break
    if flag==True and l.count(1)>ans:
        ans=l.count(1)
print(ans)

Solution (Python):
n = int(input())
XY = [[] for _ in range(n)]
ans = 0

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        XY[i].append((x-1, y))

for i in range(2**n):
    correct = [False]*n
    tmp_cnt = 0
    flag = True

    for j in range(n):
        if i&(1<<j):
            correct[j] = True
            tmp_cnt += 1

    for j in range(n):
        if correct[j]:
            for x, y in XY[j]:
                if (y==0 and correct[x]) or (y==1 and not correct[x]):
                    flag = False
    if flag:
        ans = max(tmp_cnt, ans)

print(ans)

Solution (Python):
n = int(input())
g = [[-1 for _ in range(15)] for _ in range(15)]
for i in range(n) :
    m = int(input())
    for j in range(m) :
        x,y = map(int, input().split())
        
        g[i][x-1] = y

ans = 0
for i in range(1<<n) :
    honests = [0] * n
    for j in range(n) :
        if (i>>j) & 1 :
            honests[j] = 1
    ok = True
    for j in range(n) :
        if honests[j] : 
            for k in range(n) :
                if g[j][k] == -1 :
                    continue
                if g[j][k] != honests[k] :
                    ok = False
    if ok :
        ans = max(ans, honests.count(1))

print(ans)

Solution (Python):
n = int(input())
a = []
xy = [list() for _ in range(n)]

for i in range(n):
    a += [int(input())]
    for j in range(a[i]):
        xy[i] += [list(map(int,input().split()))]


honestnum = []

for i in range(2**n):
    flag = True
    
    
    for j in range(n):
        if (i>>j)&1 == 1:
            
            for k in range(a[j]):
                if xy[j][k][1] != (i>>(xy[j][k][0]-1)&1):
                    flag = False
                    break
        
    if flag:
        
        honestnum += [bin(i).count("1")]
print(max(honestnum))

Solution (Python):
n = int(input())
a = []

for i in range(n):
    syougen_num = int(input())
    ai = []
    for j in range(syougen_num):
        xi_yi = list(map(int, input().split()))
        ai.append(xi_yi)
    a.append(ai)

res = 0
for i_bin in range(1 << n):
    syougen_list = [[0, 0] for i in range(n)]
    one_counter = 0
    for keta in range(n):
        
        if i_bin >> keta & 1 == 1:
            one_counter += 1
            for i_syougen in a[keta]:
                
                xi, yi = i_syougen
                syougen_list[xi - 1][yi] += 1
    for i_syougen in range(n):
        if syougen_list[i_syougen][0] >= 1 and syougen_list[i_syougen][1] >= 1:
            break
        elif syougen_list[i_syougen][0] >= 1 and i_bin >> i_syougen & 1 == 1:
            break
        elif syougen_list[i_syougen][1] >= 1 and i_bin >> i_syougen & 1 == 0:
            break
    else:
        res = max(res, one_counter)
        flag = i_bin
    
print(res)

Solution (Python):
n = int(input())
a = []

for i in range(n):
    syougen_num = int(input())
    ai = []
    for j in range(syougen_num):
        xi_yi = list(map(int, input().split()))
        ai.append(xi_yi)
    a.append(ai)

res = 0
for i_bin in range(1 << n):
    syougen_list = [[0, 0] for i in range(n)]
    one_counter = 0
    for keta in range(n):
        
        if i_bin >> keta & 1 == 1:
            one_counter += 1
            for i_syougen in a[keta]:
                
                xi, yi = i_syougen
                syougen_list[xi - 1][yi] += 1
    for i_syougen in range(n):
        if syougen_list[i_syougen][0] >= 1 and syougen_list[i_syougen][1] >= 1:
            break
        elif syougen_list[i_syougen][0] >= 1 and i_bin >> i_syougen & 1 == 1:
            break
        elif syougen_list[i_syougen][1] >= 1 and i_bin >> i_syougen & 1 == 0:
            break
    else:
        res = max(res, one_counter)
        flag = i_bin
    
print(res)

Solution (Python):
N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for _ in range(A):
    x, y = map(int, input().split())
    evidences[i].append((x - 1, y))

ans = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        
            
    if consistent:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Solution (Python):
n = int(input())
a = []
for _ in range(n):
    a.append([list(map(int,input().split())) for __ in range(int(input()))])
l = []
for i in range(2**n):
    flag2 = 0
    for j in range(n):
        if i >> j & 1 == 1:
            flag1 = 0
            for k in a[j]:
                if i >> (k[0]-1) & 1 != k[1]:
                    flag1 = 1
                    flag2 += 1
                    break
            if flag1 : break
        
    if flag2 == 0 :l.append(list(bin(i)).count('1'))
print(max(l))

Solution (Python):
import itertools

n = int(input())
lst = []
for _ in range(n):
  m = int(input())
  lst_s = []
  for _ in range(m):
    evi = list(map(int, input().split()))
    lst_s.append(evi)
  lst.append(lst_s)


truth = [0, 1]
all_lists = list(itertools.product(truth, repeat=n))

max_count = 0
for each in all_lists:
  flag = True
  count = 0
  
  for i in range(n):
    trust = each[i]
    
    evis = lst[i]
    for evid in evis:
      
      person_ind = evid[0] - 1
      person_trust = evid[1]
      if trust == 1:
        if person_trust != each[person_ind]:
          flag = False
          break
    if not flag:
      break
    if trust == 1:
      count += 1
  if (count > max_count) and flag:
    max_count = count
print(max_count)

Solution (Python):
import itertools 
n = int(input())
a = []
shogen =[]
for i in range(n):
    a.append(int(input()))
    temp = []
    for j in range(a[i]):
        x,y = map(int,input().split())
        temp.append([x,y])
        
    shogen.append(temp)

pattern = list(itertools.product([0,1], repeat = n))
result = 0



for i in range(len(pattern)):
    flg = True
    check = [-1 for _ in range(n)]
    
    for j in range(n):
        
        if pattern[i][j] == 1:
            
            for k in range(a[j]):
                
                if check[shogen[j][k][0]-1] == -1:
                    check[shogen[j][k][0]-1] = shogen[j][k][1]
                else:
                    if check[shogen[j][k][0]-1] != shogen[j][k][1]:
                        flg = False
                        
                        break


    for l in range(n):
        if (pattern[i][l] == 1 and check[l] == 0) or (pattern[i][l] == 0 and check[l] == 1):
            flg = False
            break

    if flg:
        
        result = max(result, sum(pattern[i]))

print(result)