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):
N=int(input())
g=[[-1]*N for _ in range(N)]
ans=0
for i in range(N):
    A=int(input())
    for _ in range(A):
        x,y=map(int,input().split())
        g[i][x-1]=y
for s in range(2**N):
    flag=1
    for i in range(N):
        if (s>>i&1):
            for j in range(N):
                if g[i][j]!=-1 and (s>>j&1)!=g[i][j]:
                    flag=0
    if flag==1:
        t=0
        x=s
        while x>0:
            t+=x%2
            x//=2
        ans=max(ans,t)
print(ans)

Solution (Python):
N=int(input())
lst=[[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    x,y=map(int,input().split())
    x-=1
    lst[i].append([x,y])
ans=0
for i in range(2**N):
  honest=[]
  unkind=[]
  flag=0
  for j in range(N):
    if (i>>j)&1:        
      honest.append(j)
    else:
      unkind.append(j)
  for p in honest:
    for l in lst[p]:
      x,y=l[0],l[1]
      if y:
        if x in unkind:
          flag=1
          break
      else:
        if x in honest:
          flag=1
          break
  if flag!=1:
    ans=max(ans,len(honest))
print(ans)

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

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N = i_i()

arr = [[] for _ in range(N)]
for i in range(N):
    A = i_i()
    for _ in range(A):
        x, y = i_l()
        arr[i].append((x-1, y))

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

print(ans)

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions

from functools import reduce

import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)







def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n = int(input())

d = []
for _ in range(n):
    tmp = int(input())
    tmpa = getSomeInputListInt(tmp)
    d.append(tmpa)



ans = 0
for i in range(int(pow(2, n))):
    flg = True
    cnt = 0
    for j in range(len(d)):
        tmp = (i >> j) & 1
        if tmp == 0:
            continue

        cnt += 1

        for k in range(len(d[j])):
            tmp = (i >> (d[j][k][0]-1)) & 1
            if tmp != d[j][k][1]:
               flg = False
               break
        if not flg:
            break

    if flg:
        ans = max(ans, cnt)

print(ans)

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

X = [[-1]*N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        b, c = map(int, input().split())
        X[i][b-1] = c
ans = 0
for i in range(2**N):
    Y = [0]*(N)
    for j in range(N):
        if ((i >> j) & 1):
            Y[j] = 1
    flag = True
    for j in range(N):
        if Y[j] == 1:
            for k in range(N):
                if X[j][k] == -1:
                    continue
                if X[j][k] != Y[k]:
                    flag = False
    if flag:
        ans = max(ans, sum(Y))

print(ans)

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

import numpy as np
import itertools
def tfcheck(say,tf):
    if len(say)==0:
        return 0
    for i in range(len(say)):
        for j in range(len(say[i])):
            [x,y] = say[i][j]
            if tf[x-1] == -1:
                tf[x-1] = y
                continue
            if tf[x-1] != y:
                return 0
    return 1
status = [[0,1] for i in range(n)]
m = 0
for tf in itertools.product(*status):
    s = []
    for i in range(n):
        if tf[i] == 1:
            s.append(say[i])
    if tfcheck(s,tf)==1:
        if sum(tf)>m:
            m = sum(tf)
print(m)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
 

def get_nums_l():
    return [ int(s) for s in input().split(" ")]
 

def get_nums_n(n):
    return [ int(input()) for _ in range(n)]
 

def get_all_int():
    return map(int, open(0).read().split())
 
def log(*args):
    print("DEBUG:", *args, file=sys.stderr)
 
def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret
 
n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]
 
ans = -1
for bits in range(2**n):
    ng = False
    for keta in range(n):
        if bits & 2**keta != 0:
            for a in aaa[keta]:
                if (bits & 2**(a[0]-1) != 0) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        ans = max(ans, count_bit_one(bits, n))
 
print(ans)

Solution (Python):
def is_consistent(bit, testimony):
    all_consistence = True
    for shift in range(n):
        if (bit >> shift) & 1:
            mask, tf = testimony[shift]
            if (bit & mask) != (tf & mask):
                all_consistence = False
    return all_consistence

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    if is_consistent(bit, testimony) and (max_honest < bin(bit).count('1')):
        max_honest = bin(bit).count('1')
print(max_honest)

Solution (Python):
def is_consistent(bit, t_tuple):
    mask, tf = t_tuple
    if (bit & mask) == (tf & mask):
        return True
    else:
        return False

n = int(input())
testimony = [0] * n
for i in range(n):
    mask, tf = 0, 0
    for j in range(int(input())):
        x, y = map(int, input().split())
        mask += 1 << (x - 1)
        tf += y << (x - 1)
    testimony[i] = (mask, tf)

max_honest = 0
for bit in range(1 << n):
    honest = 0
    all_consistence = True
    for shift in range(n):
        if ((bit >> shift) & 1):
            if is_consistent(bit, testimony[shift]):
                honest += 1
            else:
                all_consistence = False    
    if all_consistence and (max_honest < honest):
        max_honest = honest
print(max_honest)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret

def is_honest(bits, i):
    return bits & 2**i != 0

n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]



