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):
from itertools import product

N = int(input())

li = [[] for i in range(N)]
A = [0]*N
for i in range(N):
    a = int(input())
    A[i]=a
    li[i]=[list(map(int,input().split())) for i in range(a)]

counter = 0
for humen in product([0,1],repeat=N):
    flag = True
    for i in range(N):
        if humen[i]==1:
            for s in range(A[i]):
                if not li[i][s][1]==humen[li[i][s][0]-1]:
                    flag=False
                    break
        
                
    if flag :
        counter = max(counter,humen.count(1))


print(counter)

Solution (Python):
n = int(input())
a = [0 for _ in range(n)]
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        s,t = map(int,input().split())
        x[i].append(s)
        y[i].append(t)
ans = 0
for i in range(2**n):
    karishoujiki = []
    shoujiki = []
    usotuki = []
    for j in range(n):
        if (i>>j)&1:
            karishoujiki.append(j)
            for k in range(a[j]):
                if y[j][k] == 1:
                    shoujiki.append(x[j][k]-1)
                else:
                    usotuki.append(x[j][k]-1)
    flag = 1
    shoujikiflag = [0 for _ in range(n)]
    karishoujikiflag = [0 for _ in range(n)]
    usotukiflag = [0 for _ in range(n)]
    for i in range(len(shoujiki)):
        shoujikiflag[shoujiki[i]] = 1
    for i in range(len(karishoujiki)):
        karishoujikiflag[karishoujiki[i]] = 1
    for i in range(len(usotuki)):
        usotukiflag[usotuki[i]] = 1
    
    for i in range(n):
        if shoujikiflag[i] and not karishoujikiflag[i]:
            flag = 0
        if usotukiflag[i] and karishoujikiflag[i]:
            flag = 0
    
    if flag:
        ans = max(ans,len(karishoujiki))

print(ans)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        a = Scanner.int()
        for _ in range(a):
            x, y = Scanner.map_int()
            x -= 1
            A[i][x] = y
    ans = 0
    for i in range(1 << N):
        truth = [False for _ in range(N)]
        for j in range(N):
            if i >> j & 1:
                truth[j] = True
        isOK = True
        for j in range(N):
            if not truth[j]:
                continue
            for k in range(N):
                if j == k:
                    continue
                if A[j][k] == 0 and truth[k]:
                    isOK = False
                if A[j][k] == 1 and not truth[k]:
                    isOK = False
        if isOK:
            ans = max(sum(truth), ans)
    print(ans)


def main():
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
T = []
try:
	while True:
		t = input()
		t=int(t)
		T_temp=[]
		for t_ in range(t) :
			temp = list(map(int,input().split()))
			T_temp.append(temp)
		T.append(T_temp)
except EOFError:
	pass
    
def check_Contradiction(true_list):
    S = {}
    for n in range(N):
        if n in true_list:
            S[n]=set([1])
        else:
            S[n]=set([0])

    for t in true_list:
        for T_ in T[t]:
            S[T_[0]-1].add(T_[1])
    ok=True
    for s in S.keys():
        if len(S[s])!=1:
            ok='False'
            break

    return ok

ok_max = -1
for i in range(2**N):

    true_list=[]
    for j in range(N):
        if i>>j&1 ==True:
            true_list.append(j)


            
    if check_Contradiction(true_list)==True:
        if ok_max < len(true_list):
            ok_max=len(true_list)
            
print(ok_max)

Solution (Python):








def solve(N, XYs):
    ans = 0
    for i in range(2 ** N):
        for j in range(N):
            if (i >> j) & 1:
                for x, y in XYs[j + 1]:
                    if ((i >> (x - 1)) & 1) ^ y:
                        break
                else:
                    continue
                break
        else:
            ans = max(ans, bin(i).count('1'))
    print(ans)


if __name__ == '__main__':
    N = int(input())
    XYs = [[] for _ in range(N + 1)]
    for i in range(N):
        Ai = int(input())
        for _ in range(Ai):
            XYs[i + 1].append([int(i) for i in input().split()])
    
    
    
    
    
    
    
    
    
    
    solve(N, XYs)

Solution (Python):
from itertools import product

n = int(input())
al = []

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


pattern = 2
ite = product(range(pattern),repeat=n)
ans = 0
for it in ite:
    a_01_l = list(it)
    curr_ans = a_01_l.count(1)
    
    
    for i, curr_it in enumerate(it):
        if curr_it == 1:
            check = True
            for a in al[i]:
                if a_01_l[a[0]-1] != a[1]:
                    check = False
            if not check:
                break
    else:
        
        ans = max(curr_ans,ans)

