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 sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False


def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    tmp = []
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] == arr[i][j][1]:
            pass
        else:
            flag = False
            break

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    honest = [int(i) for i in bitstr]
    flag = True
    for j in range(n):
        if honest[j]:
            solv(j)
        if not flag:
            break
    debug(flag, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

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

S = []
for _ in range(N):
    A = int(input())
    S.append([tuple(map(int, input().split())) for _ in range(A)])

def sol(state):
    for i, A in enumerate(S):
        if (state & (1 << i)) == 0:
            continue
        for j, s in A:
            if ((state & (1 << (j - 1))) != 0) != (s != 0):
                return 0
    return sum(map(int, bin(state)[2:]))

ans = 0
for state in range(1 << N):
    ans = max(ans, sol(state))
print(ans)

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

result = [0]
for i in range(1, 2**n):
    h = format(i, "0"+str(n)+"b")
    c = [int(j) for j in list(h)]
    checker = True
    for j in range(n):
        if c[j]:
            for x, y in a[j]:
                if c[x-1]!=y:
                    checker = False
                    break
    if checker:
        result.append(c.count(1))
print(max(result))

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    G=[[] for _ in range(N)]
    for i in range(N):
        A=int(input())
        for _ in range(A):
            x,y=map(int, input().split())
            x=x-1
            G[i].append((x,y))

    ans=0
    for p in range(1<<N):
        s=[0]*N
        tmp=0
        for i in range(N):
            if p&(1<<i):
                s[i] = 1
                tmp+=1
        for i in range(N):
            if s[i]==0: continue
            for x,y in G[i]:
                if s[x]!=y: break
            else:
                continue
            break
        else:
            ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
X = [[] 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
        X[i].append((x, y))

ans = 0
for i in range(2**n):
    t = [-1]*n
    flag = True
    cnt = 0
    for j in range(n):
        if (i >> j) & 1:
            cnt += 1
            t[j] = 1
        else:
            t[j] = 0
    for j in range(n):
        if (i >> j) & 1:
            for x, y in X[j]:
                if t[x] != y:
                    flag = False
    if flag:
        ans = max(ans, cnt)

print(ans)

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

ans = 0
for b in range(1<<N):
    cnt = bin(b).count('1')
    if cnt <= ans: continue
    for i in range(N):
        if b&(1<<i):
            for x,y in xys[i]:
                if y==1 and b&(1<<x): continue
                if y==0 and b&(1<<x)==0: continue
                break
            else:
                continue
            break
    else:
        ans = cnt
print(ans)

Solution (Python):
n=int(input())
people=[None]*n
for i in range(n):
  a=int(input())
  people[i]=[tuple(map(int,input().split())) for k in range(a)]
ans=0
for i in range(2**n):
  shoujiki=[]
  div=i
  flg=0
  for j in range(n)[::-1]:
    s=div//(2**j)
    div%=2**j
    if s:shoujiki.append(j)
  for k in shoujiki:
    for lk in people[k]:
      if (lk[0]-1 in shoujiki and lk[1]==0) or (lk[0]-1 not in shoujiki and lk[1]==1):flg=1
  if not flg:
    if len(shoujiki)>ans:ans=len(shoujiki)
print(ans)

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

ans = 0
for i in range(2 ** N):
    S = format(i, 'b').zfill(N)
    flag = True
    for j in range(N):
        if S[j] == '1':
            for x, y in M[j]:
                if S[x - 1] != y:
                    flag = False
    if flag:
        ans = max(ans, S.count('1'))
print(ans)

Solution (Python):
import sys
def input() : return sys.stdin.readline().strip()

def main():
    ans = 0
    N = int(input())
    test = []
    for _ in range(N):
        A = int(input())
        temp = [tuple(map(int, input().split())) for _ in range(A)]
        test.append(temp) 
    
    
    print()
    for bit in range(1<<N):
        isOK = True
        for i in range(N):
            if bit & (1<<i):
                for j, flag in test[i]:
                    j -= 1
                    if flag ^ ((bit>>j) & 1):
                        isOK = False
                        break
        if isOK:
            ans = max(ans, bin(bit).count("1"))
    
    print(ans)

            
if __name__ == "__main__":
    main()

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

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

honest = 0


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

print(honest)

Solution (Python):
N = int(input())
honest = []
unkind = []

for _ in range(N):
    h_state = []
    u_state = []
    for __ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            h_state.append(x-1)
        else:
            u_state.append(x-1)
    honest.append(h_state)
    unkind.append(u_state)

ans = 0
    
for pattern in range(1 << N):
    for person in range(N):
        is_honest = pattern & 2**person > 0
        if not is_honest:
            continue
        doubt = False
        for tar in honest[person]:
            if not pattern & 2**tar > 0:
                doubt = True
        
        for tar in unkind[person]:
            if pattern & 2**tar > 0:
                doubt = True
        
        if doubt:
            break
        
    else:
        count = 0
        for person in range(N):
            if pattern & 2**person:
                count += 1
        ans = max(ans, count)

print(ans)

Solution (Python):

def inputlist(): return [int(k) for k in input().split()]

N = int(input())
A = [0]*N
says = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = inputlist()
        says[i+1][x] = y

suma = sum(A)

ans = 0

for i in range(2**N):
    bn = bin(i)
    bn = bn[2:]
    if len(bn) < N:
        for s in range(N-len(bn)):
            bn = '0' + bn
    flag = True
    for x in range(N):
        if bn[x] == '1':
            for y in range(N):
                if says[x+1][y+1] == -1:
                    continue
                if says[x+1][y+1] != int(bn[y]):
                    flag = False
                    break

    if flag:
        c = 0
        for i in range(N):
            if bn[i] == '1':
                c+=1
        ans = max(c,ans)

print(ans)

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

can_be = []
for i in itertools.product('01', repeat=n):
    people = tuple(map(int, i))
    contradiction = 0
    for j in range(n):
        if people[j] == 0:
            continue
        for k, x in statements[j]:
            if people[k] == x:
                continue
            contradiction = 1
            break
        if contradiction:
            break
    else:
        can_be.append(people)

ans = 0
for p in can_be:
    ans = max(ans, p.count(1))

print(ans)

Solution (Python):
N = int(input())
A, x, y = [], [], []
for i in range(N):
    A.append(int(input()))
    x_, y_ = [], []
    for j in range(A[i]):
        x__, y__ = map(int, input().split())
        x_.append(x__ - 1)
        y_.append(y__)
    x.append(x_)
    y.append(y_)
ans = 0
for i in range(2 ** N):
    t = 1
    for j in range(N):
        if not i & (1 << j):
            continue
        for a, b in zip(x[j], y[j]):
            if b == 1 and not i & (1 << a):
                t = 0
                break
            if b == 0 and i & (1 << a):
                t = 0
                break
        if not t:
            break
    if t:
        ans = max(ans, bin(i).count("1"))
print(ans)

Solution (Python):
from collections import defaultdict

n=int(input())
d=defaultdict(list)

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

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

res=0
for i in range(1<<n):
    bf=False
    for j in range(n):

        if (i>>j)&1 == 1:
            for x,y in d[j]:
                if (i>>x)&1 != y: 
                    bf=True
                    break
            if bf:break 

    if not bf:
        count=0
        for m in range(n):
            if (i & (1 << m)) : count+=1
            res=max(res,count)
        

print(res)

Solution (Python):
from collections import defaultdict

n=int(input())
d=defaultdict(list)

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

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

res=0
for i in range(1<<n):
    bf=False
    for j in range(n):

        if (i>>j)&1 == 1:
            for x,y in d[j]:
                if (i>>x)&1 != y: 
                    bf=True
                    break
            if bf:break 

    if not bf:
        
        
        
        
        res=max(res,bin(i).count("1"))

print(res)

Solution (Python):
from itertools import product as pro

n = int(input())
xy = []
for i in range(n):
    a_i = int(input())
    xy.append([tuple(map(int, input().split())) for _ in range(a_i)])

ans = 0
for l in pro([0, 1], repeat=n):
    for i, t in enumerate(l):
        if t == 1:
            if not all(l[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(l))

print(ans)

Solution (Python):
from itertools import product as pro

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

ans = 0
for l in pro([0, 1], repeat=n):
    for i, t in enumerate(l):
        if t == 1:
            if not all(l[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(l))

print(ans)

Solution (Python):
n = int(input())
state_ls_ls = [0] * n
a_ls = [0] * n
for i in range(n):
    a = int(input())
    a_ls[i] = a
    state_ls = [list(map(int, input().split())) for _ in range(a)]
    state_ls_ls[i] = state_ls

num_pat = 2 ** n
ans = 0
for i in range(num_pat):
    pattern = [0] * n
    for j in range(n):
        if ((i>>j)&1):
            
            pattern[j] = 1
    
    TF = True
    
    for k in range(n):
        if pattern[k] == 1:
            for l in range(a_ls[k]):
                st_person, st_kind = state_ls_ls[k][l]
                st_person -= 1
                if pattern[st_person] != st_kind:
                    TF = False
    if TF:
        ans = max(ans, pattern.count(1))
print(ans)

Solution (Python):
import copy


N=int(input())
A=[]
X=[]
Y=[]
for i in range(N):
    A.append(int(input()))
    Lx=[]
    Ly=[]
    for j in range(A[i]):
        x,y=map(int,input().split())
        Lx.append(x)
        Ly.append(y)
    X.append(copy.copy(Lx))
    Y.append(copy.copy(Ly))



def check(letter,n=N,a=A,x=X,y=Y):
    for k in range(n):
        if letter[k]=='1':
            number=a[k]
            for l in range(number):
                if y[k][l]!=int(letter[x[k][l]-1]):
                    return False
                    break
            else:
                continue
            break
    else:
        return True


L=[]
for m in range(2**N):
    bin_str=bin(m)[2:]
    if len(bin_str)<N:
        bin_str=(bin_str[::-1]+'0'*(N-len(bin_str)))[::-1]
    L.append(bin_str)



ans=0
for p in range(len(L)):
    if check(L[p]):
        
        ans=max(ans,L[p].count('1'))

print(ans)

Solution (Python):
N = int(input())
L = [ [] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int,input().split())
        L[i].append([person - 1, state])


honest = 0

for i in range(1,2**N):
    flag = True
    for j in range(N):
        if (i>>j)&1 == 1: 
            for x, y in L[j]:
                if (i>>x)&1 != y: 
                    flag = False
                    break 
            if not flag:
                break
    if flag:
        honest = max(honest, bin(i).count("1"))

print(honest)

Solution (Python):
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(2**n):
    state = bin(i)[2:].zfill(n)
    honest = []
    unkind = []
    for j in range(n):
        if state[j] == "0":
            unkind.append(j+1)
        else:
            honest.append(j+1)
    flag = True
    for human in honest:
        for x, y in work[human-1]:
            if y == 1 and x in unkind:
                flag = False
                break
            elif y == 0 and x in honest:
                flag = False
                break
        if not flag:
            break
    if flag:
        result = result if result>len(honest) else len(honest)
print(result)

Solution (Python):
import math

if __name__ == '__main__':
    n = int(input())
    ans = 0
    is_honest = [-1] * n
    evidence = []
    for i in range(n):
        a = int(input())
        tmp = []
        for j in range(a):
            x, y = map(int, input().split())
            tmp.append((x - 1, y))
        evidence.append(tmp)

    
    for i in range(2 ** n):
        flag = True
        for j in range(n):
            
            if not (i & (1 << j)):
                continue
            for x, y in evidence[j]:
                if y == 1 and not (i & (1 << x)):
                    flag = False
                elif y == 0 and (i & (1 << x)):
                    flag = False
        if flag:
            count = 0
            for k in range(n):
                if i & (1 << k):
                    count += 1
            ans = max(ans, count)

    print(ans)

Solution (Python):
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: 
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag = 1
                    break
    if flag == 0:  
        honest = max(honest, bin(i).count('1'))  
print(honest)

Solution (Python):
n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = [list(map(int,input().split())) for _ in range(num)]

def check(i, bit_):
    com = a[i]
    for xy in com:
        x,y = xy
        if( (bit_ >> (x-1))&1 != y ):
            return 0
    return 1

ans = 0
for i in range(2**n):
    c_num = 1
    honest = 0
    for j in range(n):
        if( (i>>j)&1 == 1 ):
            honest += 1
            c_num *= check(j, i)
    if(c_num == 0):
        continue

    ans = max(ans, honest)

print(ans)

Solution (Python):
N = int(input())
A = [0 for _ in range(N)]
X = [[[] for i in range(2)] for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i][0].append(x)
        X[i][1].append(y)
ans = 0
for i in range(pow(2,N)):
    binary = format(i, 'b').zfill(N)
    flag = True
    honest = 0
    for j in range(N):
        if int(binary[j]) == 0:
            continue
        for x, y in zip(X[j][0], X[j][1]):
            if int(binary[x-1]) != y:
                flag = False
                break
        honest += 1
    if flag:
        ans = max(ans, honest)
print(ans)

Solution (Python):
def judge(isHonest, judge_list):
    for j in judge_list:
        x, y = j 
        if isHonest[x-1] != y:
            return False
    return True  

def main():
    N = int(input())

    testimony = []
    for _ in range(N):
        A = int(input())
        testimony.append([list(map(int, input().split())) for _ in range(A)])
    
    ans = 0
    for i in range(2**N):
        judge_list = []
        isHonest = []
        for j in range(N):
            if i & (1 << j):
                judge_list += testimony[j]
                isHonest.append(1)
            else:
                isHonest.append(0)
        if judge(isHonest, judge_list):
            ans = max(ans, sum(isHonest))
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
hatugen = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        c,d = map(int,input().split())
        hatugen[i].append((c,d))
ans = 0
for i in range(1,2**n):
    consistent = True
    for j in range(n):
        
        if (i >> j) & 1 == 0:
                continue
        else:
            for l,m in hatugen[j]:
                if (i >> (l-1)) & 1 != m:
                    consistent = False
                    break
    if consistent == True:
        ans = max(ans,bin(i)[2:].count('1'))
        
print(ans)

Solution (Python):
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: 
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag = 1
                    break
    if flag == 0:  
        honest = max(honest, bin(i)[2:].count('1'))  
print(honest)

Solution (Python):
import numpy as np
import itertools

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

a = np.array(list(itertools.product([0, 1], repeat=n)), dtype=np.bool)
for i, x, y in info:
    bl = (~a[:, i]) | (a[:, x] == bool(y))
    a = a[bl]

ans = a.sum(axis=1).max()
print(ans)

Solution (Python):
def main():
    n = int(input())
    ttn = [[-1] * n for _ in range(n)]  
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = [int(z) for z in input().split()]
            x -= 1
            ttn[i][x] = y  
    ans = set()
    for i in range(2 ** n):
        tmp = [i >> j & 1 for j in range(n)]  
        possible = True
        for k, tm in enumerate(tmp):
            if not possible:
                break
            if tm:
                for l, tt in enumerate(ttn[k]):
                    if tt == -1:
                        continue
                    if tt != tmp[l]:
                        possible = False
                        break
        if possible:
            ans.add(bin(i).count('1'))
    return max(ans)


if __name__ == '__main__':
    print(main())

Solution (Python):
def main():
    n = int(input())
    ttn = [[-1] * n for _ in range(n)]  
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = [int(z) for z in input().split()]
            x -= 1
            ttn[i][x] = y  
    ans = set()
    
    for i in range(2 ** n):
        tmp = [i >> j & 1 for j in range(n)]  
        for k, tm in enumerate(tmp):
            if tm:
                for l, tt in enumerate(ttn[k]):
                    if tt == -1:
                        continue
                    if tt != tmp[l]:
                        break
                else:
                    continue
                break
        else:
            ans.add(bin(i).count('1'))
    return max(ans)


if __name__ == '__main__':
    print(main())

Solution (Python):
def check(x, y):
    for a, b in zip(x, y):
        if a != b and b != -1:
            return False
    else:
        return True


n = int(input())
remarks = []
cnt_max = 0
for _ in range(n):
    a = int(input())
    x = [tuple(map(int, input().split())) for i in range(a)]
    r = [-1] * n
    for i, j in x:
        r[i - 1] = j
    remarks.append(r)
for r in range(2 ** n):
    r = list(bin(r)[2:].zfill(n))
    r = [int(i) for i in r[:]]
    cnt = 0
    for i in range(n):
        if r[i] == 1:
            flag = check(r, remarks[i])
            cnt += 1
            if not flag:
                cnt = 0
                break
    cnt_max = max(cnt, cnt_max)
print(cnt_max)

Solution (Python):
n = int(input())
data = []
for i in range(n):
    a = int(input())
    d = []
    for j in range(a):
        xy = list(map(int,input().split()))
        d.append(xy)
    data.append(d)
ans = 0
def search(honest):
    if len(honest)==n:
        global ans
        ok = True
        for i in range(n):
            if honest[i]:
                for d in data[i]:
                    if honest[d[0]-1]!=d[1]:
                        ok = False
        if ok: ans = max(ans,honest.count(1))
    else:
        search(honest+[0])
        search(honest+[1])
search([])
print(ans)

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


def make_remark_list(i, r):
    
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people


def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        a, b = min(a, b), max(a, b)
        if (a, b) == (0, 1):
            return False
        elif (a, b) == (-1, 0):
            new_list.append(0)
        else:
            new_list.append(max(a, b))
    return new_list


remarks = []
for i in range(n):
    a = int(input())
    r = [tuple(map(int, input().split())) for _ in range(a)]
    remarks.append(make_remark_list(i, r))

def max_count(r, cnt, i = 0):
    tmp = r
    for j, r_j in enumerate(remarks):
        if j < i: continue
        if tmp[j] == 0:
            continue
        elif tmp[j] == 1:
            if check(tmp, r_j):
                tmp = check(tmp, r_j)
                cnt += 1
            else:
                cnt = 0
                break
        else:
            tmp[j] = 1
            if check(tmp, r_j):
                cnt_1, tmp_1 = max_count(tmp, cnt, j)
                tmp[j] = 0
                cnt_0, tmp_0 = max_count(tmp, cnt, j)
                if cnt_0 > cnt_1:
                    return cnt_0, tmp_0
                else:
                    return cnt_1, tmp_1
            else:
                tmp[j] = 0
    return cnt, tmp

r = [-1] * n
cnt, r = max_count(r, 0)
print(cnt)

Solution (Python):
N = int(input())
A = [0]*N
relation = []
for i in range(N):
    tmp = []
    A[i] = int(input())
    for j in range(A[i]):
        tmp.append(list(map(int, input().split())))
    relation.append(tmp)

ans = 0
for i in range(1<<N):
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  
            cond[j] = 1

    mujun = False
    stop_flag = False
    for j in range(N):  

        
        
        if cond[j] == 1:
            for k in range(A[j]):  
                
                
                if cond[relation[j][k][0]-1] != relation[j][k][1]:  
                    mujun = True
                    stop_flag = True
                    break

        if stop_flag:
            break
    
    if not mujun:
        ans = max(ans, sum(cond))

print(ans)

Solution (Python):
N = int(input())
L = []
for i in range(N):
    L.append([])
    A = int(input())
    for j in range(A):
        x,y = map(int, input().split())
        L[i].append([x-1,y])
ans = 0
for i in range(2**N):
    ok = True
    for j in range(N):
        if (i & (1 << j)) != 0:
            for x,y in L[j]:
                truth = (i & (1<<x)) == 0
                claim = y == 0
                if(truth != claim):
                    ok = False
    
    if ok:
        
        ans = max(ans, bin(i).count('1'))
print(ans)

Solution (Python):
N = int(input())
L = []
for i in range(N):
    L.append([])
    A = int(input())
    for j in range(A):
        x,y = map(int, input().split())
        L[i].append([x-1,y])
def check(i, N):
    flg = True
    for j in range(N):
        if i >> j & 1:
            for x, y in L[j]:
                if (i >> x) & 1 != y:
                    flg = False
                    return flg
    return flg
ans = 0
for i in range(2 ** N):
    if check(i, N):
        ans = max(bin(i).count("1"), ans)
print(ans)

Solution (Python):
N = int(input())
path = []
ans = 0
for i in range(N):
    A = int(input())
    path.append([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<N)
    judge = True
    for j in range(N):
        if not judge:
            break
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
                    break
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)

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

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


def check(i,n):
    flg = True
    for j in range(n):
        if i>>j & 1:
            for x,y in table[j]:
                if (i>>x)&1 != y:
                    flg = False
                    return flg
    return flg
ans = 0
for i in range(2**n):
    if check(i,n):
        ans = max(bin(i).count("1"),ans)

print(ans)

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

ans = set()
for bb in range(2 ** n):
    tmp = [0] * n
    possible = True
    for shift in range(n):
        if bb >> shift & 1:
            tmp[shift] = 1  
    for i, j in enumerate(tmp):
        if j:  
            for k in range(n):
                if g[i][k] == -1:
                    
                    continue
                if g[i][k] != tmp[k]:
                    
                    possible = False
    if possible:
        ans.add(bin(bb).count('1'))

print(max(ans))

Solution (Python):
n=int(input())
a=[0]*n
x=[[0]*n for i in range(n)]
y=[[0]*n for i in range(n)]

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return 0
      if y[i][j]==0 and honest[x[i][j]]:
        return 0
  return 1

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [1]),
             dfs(honest + [0]))
 
print(dfs([]))

Solution (Python):
n=int(input())
a=[0]*n
x=[[0]*n for i in range(n)]
y=[[0]*n for i in range(n)]

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return False
      if y[i][j]==0 and honest[x[i][j]]:
        return False
  return True

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [1]),
             dfs(honest + [0]))
 
print(dfs([]))

Solution (Python):
n=int(input())
a=[0]*n
x=[[0]*n for i in range(n)]
y=[[0]*n for i in range(n)]

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return False
      if y[i][j]==0 and honest[x[i][j]]:
        return False
  return True

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [True]),
             dfs(honest + [False]))
 
print(dfs([]))