ans = -1

for bits in range(2**n):
    ng = False
    for keta in range(n):
        if is_honest(bits, keta):
            for a in aaa[keta]:
                if is_honest(bits, a[0]-1) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        
        ans = max(ans, count_bit_one(bits, n))

print(ans)

Solution (Python):
N=int(input())
A=[0 for j in range(N)]
B=[[] for j in range(N)]
for i in range(N):
 A[i]=int(input())
 for j in range(A[i]):
  x,y=map(int,input().split())
  B[i].append([x,y])
F=0
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 E=0
 for k in range(N):
  if Sui[k]==0:
   E+=1
  else:
   D=0
   for l in range(A[k]):
    if (Sui[B[k][l][0]-1]+B[k][l][1])%2==0:
     D+=1
   if D==A[k]:
    E+=1
 if E==N:
  H=0
  for h in range(N):
   H+=Sui[h]
  F=max(F,H)
print(F)

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

patterns = []
def dfs(N, li):
    if len(li) == N:
        patterns.append(li)
        return
    for i in range(2):
        new = li[::]
        new.append(i)
        dfs(N, new)
dfs(n, [])
ans = 0
for pattern in patterns:
    contradict = False
    for i in range(len(pattern)):
        if pattern[i] == 0:
            continue
        test = tests[i]
        for xy in test:
            x = xy[0]-1
            y = xy[1]
            if pattern[x] != y:
                contradict = True
                break
        if contradict:
            break
    if contradict:
        continue
    ans = max(ans, sum(pattern))
print(ans)

Solution (Python):
n=int(input())
a_list_sum = []
for i in range(n):
    a_tmp=int(input())
    a_list_tmp=[list(map(int,input().split())) for _ in range(a_tmp)]
    a_list_sum_tmp=[]
    a_list_sum_tmp.append(a_tmp)
    a_list_sum_tmp.append(a_list_tmp)
    a_list_sum.append(a_list_sum_tmp)
    
import itertools
L = [0, 1] 
bit_list = list(itertools.product([0, 1], repeat=n))


for i in range(len(bit_list)):
    count = 0
    
    for j in range(len(a_list_sum)):
        
        if bit_list[i][j] == 1:
            
            for k in range(len(a_list_sum[j][1])):
                
                person_id = a_list_sum[j][1][k][0] - 1
                
                is_honest = a_list_sum[j][1][k][1]
                
                if bit_list[i][person_id] != is_honest:
                    count += 1
    if count == 0:
        ans = sum(bit_list[i])
print(ans)

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

def A(s):
    count = 0
    for j in range(n):
        if s[j] == 1:
            count += 1
            for k in range(len(xy[j])):
                if s[xy[j][k][0]] != xy[j][k][1]:
                    return 0
    return count

ans = 0

for i in range(2 ** n):
    ss = []
    for h in range(n):
        if ((i >> h) & 1):
            ss.append(1)
        else:
            ss.append(0)
    ans = max(ans, A(ss))

print(ans)

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

ans = 0
for bit in range(1, (1 << N)):
    ok = True
    count = 0
    for i in range(N):
        if bit & (1 << i):
            count += 1
            for x, y in people[i]:
                if (bit & (1 << x) > 0) != (y == 1):
                    ok = False
                    break
            if not ok:
                break
    if ok and ans < count:
        ans = count
print(ans)

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

for i in range(1<<N):
  d = [0]*N
  for j in range(N):
    if (i>>j&1):
      d[j] = 1
  flag = True
  for j in range(N):
    if d[j]:
      for k,l in A[j]:
        if d[k] == l:
          continue
        if d[k] != l:
          flag = False
      if not flag:
        break
  if flag:
    ans = max(ans,sum(d))