print(ans)

Solution (Python):
n=int(input())
state=[[] for _ in range(n)]
for _ in range(n):
    a=int(input())
    for i in range(a):
        x,y=map(int,input().split())
        state[_].append([x,y])
ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for k,s in enumerate(temp):
        if s==0: continue
        for st in state[k]:
            if temp[st[0]-1]!=st[1]:
                flag=0
                break
            if not flag: break
    if flag:
        cnt=temp.count(1)
        if cnt>ans: ans=cnt
print(ans)

Solution (Python):
import sys

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

N = I()
A = []
xy = [[] for i in range(N)]
for i in range(N):
    A.append(I())
    for j in range(A[i]):
        x,y = LI()
        xy[i].append([x-1,y])




ans = 0
for i in range(2**N):
    B = [[] for _ in range(N)]
    a = 0  
    for j in range(N):
        if (i>>j) & 1:  
            B[j].append(1)
            a += 1
            for k in range(A[j]):
                B[xy[j][k][0]].append(xy[j][k][1])
        else:  
            B[j].append(0)
    if sum(len(set(B[j])) for j in range(N)) != N:  
        continue
    else:
        ans = max(ans,a)

print(ans)

Solution (Python):
N = int(input())
evidence = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for _ in range(A):
    x,y = map(int,input().split())
    evidence[i].append((x-1,y))
result = 0
for j in range(1,2**N):
  consistent = True
  for k in range(N):
    if (j >> k) & 1 == 0:
      continue
    for x,y in evidence[k]:
      if (j >> x) & 1 != y:
        consistent = False
        break
    if not consistent:
      break
  if consistent:
    result = max(result, bin(j)[2:].count("1"))
print(result)

Solution (Python):
import itertools
n = int(input())
a_li = []
x_li = []
y_li = []
for i in range(n):
  a = int(input())
  a_li.append(a)
  tmp_x = []
  tmp_y = []
  for j in range(a):
    x, y = list(map(int, input().split()))
    x -= 1
    tmp_x.append(x)
    tmp_y.append(y)
  x_li.append(tmp_x)
  y_li.append(tmp_y)
total_li = list(itertools.product([0, 1], repeat=n))
ans = 0
for each in total_li:
  flag = True
  for i, person in enumerate(each):
    if person == 1:
      per_li = x_li[i]
      hone_li = y_li[i]
      for pe, ho in zip(per_li, hone_li):
        if each[pe] != ho:
          flag = False

  if flag:
    ans = max(ans, sum(each))
print(ans)

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

def main():
    
    def check(bit):
        for i in range(n):
            if not bit & (1 << i):
                continue

            for human, is_honest in a[i]:
                if is_honest == 1 and (bit & (1 << human)):
                    continue
                elif is_honest == 0 and not (bit & (1 << human)):
                    continue
                else:
                    return False
        return True

    n = int(input())
    ans = 0
    a = [[] for _ in range(n)]
    for i in range(n):
        m = int(input())
        for j in range(m):
            xy = list(map(int, input().split()))
            xy[0] -= 1
            a[i].append(xy)

    
    for bit in range((1 << n)):
        num = 0
        if check(bit):
            for k in range(n):
                if bit & (1 << k):
                    num += 1
            ans = max(ans, num)
    print(ans)

if __name__ == '__main__':
    main()

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

result = 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 evidence[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count("1"))
print(result)

Solution (Python):
n=int(input())
p = []
for _ in range(n):
  p1 = []
  a = int(input())
  for __ in range(a):
    x,y = map(int,input().split())
    x-=1
    p1.append((x,y))
  p.append(p1)

ans = 0
for i in range(2**n):
  ok = True
  for j in range(n):
    if (i>>j) & 1 == 0:continue
    for x,y in p[j]:
      if (i>>x)&1 != y:
        ok = False
        break
    if ok == False:
      break
  if ok:
    
    cnt = len([j for j in range(n) if (i>>j)&1])
    ans = max(ans,cnt)
print(ans)

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

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


X = list(range(1, N+1))

