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 combinations

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

person = [x for x in range(N)]

for h_num in reversed(range(N + 1)):
    for h_ppl in combinations(person, h_num):
        ppl = [0] * N
        for i in h_ppl:
            ppl[i] = 1

        consistency = True
        for i, testimony in enumerate(A):
            for t in testimony:
                if (ppl[i] == 1 and ppl[t[0]] != t[1]):
                    consistency &= False

        if consistency:
            print(h_num)
            exit(0)

Solution (Python):
import itertools
n = int(input())
maru = []
batu = []
for i in range(n):
    tmp_maru = []
    tmp_batu = []
    a = int(input())
    for i in range(a):
        x,y = map(int,input().split())
        if y == 0:
            tmp_batu.append(x)
        else:
            tmp_maru.append(x)
    maru.append(tmp_maru)
    batu.append(tmp_batu)
seq = (0,1)
list = []
for i in itertools.product(seq, repeat=n):
    list.append(i)
ans = 0
for i in list:
    tmp = [2 for i in range(n)]
    check = 0
    for j in range(n):
        if i[j] == 0:
            tmp[j] = 0
        else:
            tmp[j] = 1
    for j in range(n):
        if i[j] == 1:
            for k in maru[j]:
                if tmp[k-1] == 0:
                    check = 1
                    break
                else:
                    tmp[k-1] = 1
            for k in batu[j]:
                if tmp[k-1] == 1:
                    check = 1
                    break
                else:
                    tmp[k-1] = 0
    if check == 0:    
        x = i.count(1)
        if x > ans:
            ans = x
print(ans)

Solution (Python):

import sys
from copy import copy

def chk(shoji, N, A, x, y):
    for chk in range(N):
        if shoji[chk]==0: continue
        for s in range(A[chk]):
            if ((y[chk][s]==1 and shoji[x[chk][s]-1]!=1) or 
                (y[chk][s]==0 and shoji[x[chk][s]-1]!=0)):
                return False
    return True