print(ans)

Solution (Python):
from itertools import *
n = int(input())
xy =[]
for i in range(n):
    tmp = int(input())
    testimony = []
    for j in range(tmp):
        testimony.append(list(map(int, input().split())))
    xy.append(testimony)
ans = 0
for p in product([0,1],repeat=n):

    flag = True
    if sum(p) <= ans:
        continue
    for i in range(n):
        if p[i] == 0:
            continue
        for test in xy[i]:
            if p[test[0]-1] != test[1]:
                flag = False
    if flag:
        ans = sum(p)

print(ans)

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

s =[[] for _ in range(n)]

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



mx = 2**n


def hantei(num):
    flag=0
    bi =[0 for _ in range(n)]
    for j in range(n):
        bi[j] = (num>>j)%2
    
    for j in range(n):
        if((num>>j)%2 == 1):
            for x,y in s[j]:
                if(y != bi[x-1]):
                    flag = 1
                    return flag
    
    return flag

ans = 0 
for i in range(mx):
    if(hantei(i) == 0):
        
        ans = max(ans,bin(i)[2::].count("1"))
        
print(ans)

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




pattern=[]
ans=0
for i in range(2**n):
  tmp=[0]*(n)
  for j in range(n):
    if i>>j & 1:
      tmp[j]=1
  pattern.append(tmp)
  
  count=0
  flag=-1
  for j in range(n):
    if (pattern[i][j]==1):
      if (flag==-1):
        flag=0
      for k in range(a[j]):
          if (y[j][k]!=pattern[i][x[j][k]-1]):
            flag=1
            
      
  if (flag==0):
    count=sum(pattern[i])
    
  ans=max(ans,count)
  
print(ans)

Solution (Python):
N = int(input())
testimony = [[] for _ in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        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):

n=int(raw_input())
p=[[] for i in range(n)]
for i in range(n):
 a=int(raw_input())
 for j in range(a):
  p[i].append(map(int,raw_input().split()))
res=0
for i in range(2**n):
 a=[(i>>j) & 1 for j in range(n-1,-1,-1)]
 x=1
 for k in range(n):
  if a[k]*x==1:
   for l in p[k]:
    if a[l[0]-1]!=l[1]:
     x=0
 res=max(res,x*sum(a))
print res

Solution (Python):
def resolve():
    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, y))

    ans = 0
    for p in range(2**N):
        ok = True
        for i in range(N):
            for x, y in L[i]:
                if p & (1 << i):
                    if p & (1 << (x-1)) > 0 and y == 0:
                        ok = False
                        break
                    elif p & (1 << (x-1)) == 0 and y == 1:
                        ok = False
                        break

            if not ok:
                break

        if ok:
            ans = max(ans, bin(p).count('1'))

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
a_list = []
for i in range(n):
  a = int(input())
  list_ = []
  for _  in range(a):
    tuple_a = list(map(int,input().split()))
    list_.append(tuple_a)
  a_list.append(list_)
case_list = []
for i in range(2**n):
  case = [0 for i in range(n)]
  for j in range(n):
    if ((i >> j) & 1): 
      case[j] = 1
  case_list.append(case)

ok_case = []
for case in case_list:
  frug = True
  for i  in range(n):
    if case[i] == 1:
      cheker = a_list[i]
      for c in cheker :
        if c[1] != case[c[0] - 1]:
          frug = False
  if frug == True:
    ok_case.append(case)
result_list = []
for ok in ok_case:
  result_list.append(sum(ok))
print(max(result_list))

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


ans = 0



for i in range(2 ** N):
    temp = [True for _ in range(N)]
    flg = True
    for j in range(N):
        if ((i >> j) & 1):
            temp[j] = True
                
        else:
            temp[j] = False
        
    for nn, n in enumerate(temp):
        if n:
            for l, m in box[nn]:
                if m == 0:
                    if temp[l-1]:
                        flg = False
                        break
                else:
                    if not temp[l-1]:
                        flg = False
                        break
            
    if flg:
        ans = max(ans, temp.count(True))

print(ans)

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

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


def judge(bit):
    for i in range(N):
        if not (bit & (1 << i)):
            continue
        for x, y in XY[i]:
            if y == 1 and (not (bit & (1 << x))):
                return False
            if y == 0 and (bit & (1 << x)):
                return False
    return True