n = N
ans = 0
for bit in range(2**n):
    Pick = []
    for j in range(n):
        mask = 1 << j
        if bit & mask:
            Pick.append(X[j])


    flag = True
    for pick in Pick:
        for xy in A[pick]:
            x = xy[0]
            y = xy[1]
            if y == 1 and x in Pick:
                flag *= True
            elif y == 0 and not(x in Pick):
                flag *= True
            else:
                flag *= False


    if flag == True:
        ans = max(ans, len(Pick))
print(ans)

Solution (Python):
n=int(input())
a=[]
for i in range(n):
  b=int(input())
  c=[[] for _ in range(n)]
  for j in range(b):
    x,y=map(int,input().split())
    c[x-1]=y
  a.append(c)
ans=[]
for i in range(2**n):
  tr=bin(i)[2:].zfill(n)
  cnt=0
  for j in range(n):
    if tr[j]=='1':
      for k in range(n):
        if a[j][k]!=[] and a[j][k]!=int(tr[k]):
          break
      else:
        cnt+=1
  if sum(list(map(int,tr)))==cnt:ans.append(cnt)
print(max(ans))

Solution (Python):
n = int(input())
a = [0] * n
x = [0] * n
y = [0] * n
for i in range(n):
    a[i] = int(input())
    t = [[int(j) for j in input().split()] for k in range(a[i])]
    x[i] = [j[0] for j in t]
    y[i] = [j[1] for j in t]

mx = 0
for bit in range(1<<n):
    flag = True
    tf = [0] * n
    for i in range(n):
        if bit & (1 << i): 
            tf[i] = 1
    for i in range(n):
        if tf[i] == 0:
            continue
        for j in range(a[i]):
            if tf[x[i][j]-1] != y[i][j]:
                flag = False
    if flag: mx = max(mx, bin(bit).count("1"))
print(mx)

Solution (Python):
def my_eval(ar,str):
    res = True
    n = len(str)
    
    
    for i in range(n):
        

        if(ar[str[i][0]] == 1):
            
            
            
            
            
            
            
            if(ar[str[i][1]] != str[i][2]):
                res = False
    
    
    return res

if __name__ == "__main__":

    
    n = int(input())
    str = []
    for i in range(n):
        a = int(input())

        for j in range(a):
            x = list(map(int,input().split()))
            x.insert(0,i+1)
            str.append(x)
    ar = [0] * (n+1)
    res = 0
    
    count = 0
    for i in range(2**n):
        count = 0
        for j  in range(n):
            if(i >> j & 1 == 1):
                ar[j+1] = 1
                count += 1
            else:
                ar[j+1] = 0
        
        if(my_eval(ar,str)):
            res = max(res,count)
    print(res)

Solution (Python):
def main():
    N = int(input())
    shougen = []
    for _ in range(N):
        A = int(input())
        shougen.append([list(map(int, input().split())) for _ in range(A)])
    
    ans = 0
    for i in range(2**N):
        state = [1]*N
        
        for j in range(N):
            if (i >> j) & 1:
                state[j] = 0
        
        flag = True
        for k in range(N):
            if not flag:
                break
            if state[k] == 1:
                for ele in shougen[k]:
                    if state[ele[0]-1] != ele[1]:
                        flag = False
                        break
                    
        if flag:
            ans = max(ans, sum(state))
    
    print(ans)
                
    
if __name__  == '__main__':
    main()

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

ans = 0
for ptn in range(1<<N):
    conflict = False
    for i in range(N):
        if (ptn>>i) & 1:
            for x, y in xyss[i]:
                if (ptn>>x) & 1 != y:
                    conflict = True
                    break
        if conflict:
            break
    else:
        num1 = bin(ptn).count('1')
        if num1 > ans:
            ans = num1

print(ans)

Solution (Python):
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        popcnt = bin(i).count('1')
        if popcnt <= c:
            continue
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        popcnt = bin(i).count('1')
        if popcnt <= c:
            continue
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            if popcnt > c:
                c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            popcnt = bin(i).count('1')
            if popcnt > c:
                c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=[]
ans=0
for i in range(a):
  s=ii()
  h=[list(mi()) for _ in range(s)]
  l.append(h)
for k in range(2**a):
  lst=[]
  for p in range(a):
    if k>>p & 1:
      lst.append(p)
  t=True
  for aa in lst:
    for m in l[aa]:
      if m[1]==0:
        if m[0]-1 in lst:
          t=False
          break
      else:
        if not m[0]-1 in lst:
          t=False
          break
  if t:
    ans=max(ans,len(lst))
print(ans)

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

N = int(readline())
A = [[] for _ in range(N)]

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