def solve(N: int, A: "List[int]", x: "List[int][int]", y: "List[int][int]"):
    fmt="0"+str(N)+"b"
    ans=0
    for kans in range(2**N):
        lst=list(format(kans,fmt))
        if chk([int(c) for c in lst], N, A, x, y):
            ans=max(ans, lst.count('1'))
    print(ans)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A=[0]*N
    x=[[0 for i in range(N)] for j in range(15)]
    y=[[0 for i in range(N)] for j in range(15)]
    for k in range(N):
        A[k] = int(next(tokens))
        for l in range(A[k]):
            x[k][l] = int(next(tokens))
            y[k][l] = int(next(tokens))
    solve(N, A, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
X = [[] for k in range(N)]
A = [0 for k in range(N)]

for k in range(N):
    A[k] = int(input())
    X[k] = [list(map(int, input().split())) for i in range(A[k])]
    

ans = [0]
for m in range(2**N)[::-1]:
    s = str(bin(m))[2:].zfill(N)
    li = list(s)
    li = [int(a) for a in li]
    chk = 1
    for k in range(N): 
        if li[k] == 0: 
            pass
        elif A[k] == 0: 
            pass
        else: 
            for y in X[k]:
                if y[1] == li[y[0]-1]: 
                    pass
                else: 
                    chk = 0
                        
    if chk == 1:
        ans.append(sum(li))
        break
    else:
        pass


print(max(ans))

Solution (Python):
N = int(input())
matrix = [[0 for i in range(N)] for j in range(N)]
for n in range(N):
    A = int(input())
    for a in range(A):
        array = [int(i) for i in input().split()]
        matrix[n][array[0]-1] = 1 if array[1] == 1 else -1
l = [True,False]
from itertools import product
for pattern in product(l,repeat=N):
    able = True
    for i,p in enumerate(pattern):
        if p:
            for a,b in zip(matrix[i],pattern):
                if (b==True and a==-1) or (b==False and a == 1):
                    able = False
                    break
            if able == False:
                break
        else:
            pass
    if able == True:
        break
print(sum(pattern))

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

for i in range(n):
    A = int(input())
    p = []
    for j in range(A):
        x,y = map(int, input().split())
        p.append([x,y])
    P.append(p)

d = len(str(bin(2**n))[2:])-1

for i in range(2**n)[::-1]:
    S = str(bin(i))[2:].zfill(d)
    for j,s in enumerate(S):
        if s == '1':
            for q in P[j]:
                x,y = q
                if S[x-1] != str(y):
                    break
            else:
                continue
            break
    else:
        print(S.count('1'))
        exit()

Solution (Python):
from copy import deepcopy 
n = int(input())
list1 = [] 
ans = 0
for i in range(n):
    q = int(input())
    if q != 0:
        list1.append([list(map(int,input().split())) for j in range(q)])
    else:
        list1.append([])

bin_list = []
for i in range(2**n):
    bin_list = list(format(i, 'b').zfill(n))
    bin_list = [0 if i == "1" else 1 for i in bin_list]
    tf_list = deepcopy(bin_list)
    flag = 1
    
    
    for j in range(n):
        if bin_list[j] == 1: 
            for person,tf in list1[j]: 
                if tf_list[person-1] != tf:
                    if tf_list[person-1] == -1:
                        tf_list[person-1] = tf
                    else:
                        flag = 0
                        break
        if not flag:break
    if flag: 
        print(sum(bin_list))
        exit()

Solution (Python):
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [[] for _ in range(N + 1)]
for i in range(1, N + 1):
  t = int(input())
  for _ in range(t):
    a[i].append(tuple(map(int, input().split())))
x = [i for i in range(1, N + 1)]
res = 0

for i in range(N + 1):
  for c in combi(x, i):
    
    table = [0] * (N + 1)
    for p in c:
      table[p] = 1
    f = 0
    for p in c:
      
      for q in a[p]:

        if table[q[0]] != q[1] and (table[q[0]] != -1):
          f = 1
          break
        table[q[0]] = q[1]
      if f: break
    for i in range(1, N + 1):
      if table[i] == 1:
        for q in a[i]:
          if table[q[0]] != q[1] and (table[q[0]] != -1):
            f = 1
            break
          table[q[0]] = q[1]

        if f: break
    if f == 0:
      res = max(res, len(c))
      

print(res)

Solution (Python):
N=int(input())
A=[0]*N
L=[[[-1]*2 for i in range (15)] for j in range (N)]
C=[1]*N
c=2**N-1
H=0
for i in range(N):
    A[i]=int(input())
    for j in range(A[i]):
        L[i][j][0],L[i][j][1]=map(int,input().split())

for i in range(c,-1,-1):
    C=list(format(i, '015b'))
    f=0
    M=C[15-N:15]
    h=0
    for e in range(N):
        h+=int(M[e])
    if(H>=h):break
    for k in range(N):
        for l in range(15):
            if(int(M[k])==0):break
            if(L[k][l][0]==-1):break
            if((int(M[L[k][l][0]-1])) != int(L[k][l][1])):
                f=1
                break
        if(f==1):
            break
    if(f==0):
        H=h

print(H)

Solution (Python):
from collections import defaultdict

N = int(input())
L = [[] 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
        L[i].append((x, y))

ans = 0
for s in range(1 << N):
    honest = 0
    D = defaultdict(list)
    for i in range(N):
        if s >> i & 1:
            honest += 1
            D[i].append(1)
            for x, y in L[i]:
                D[x].append(y)

    mujun = False
    for k, v in D.items():
        if len(set(v)) != 1:
            mujun = True
        if s >> k & 1:
            if v[0] == 0:
                mujun = True
        else:
            if v[0] == 1:
                mujun = True

    if not mujun:
        ans = max(ans, honest)

print(ans)

Solution (Python):
N = int(input())
B = [[] for i in range(N)]
C = []
for i in range(N):
  M = int(input())
  C.append(M)
  for j in range(M):
    B[i].append([int(s) for s in input().split()])

def check_val(val, digit):
  return (val%2**(digit+1))//(2**(digit))

count = 0
for i in range(2**N):
  A = []
  for j in range(N):
    A.append(check_val(i, j))
  A.reverse()
  flg = True
  for j, Ad in enumerate(A):
    if Ad == 1:
      for E, F in B[j]:
        if F != A[E-1]:
          flg = False
  if flg == True:
    count = sum(A)
print(count)

Solution (Python):
n = int(raw_input())
d ={}
for i in range(1,n+1):
    nt = int(raw_input())
    all_testemonies = []
    for ii in range(nt):
        testemony_inpt = raw_input().split(" ")
        
        x, y =int(testemony_inpt[0]), int(testemony_inpt[1])
        all_testemonies.append([x,y])
    d[i] =all_testemonies

def get_honest_shougens(state, d, for_target):
    shougens = []
    for i in range(len(state)):
        if i+1 == for_target: 
            continue
        elif state[i] != 1: 
            continue
        else:
            current_shougens = d[i+1]
            for ii in current_shougens:
                if ii[0] == for_target:
                    shougens.append(ii)
    return shougens

def check_consistency(state, d):
    c = 0
    for i in range(len(state)):
        shougens = get_honest_shougens(state, d, i+1)
        if state[i] == 1:
            if [i+1, 0] in shougens:
                return False
            else:
                c+=1
        elif state[i] == 0:
            if [i+1,1] in shougens:
                return False
            else:
                c+=1
        else:
            print("strange state..", state[i])
    if c == len(state):
        return True
    else:
        return False

import itertools
combinations = list(itertools.product([0, 1], repeat=n))
highest = 0
for i in combinations:
    s = sum(i)
    if s == 0:
        continue 
    else:
        c = check_consistency(i, d)
        if c:
            if s>highest:
                highest = s
print(highest)

Solution (Python):
N=int(input())
evid = []

count=0
while count < N:
    A = int(input())
    temp = []
    in_count = 0
    while in_count < A:
        l=list(map(int, input().split()))
        temp.append( l )
        in_count += 1
    evid.append(temp)
    count += 1

all_pattern = 2**N

max_num = 0
for pattern in range(all_pattern+1):
    break_flag = False
    for ii in range(N):
        person_evid = (pattern>>ii) & 1
        
        for temp_evid in evid[ii]:
            if person_evid == 1 and (pattern>>(temp_evid[0]-1) ) & 1 != temp_evid[1]:
                break_flag = True
            
            
            if break_flag:
                
                break

        if break_flag:
            break
    if break_flag:
        continue
    num = 0
    for ii in range(N):
        num += (pattern>>ii) & 1
    if max_num < num:
        max_num = num
print(max_num)

Solution (Python):
n=int(input())
lists=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        lists[i].append([x,y])
ans=0
for k in range(2**n):
    subans=0
    flag=True
    string=format(k,"0%ib"%n)
    listss=["unknown" for i in range(n)]
    for i in range(n):
        if string[i]=="1":
            
            subans+=1
            for some in lists[i]:
                if listss[some[0]-1]=="unknown":
                    listss[some[0]-1]=some[1]
                elif listss[some[0]-1]!="unknown":
                    if listss[some[0]-1]!=some[1]:
                        flag=False
                        break

    if flag:
        flags=True
        for i in range(n):
            if  listss[i]!="unknown" and listss[i]!=int(string[i]):
                flags=False
        if flags:
            ans=max(ans,subans)

print(ans)

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

import sys
input = sys.stdin.readline

testimony = {}

for n in range(1, N+1):
    A = int(input())
    testimony[n] = {}
    for _ in range(A):
        x, y = map(int, input().split())
        testimony[n][x] = y


def dfs(idx, ans):
    
    if not idx in testimony:
        ret = 0
        
        for a in ans:
            if a != 0:
                ret += 1
        return ret
    
    ans_true = ans[:]
    flag_true = True
    ans_false = ans[:]
    flag_false = True
    
    if ans[idx] == 0:
        flag_true = False
    else:
        ans_true[idx] = 1
        for k, v in testimony[idx].items():
            if ans_true[k] == 2 or ans_true[k] == v:
                ans_true[k] = v
            else:
                flag_true = False
                break
    if ans[idx] == 1:
        flag_false = False
    else:
        ans_false[idx] = 0
        
        
        
        
        
        
        
            
    if flag_false and flag_true:
        a = dfs(idx+1, ans_true)
        b = dfs(idx+1, ans_false)
        return max(a, b)
    elif flag_false:
        return dfs(idx+1, ans_false)
    elif flag_true:
        return dfs(idx+1, ans_true)
    else:
        return 0
        
    
ans = dfs(1, [0]+[2]*N)
print(ans)

Solution (Python):


n=int(input())
mention_list = {}

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

max_count = 0
num = 2**n
flag = 0
for i in range(1,num):
    bina = bin(i)[2:].zfill(n)
    count = 0
    for x in range(n):
        j = int(bina[x])
        flag = 0
        if j == 1:
            for mention in mention_list[x]:
                if int(bina[mention[0]]) != int(mention[1]):
                    flag = -1
                    break
            if flag == -1:
                break
            count = count + 1
    if flag == -1:
        continue
    max_count = max(max_count, count )

print(max_count)

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    xy = {i+1:[] for i in range(N)}
    
    for i in range(N):
        for j in range(int(input())):
            xy[i+1].append(tuple(map(int, input().split())))
            
    ans = 0
    nums = [2**i for i in range(N)]
    for i in range(1, 2**N):
        num = [idx+1 for idx, n in enumerate(nums) if i & n != 0]
        visited = [False] * (N+1)
        A = [None] * (N+1)
        
        f = True
        for i in num: A[i] = True
        
        while num:
            n = num.pop(0)
            if visited[n]: continue
            visited[n] = True
            
            for x, y in xy[n]:
                if A[x] is None: 
                    A[x] = y
                    if y and not visited[x]: num.append(x)
                    
                elif A[x] == y: continue
                else: f = False; break
            if not f: break
        if f: 
            ans = max(ans, sum([a for a in A if not a is None]))
            
    print(ans)

if __name__ == '__main__':
    main()

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

def search(l):
  global seigo,syougen,flg
  for x,y in l:
    if seigo[x-1]==100:
      seigo[x-1]=y
      if y==1:
        search(syougen[x-1])
    elif seigo[x-1]!=y:
      flg=False

ans=0
for i in range(N):
  flg=True
  seigo=[100]*N
  seigo[i]=1
  _ans=0
  search(syougen[i])
  if flg:
    if sum(seigo)>100:
      i=0
      while sum(seigo)>100:
        if seigo[i]==100:
          _seigo=seigo[:]
          flg=True
          seigo[i]=1
          search(syougen[i])
          if flg:
            pass
          else:
            seigo=_seigo[:]
            seigo[i]=0
        i+=1
        i%=N
    _ans=sum(seigo)%100
    if _ans>ans:
      ans=_ans
      maxseigo=seigo        
print(ans)

Solution (Python):
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = []
B = []

i = 1
try:
    while True:
        a = int(inputs[i])
        A.append(a)
        B.append([tuple(map(int, inputs[j].split())) for j in range(i+1, i+a+1)])
        i += a+1        
except IndexError:
    pass

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in B[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Solution (Python):
def main():
    N = int(input())
    A = []
    for i in range(N):
        a = int(input())
        h, d = 0, 0
        for _ in range(a):
            x, y = [int(i) for i in input().split()]
            if y == 1:
                h |= 1 << (x - 1)
            else:
                d |= 1 << (x - 1)
        A.append((i, h, d))
    
    m = 0
    for n in range(2 ** N):
        ch, cd = 0, 0
        mm = 0
        for i, h, d in A:
            if n & (1 << i):
                ch |= h | (1 << i)
                cd |= d
                if ch & cd:
                    break
                if cd & n:
                    break
                mm += 1
            elif ch & (1 << i):
                break
        else:
            if n == ch:
                m = max(m, mm)
    print(m)


main()

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

flag = False

Ai = []
xij = []
yij = []


for i in range(N):
    Ai_temp=int(raw_input())
    Ai.append(Ai_temp)
    x_temp = []
    y_temp = []
    for j in range(Ai_temp):
        x, y = map(int, raw_input().split())
        x_temp.append(x)
        y_temp.append(y)
    xij.append(x_temp)
    yij.append(y_temp)

ans_max = 0
for l in reversed(range(2**N)):
    flag = True
    for i in range(N):
        Ai_temp = Ai[i]
        if (l>>i)&0b1 == 1:
            for j in range(Ai_temp):
                xij_temp = xij[i][j]
                yij_temp = yij[i][j]
                if (l>>(xij_temp-1))&0b1 != yij_temp:

                    flag = False
                    break

        if flag == False:
            break

    if flag == True:


        ans = 0
        for i in bin(l)[2:]:
            ans = ans + int(i)
        if ans > ans_max:
            ans_max = ans

print ans_max

Solution (Python):
import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) 

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

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]): return False
    if not(np.all(mask[a[1]])): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)

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