ans = 0
for bit in range(1 << N):
    if (judge(bit)):
        
        cnt = 0
        for i in range(N):
            if (bit & (1 << i)):
                cnt += 1
        ans = max(ans, cnt)
print(ans)

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

S=[[-1]*N for _ in range(N)]
for i in range(N):
  A=int(input())
  for _ in range(A):
    x, y=map(int, input().split())
    S[i][x-1]=y
ans=0   
for s in range(2**N):
  ok=True
  for i in range(N):
    
    if (s>>i&1)==1:
      for j in range(N):
        
        if S[i][j]!=-1 and (s>>j&1)!=S[i][j]:
          ok=False
  if ok:
    ans=max(ans, bin(s).count("1"))
    
print(ans)

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

g = [[-1 for j in range(n)] for i in range(n)]

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] != -1 and (s>>j&1) != g[i][j]:
					ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Solution (Python):
def resolve():
    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, y))

    ans = 0
    for p in range(1, 2**N):
        isOk = True
        for i in range(N):
            for x, y in L[i]:
                if p & (1 << i):
                    if p & 1 << (x-1) and not y:
                        isOk = False
                        break
                    elif not(p & 1 << (x-1)) and y:
                        isOk = False
                        break

                if not isOk:
                    break

        if isOk:
            ans = max(ans, bin(p).count('1'))

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
w = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        w[i].append([int(x) for x in input().split()])

ans = 0
for i in range(2**n):
    flag = 1
    f = [0]*n
    num = 0
    for j in range(n):
        if i & 1<<j:
            f[j] = 1
            num += 1
    for j in range(n):
        if f[j]==1:
            for k in w[j]:
                if k[1]!=f[k[0]-1]:
                    flag = 0
    
    if flag == 1:
        ans = max(ans,num)
print(ans)

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

g = [[-1]*n for i in range(n)]

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

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

print(ans)

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

g = [[-1 for j in range(n)] for i in range(n)]

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] != -1 and (s>>j&1) != g[i][j]:
					ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Solution (Python):
def judge(bit): 
  ok = True
  for i in range(n):
    if ((bit >> i) & 1) == 1: 
      for j in range(len(li[i])):
        x = li[i][j][0]
        y = li[i][j][1]
        if y == 1 and ((bit >> (x-1)) & 1) == 0:
          ok = False
        if y == 0 and ((bit >> (x-1)) & 1) == 1:
          ok = False
  return ok
n = int(input())
li = []
ans = 0
for i in range(n):
  a = int(input())
  xy =  [list(map(int, input().split())) for _ in range(a)]
  li.append(xy)
for bit in range(1<<n):
  if judge(bit):
    cnt = 0
    for i in range(n):
      if ((bit >> i) & 1) == True:
        cnt += 1
    ans = max(ans,cnt)
print(ans)

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

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i>>j) & 1:
            for k in ls[j]:
                if (i >> k[0]) & 1!= k[1]:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans,bin(i)[2:].count('1'))
print(ans)

Solution (Python):
def main():
    N = int(input())
    testimony = [[] for i in range(N)]
    for i in range(N):
        for j in range(int(input())):
            x,y = map(int,input().split())
            testimony[i].append([x-1,y])
    
    ans = 0
    for i in range(2**N):
        for j in range(N):
            flag = True
            if (i>>j)&1:
                for x,y in testimony[j]:
                    if ((i>>x)&1) != y:
                        flag = False
                        break
                if not flag:
                    break        
        if flag:
            tmp = list(bin(i))
            ans = max(ans,tmp[2:].count("1"))

    print(ans)

if __name__ == "__main__":
    main()

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

g = [[-1 for j in range(n)] for i in range(n)]

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

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

print(ans)

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

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

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 evidences[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):
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for x, y in l[j]:
      if i[j] == 1 and i[x] != y:
        flg += 1
        break
  if flg == 0:
    break
    
print(sum(i))

Solution (Python):
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
  if flg == 0:
    break
    
print(sum(i))

Solution (Python):
import itertools

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

for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)

for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
      if flg != 0:
        break
  if flg == 0:
    break
    
print(sum(i))

Solution (Python):
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
people = []

for i in range(n):
    ret = [None for i in range(n)]
    for j in range(iip()):
        x, y = iip()
        ret[x-1] = y
    people.append(ret)