ans = 0
for i in range(2**N):
    pattern = [0] * N
    valid = True
    for j in range(N):
        if (i >> j) & 1:
            pattern[j] = 1

    
    for k in range(N):
        if pattern[k]:
            for x, y in A[k]:
                if pattern[x] != y:  
                    valid = False
                    break
    if valid:
        ans = max(ans, sum(pattern))

print(ans)

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

N = int(readline())
A = [[] for _ in range(N)]

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


ans = 0
for i in range(2**N):
    good = [0] * N
    f = 1
    for j in range(N):
        if (i >> j) & 1:
            good[j] = 1

    for k in range(N):
        if good[k]:
            for x, y in A[k]:
                if good[x] != y:
                    f = 0
    if f:
        ans = max(ans, sum(good))

print(ans)

Solution (Python):


from itertools import product
N = int(input())
A = {}
for i in range(N):
    A[i] = []

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

ret = -1
for p in product([0,1], repeat=N):
    cnt = 0
    flag = True
    for i in range(N):
        if p[i] == 1:
            for XY in A[i]:
                if XY[1] != p[XY[0]]:
                    flag = False
    if flag:
        ret = max(sum(p), ret)


print(ret)

Solution (Python):
from collections import deque


def solve():
    N = int(input())
    XY= [[]]
    for _ in range(N):
        A = int(input())
        xylist = []
        for __ in range(A):
            x, y = map(int, input().split())
            xylist.append([x,y])
        XY.append(xylist)
        ans = 0
    for bit in range(2 ** N):
        honestset = set()
        unhonestset = set()
        for i in range(N):
            if ((bit >> i) & 1) == 1:
                honestset.add(i+1)
            else:
                unhonestset.add(i+1)

        before = 100
        before_un = 100
        while (before != len(honestset) or before_un != len(unhonestset)):
            before = len(honestset)
            before_un = len(unhonestset)
            tmp = list(honestset)
            for x in tmp:
                for xin, yin in XY[x]:
                    if yin == 1:
                        honestset.add(xin)
                    else:
                        unhonestset.add(xin)
        if len(honestset & unhonestset) == 0:
            ans = len(honestset) if ans < len(honestset) else ans

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import product
N = int(input())
A = []
shougen = []
for i in range(N):
    a = int(input())
    A.append(a)
    ls = []
    for j in range(a):
        ls.append([int(k) for k in input().split()])
    shougen.append(ls)
truth = [0, 1]
ans = 0
for x in product(truth, repeat=N):
    num = 0
    for i, y in enumerate(x):
        if y == 1:
            for z in shougen[i]: 
                if x[z[0]-1] != z[1]:
                    num += 1
    if num == 0:
        ans = max(ans, sum(x))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

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

def countB(b):
    ret = 0
    while b > 0:
        if b % 2 == 1:
            ret += 1
        b //= 2

    return ret

ans = 0
for i in range(2 ** N):
    hs = [-1] * N
    contradiction = False
    for j in range(N):
        if i & 1 << j > 0:
            for k in range(N):
                if people[j][k] == -1:
                    continue
                if hs[k] == -1:
                    hs[k] = people[j][k]
                else:
                    if hs[k] != people[j][k]:
                        contradiction = True
    if not contradiction:
        for j in range(N):
            if hs[j] == -1:
                continue
            if i & 1 << j > 0 and hs[j]:
                continue
            if i & 1 << j == 0 and not hs[j]:
                continue
            else:
                break
        else:
            ans = max(ans, countB(i))
print(ans)

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

A = []
xy = []

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

ans = 0
p = [-1]*N

def dfs(i, p):
    global ans
    if i == N:
        ans = max(ans, sum(p))
    else:
        p_true = p.copy()
        if p_true[i] != 0:
            p_true[i] = 1
            ok = True
            for x, y in xy[i]:
                if y == p_true[x-1] or p_true[x-1] == -1:
                    p_true[x-1] = y
                else:
                    ok = False
            if ok:
                dfs(i+1, p_true)
        p_false = p.copy()
        if p_false[i] != 1:
            p_false[i] = 0
            dfs(i+1, p_false)

dfs(0, p)

print(ans)

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

ans = 0

def check(tf) :
    for i in range(N) :
        if tf[i] == 1 :
            for x,y in data[i] :
                if y != tf[x] :
                    return False
    return True