def main():
    N = int(input())
    H = [set() for _ in range(N)]
    U = [set() for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            if y == 1:
                H[i].add(x)
            else:
                U[i].add(x)

    ans = 0
    for i in range(1 << N):

        h = set()
        u = set()
        for j in range(N):
            if ((i >> j) & 1) == 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for j in range(N):
            if ((i >> j) & 1) == 1:
                if H[j] & u:
                    b = False
                    break
                else:
                    h |= H[j]
                if U[j] & h:
                    b = False
                    break
                else:
                    u |= U[j]
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

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

table = [[-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())
    table[i][x-1] = y


result = 0
for i in range(2**N):
  state = bin(i)[2:]
  state = list('0' * (N - len(state)) + state)
  d = 1
  for i, tf in enumerate(state):
    if tf == '1':
      c = 1
      for j, a in enumerate(table[i]):
        if a == 1:
          if state[j] != '1':
            c = 0
            break
        elif a == 0:
          if state[j] != '0':
            c = 0
            break
      if c != 1:
        d = 0
        break
  if d == 1:
    result = max(result, state.count('1'))

print(result)

Solution (Python):
n = int(input())
x_arr = []
y_arr = []

for i in range(n):
  a = int(input())
  x = []
  y = []
  for j in range(a):
    tmp1,tmp2 = map(int,input().split())
    x.append(tmp1)
    y.append(tmp2)
    
  x_arr.append(x)
  y_arr.append(y)

ans = 0
for i in range(2 ** n):
  
  flag3 = True
  bin_str = format(i,'b').zfill(n)
  array = [-1] * (n+1)
  for k in range(len(bin_str)):
    if (array[k+1] != -1) and (int(bin_str[k]) != array[k+1]):
      flag3 = False
      break
    
    if bin_str[k] == '0':
      array[k+1] = 0
      continue
    else:
      array[k+1] = 1
      

    x = x_arr[k]
    y = y_arr[k]
    
    flag2 = True
    for j in range(len(x)):
      flag = True
      tmp1 = x[j]
      tmp2 = y[j]
      if array[tmp1] == -1:
        array[tmp1] = tmp2
      elif array[tmp1] != tmp2:
        flag = False
      else:
        pass
      
      if not flag:
        flag2 = False
        break
        
    if not flag2:
      flag3 = False
      break
    
  if not flag3:
    continue
    
  ans = max(ans, len(bin_str.replace('0','')))
    
print(ans)

Solution (Python):
from collections import deque
N = int(input())
table = [[] for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int, input().split())
    table[i].append((x,y))
ans = 0
for i in range(2**N):
    memo = [-1]*N
    flag = 0
    tmp = 0
    H = deque()
    for j in range(N):
        if (i>>j)&1:
            tmp += 1
            if memo[j] == -1:
                memo[j] = 1
            else:
                if memo[j] != 1:
                    tmp = 0
                    flag = 1
                    break

            for x,y in table[j]:
                x -= 1
                if memo[x] == -1:
                    memo[x] = y
                else:
                    if memo[x] != y:
                        tmp = 0
                        flag = 1
                        break
            if flag == 1:
                break
        else:
            if memo[j] == -1:
                memo[j] = 0
            else:
                if memo[j] != 0:
                    tmp = 0
                    flag = 1
                    break
    ans = max(tmp,ans)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

L = [[-1 for j in range(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())
        L[i][x-1] = y



ans = 0
for i in range(2**(N)):
    if len(str(bin(i))[2:]) < N:
        K = ["0"] * (N-len(str(bin(i))[2:])) + list(str(bin(i))[2:])
    else:
        K = list(str(bin(i))[2:])
    for j in range(N):
        
        flag = 1
        if K[j] == "0":
            pass
        else:
            for l in range(N):

                if L[j][l] == -1:
                    continue
                elif L[j][l] == 0:
                    if K[l] == "1":
                        flag = 0
                        break
                elif L[j][l] == 1:
                    if K[l] == "0":
                        flag = 0
                        break
        if flag == 0:
            break
        if j == N-1:
            ans = max(ans, K.count("1"))

print(ans)

Solution (Python):
n = int(input())
a = [0] * n
d = {}
ans = 0
for i in range(n):
    d[i] = []
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        d[i].append([int(_) for _ in input().split()])
for i in range(0, 2**n):
    fool = 'yes'
    bin_str = format(i, '0' + str(n) + 'b')
    
    res = {}
    for j in range(n):
        res[j] = bin_str[j]
    
    for k in range(n):
        if res[k] == '1':
            for l in d[k]:
                x = l[0] - 1
                y = l[1]
                
                if res[x] != str(y):
                    fool = 'no'
    
    if fool == 'yes':
        tem = 0
        for i in range(n):
            if res[i] == '1':
                tem += 1
        ans = max(ans, tem)
print(ans)

Solution (Python):
N=int(input())
flag=0
E=[]
total=0
maxi=0
for i in range(N):
    E.append([0]*N)
for i in range(N):
    M=int(input())
    for j in range(M):
        C, D = map(int, input().split())
        if D==1:
            D=2
        else:
            D=1
        E[i][C-1]+=D



A=[]
for i in range((2**N)):
    s=format(i,'b')
    A.append(s.zfill(N))


for i in range(len(A)):
    flag=0
    total=0
    S=A[i]
    
    for j in range(len(S)):
        if S[j]=='0':
            for k in range(N):
                
                if (E[j][k]==1 and S[k]=='0')or (E[j][k] == 2 and S[k] == '1'):
                    
                    flag=1
    if flag==0:
        for o in range(len(S)):
            if S[o]=='0':
                total+=1
        maxi=max(maxi,total)
print(maxi)

Solution (Python):
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
  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):
  z=str(format(i,('0'+str(n)+'b')))
  f=1
  for k in range(n):
    if f:
      if int(z[k]):
        for m in l[k]:
          if z[m[0]]!=str(m[1]):
            f=0
  if f:            
    ans=max(ans,z.count('1'))    
print(ans)

Solution (Python):
def is_contradict(T, H):
    for t in T:
        a = t[0]
        x = t[1]
        y = t[2]
        if int(H[a-1]) == 1 and int(H[x-1]) != y:
            return True
    return False

def main():
    N=int(input())
    T=[]
    for n in range(N):
        A=int(input())
        for a in range(A):
            x,y = map(int, input().split())
            T.append((n+1,x,y))
    
    ans = 0
    for i in range(2**N):
        s = format(i, "015b")
        s = s[15 - N:]
        if not is_contradict(T, s):
            c = s.count("1")
            if ans < c:
                ans = c
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

comb = itertools.product([0, 1], repeat=n)
ans = 0
for c in comb:
    list_c = list(c)
    flag = True
    for i in range(len(xy)):
        if list_c[i] == 1:
            for j in range(len(xy[i])):
                if xy[i][j][1] == 1:
                    if list_c[xy[i][j][0]-1] != 1:
                        flag = False
                        break
                else:
                    if list_c[xy[i][j][0]-1] != 0:
                        flag = False
                        break
    if flag:
        ans = max(ans, list_c.count(1))
print(ans)

Solution (Python):
def examC():
    N = I()
    A = [0]*N; xy = [[] for _ in range(N)]
    for i in range(N):
        A[i] = I()
        for j in range(A[i]):
            s1,s2 = LI()
            xy[i].append([s1,s2])

    loop = 2**N; differ = 2**4
    ans = 0
    for i in range(loop):
        uso = [False]*N
        honto = [False]*N
        cur = 0
        for j in range(N+1):
            if i&(2**j)==(2**j):
                cur +=1

        for j in range(N):
            if i&(2**j)==(2**j):
                for k in xy[j]:
                    if k[1]==0:
                        uso[k[0]-1] = True
                    elif k[1]==1:
                        honto[k[0]-1] = True

        for j in range(N):
            if uso[j] and i&(2**j)==(2**j):
                cur = 0
                break
            if honto[j] and i&(2**j)==0:
                cur = 0
                break
        ans = max(ans,cur)
    print(ans)

    return

def examD(mod):
    N = I(); A = LI()
    d = defaultdict(int)
    for i in range(N):
        cur = A[i]
        j = 1
        while(cur>0):
            if cur&1==1:
                d[j] +=1
            j +=1
            cur >>=1
    ans = 0
    for i,j in d.items():
        ans += j*(N-j) * 2**(i-1)
        ans %=mod
    print(ans)
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

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

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

maxCnt = 0
for i in range(2 ** n):
    bin_str = format(i, 'b').zfill(n)
    trueFlg = 1
    for j in range(n):
        for k in B[j]:
            if bin_str[j] == '1':
                if int(bin_str[k[0] -1]) != k[1]:
                    trueFlg = 0
                    break




    if trueFlg == 1:
        maxCnt = max(maxCnt, bin_str.count('1'))

print(maxCnt)

Solution (Python):

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

rst = 0
chk = 2 ** n
for h in list(range(chk))[::-1]:
    h_list = ("{:0>"+str(n)+"}").format(bin(h)[2::])
    flag = True
    for i, a in enumerate(h_list):
        if a == '0':
            continue

        for x, y in tests[i]:
            ys = str(y)
            if h_list[x-1] == ys:
                continue
            else:
                flag = False
                break
        
        if not flag:
            break
    
    if flag:
        rst = h_list.count('1')
        break

print(rst)