def collect(mode):
    mode = bin(mode)[2:].zfill(n)
    result = mode.count("1")

    
    for i in range(n):
        if mode[i] == "0":
            continue

        for j, say in enumerate(people[i]):
            if say == 1 and mode[j] == "0":
                return 0
            if say == 0 and mode[j] == "1":
                return 0
    return result


maxx = 0
for i in range(2**(n)):
    maxx = max(maxx, collect(i))

print(maxx)

Solution (Python):


N = int(input())
maxlen = len(bin(2**N-1)[2:])
testimonies = []
res = 0

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

    testimonies.append(testimony)

for _ in range(1 << N):
    
    ok = True
    ans = [int(e) for e in bin(_)[2:].zfill(maxlen)]
    for i, t in enumerate(ans.copy()):
        if t==1: 
            for j, v in enumerate(testimonies[i]):
                if v != -1: 
                    if ans[j] == -1:
                        ans[j] = v 
                    elif ans[j] != v:
                        ok = False
    
    if ok:
        
        res = max(res, sum(e for e in ans if e==1))
    
    

print(res)

Solution (Python):
n=int(input())
A=[[2]*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())
    A[i][x-1]=y
ans=0
for i in range(2**n):
  aa=0
  s=format(i,'18b')
  H=[]
  for j in range(n):
    if s[-1-j]=="1":
      H.append(j)
      aa=aa+1
  h=set(H)
  f=0
  for j in range(len(H)):
    for k in range(n):
      if A[H[j]][k]==2:
        continue
      if A[H[j]][k]==1:
        if k not in h:
          f=1
      else:
        if k in h:
          f=1
  if f==0:
    if aa>ans:
      ans=aa
print(ans)

Solution (Python):
n=int(input())
A=[[2]*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())
    A[i][x-1]=y
ans=0
for i in range(2**n):
  aa=0
  s=format(i,'18b')
  H=[]
  for j in range(n):
    if s[-1-j]=="1":
      H.append(j)
      aa=aa+1
  h=set(H)
  f=0
  for j in range(len(H)):
    for k in range(n):
      if A[H[j]][k]==2:
        continue
      if A[H[j]][k]==1:
        if k not in h:
          f=1
      else:
        if k in h:
          f=1
  if f==0:
    if aa>ans:
      ans=aa
print(ans)

Solution (Python):
N = int(input())
A = [0] * N
xy = [0] * N
for i in range(N):
  A[i] = int(input())
  xy[i] = [0] * A[i]
  for j in range(A[i]):
    xy[i][j] = [int(k) for k in input().split()]

ans = 0
for bit in range(2**N):
  
  are_correct = True
  n_honest = 0
  for i in range(N):
    a = (bit >> i) & 1
    if a == 0:
      continue
    else:
      n_honest += 1
    for j in xy[i]:
      b = (bit >> (j[0]-1)) & 1
      if b != j[1]:
        are_correct = False
  
  if are_correct:
    if ans < n_honest:
      ans = n_honest

print(ans)

Solution (Python):
N = int(input())
A = [0] * N
xy = [0] * N
for i in range(N):
  A[i] = int(input())
  xy[i] = [0] * A[i]
  for j in range(A[i]):
    xy[i][j] = [int(k) for k in input().split()]

ans = 0
for bit in range(2**N):
  
  a = [0] * N
  for i in range(N):
    a[i] = (bit >> i) & 1
  
  are_correct = True
  for i in range(N):
    if a[i] == 0:
      continue
    for j in xy[i]:
      if a[j[0]-1] != j[1]:
        are_correct = False
  
  if are_correct:
    if ans < sum(a):
      ans = sum(a)

print(ans)

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

def judge(S,bin):
    
    
    for i in range(N):
        if bin[i] == 1:
            for j in range(len(S[i])):
                if (S[i][j][1] == 1 and bin[S[i][j][0]-1] != 1) \
                or (S[i][j][1] == 0 and bin[S[i][j][0]-1] != 0):
                    return False
    return True

ans = 0
for i in range(2**N):
    b = bin(i)
    b = b[2:]
    while len(b) < N:
        b = "0"+b
    bit = []
    for j in range(len(b)):
        if b[j] == "0":
            bit.append(0)
        else:
            bit.append(1)
    if judge(S,bit):
        ans = max(ans,sum(bit))

print(ans)