def combination(tf) :
    global ans
    if len(tf) == N :
        if check(tf) :
            count = sum(tf)
            if count > ans :
                ans = count
    else :
        combination(tf + [0])
        combination(tf + [1])

combination([])
print(ans)

for i in range(2**N) :
    a = list(format(i,"b").zfill(N))
    for j in range(N) :
        if a[j] == "0" :
            data[j]

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

XY = []
for _ in range(N):
    A = int(input())

    temp = []
    for _ in range(A):
        temp.append(list(map(int, input().split())))

    XY.append(temp)


max_honest = 0
for c in range(1 << N):
    check = [0] * N
    contradict = False

    cnt1 = 0
    while c != 0:
        if 1 & c:
            check[cnt1] = 1

        c >>= 1
        cnt1 += 1

    for i in range(N):
        if check[i] == 1:
            for x, y in XY[i]:
                if check[x - 1] != y:
                    contradict = True
                    break

            if contradict:
                break

    if not contradict:
        max_honest = max(max_honest, sum(check))


print(max_honest)

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

XY = []
for _ in range(N):
    A = int(input())

    temp = []
    for _ in range(A):
        temp.append(list(map(int, input().split())))

    XY.append(temp)


max_honest = 0
for c in range(1 << N):
    check = [0] * N
    contradict = False
    temp = c

    cnt2 = 0
    while temp != 0:
        if 1 & temp:
            check[cnt2] = 1

        temp >>= 1
        cnt2 += 1

    for i in range(N):
        if check[i] == 1:
            for x, y in XY[i]:
                if check[x - 1] != y:
                    contradict = True
                    break

            if contradict:
                break

    if not contradict:
        cnt1 = 0
        for i in range(N):
            if check[i] is not None and check[i] == 1:
                cnt1 += 1

        max_honest = max(max_honest, cnt1)


print(max_honest)

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


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

for i in range(2**N):
  flag=1
  honest=[]
  unkind=[]
  for j in range(N):
    if (i>>j)&1:
      honest.append(j)
    else:
      unkind.append(j)
      
  for k in honest:
    
    for l in Ins[k]:
      if l[1]==1 and l[0] in unkind:
        flag=0
        break
        
        
      elif l[1]==0 and l[0] in honest:
        flag=0
        break
        
        
  if flag==1:
    ans=max(ans,len(honest))
    
    
print(ans)

Solution (Python):
def readinput():
    n=int(input())
    shogensList=[]
    for i in range(n):
        a=int(input())
        shogens=[]
        for _ in range(a):
            shogen=list(map(int,input().split()))
            shogens.append(shogen)
        shogensList.append(shogens)
    return n, shogensList

def isMujun(shogensList, shojikiList):
    for shojiki in shojikiList:
        shogens=shogensList[shojiki]
        
        
        for x,y in shogens:
            if(y==1):
                if not (x-1 in shojikiList):
                    return True
            else:
                if x-1 in shojikiList:
                    return True
    return False

def main(n,shogensList):
    maxShojiki=0
    for x in range(2**n):
        shojikiList=[]
        b=1
        for i in range(n):
            if (x&b==b):
                shojikiList.append(i)
            b=b*2
        
        
        if not isMujun(shogensList, shojikiList):
            maxShojiki=max(maxShojiki, len(shojikiList))
    return maxShojiki

if __name__=='__main__':
    n,shogensList=readinput()
    ans=main(n,shogensList)
    print(ans)

Solution (Python):
n = int(input())
ans = 0
pr = [[] for i in range(n)]
for i in range(n):
    for j in range(int(input())):
        xy = list(map(int, input().split()))
        pr[i].append(xy)



for i in range(2 ** n):
    tflist = [0]*n  
    for j in range(n):
        if ((i >> j) & 1):
            tflist[j] = 1
    
    mujun = False
    for k in range(n):
        if (tflist[k] == 1):
            
            for m in pr[k]:
                
                
                if (tflist[m[0] - 1] != m[1]):
                    
                    mujun = True
                    break
    if (not (mujun)):
        ans = max(ans, tflist.count(1))
        

    

print(ans)

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

ans = 0
for i in range(1 << N):
    isPossible = True
    bit = [0] * N
    for k in range(N):
        if (i >> k) & 1:
            bit[k] = 1
    for idx, b in enumerate(bit):
        if b == 1:
            for x, y in T[idx]:
                isPossible &= (bit[x] == y)
    if isPossible:
        ans = max(ans, bit.count(1))
print(ans)