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):
def main():
    N = int(input())
    A = [int()] * N
    x = [[] for i in range(N)]
    y = [[] for i in range(N)]
    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            xij, yij = map(int, input().split())
            x[i].append(xij - 1)
            y[i].append(yij)
    ans = 0
    for b in range(1 << N):
        flg = True
        for i in range(N):
            if not b & 1 << i:
                continue
            for j in range(A[i]):
                if 1 & b >> x[i][j] ^ y[i][j]:
                    flg = False
                    break
            if not flg:
                break
        if flg:
            ans = max(ans, bin(b)[2:].count("1"))
    print(ans)
    return


main()

Solution (Python):
N = int(input())
A_list = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for a in range(A):
        x, y = map(int, input().split())
        A_list[i].append([x,y])
ans = 0
for i in range(1 << N):
    for j in range(N):
        wrong = False
        if 1 << j & i:
            prf = A_list[j]
            for p in prf:
                x, y = p
                if y == 0 and not (i & 1 << (x - 1)):
                    continue
                elif (i & 1 << (x - 1)) and y == 1:
                    continue
                else:
                    wrong = True
                    break

        if wrong:
            break
    if not wrong:
        cnt = 0
        for j in range(N):
            if 1 << j & i:
                cnt += 1
        ans = max(ans, cnt)
print(ans)

Solution (Python):
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)



import numpy
import scipy




def best(bm):
    res = [-1] * N
    for i in range(N):
        if (bm & (1 << i) == 0):
            if (res[i] == 1):
                return -1

            res[i] = 0
            continue

        if (res[i] == 0):
            return -1

        res[i] = 1

        for x, y in ts[i]:
            
            if res[x] == -1:
                res[x] = y
            elif res[x] != y:
                return -1

    cnt = 0

    for v in res:
        if v:
            cnt += 1

    return cnt



N = gi()
ts = []

for i in range(N):
    ai = gi()
    ts.append([])
    for j in range(ai):
        x = gi() - 1
        y = gi()
        ts[i].append((x, y))

ans = 0
for bitmap in range(1 << N):
    ans = max(ans, best(bitmap))

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):


N = int(input())

ans = 0


syo = [ [] for i in range(N)]

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


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

print(ans)

Solution (Python):
from collections import Counter
N = int(input())
ans = 0
evidence = [[] for n in range(N)]

for n in range(N):
    A = int(input())
    for a in range(A):
        lis = list(map(int, input().split()))
        evidence[n].append(lis)

for n in range(1 << N):
    bits = [(n >> i) & 1 for i in range(N)]
    flag = True
    boolean = True
    for i in range(N):
        if (n >> i) & 1 == 0:
            continue
        for x, y in evidence[i]:
            if bits[x-1] == y:
                continue
            flag = False
    if flag:
        ans = max(ans, sum(bits))
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 i in range(1<<n):
    ok = True
    for j in range(n):
        
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i).count('1'))
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))

def digitsum(x):
    return bin(x).count('1')

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

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

Y=list()
for i in range(N):
   Y.append([])

for i in range(N):
   A_i=int(input())
   A.append(A_i)

   for j in range(A_i):
      x,y=list(map(int,input().split()))
      X[i].append(x)
      Y[i].append(y)

max_nin=0

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

   liar_kamo=[c for c in range(N)]
   liar_kamo=list(set(liar_kamo)-set(honest_kamo))
   
   

   flag=True
   for i in honest_kamo:
      for j in range(A[i]):
         if Y[i][j]==1:
            if X[i][j]-1 in liar_kamo:
               flag=False
         elif Y[i][j]==0:
            if X[i][j]-1 in honest_kamo:
               flag=False
   
   
   if flag:
      max_nin=max(max_nin,len(honest_kamo))

print(max_nin)

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))

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

Solution (Python):
import itertools
import queue


def does_contradict(assumed_honest_men):
    table = {i: None for i in range(1, N+1)}
    table.update({man: 1 for man in assumed_honest_men})
    for honest_man in assumed_honest_men:
        for target, flag in testimonies[honest_man]:
            if table[target] is None and flag == 1:
                return True
            elif table[target] is not None and table[target] != flag:
                return True
    return False


N = int(input())
testimonies = dict()
for witness in range(1, N+1):
    testimonies[witness] = list()
    for _ in range(int(input())):
        target, flag = map(int, input().split(" "))
        testimonies[witness].append((target, flag))

for i in range(N+1, 0, -1):
    for assumption in itertools.combinations(range(1, N+1), i):
        if not does_contradict(assumption):
            print(len(assumption))
            exit(0)
else:
    print(0)

Solution (Python):
n = int(input())
t = []
for i in range(n):
  m = int(input())
  t.append({})
  for j in range(m):
    x, y = map(int, input().split())
    t[-1][x-1] = y == 1
res = 0
for i in range(1 << n):
  s = [(i & (1 << j)) > 0 for j in range(n)]
  good = True
  for j in range(n):
    if (s[j] and any(t[j][x] != s[x] for x in t[j])) or (not s[j] and all(t[j][x] == s[x] for x in t[j])):
      good = False
      break
  if good:
    res = max(res, sum(1 for x in s if x))
print(res)

Solution (Python):
n=int(input())
a=[]
syougen=[]
for i in range(n):
  a+=[int(input())]
  syougen+=[[list(map(int,input().split()))for j in range(a[-1])]]
for i in range(n):
  for j in range(a[i]):
    syougen[i][j][0]-=1
honest=0
for i in range(2**n):
  t=[0]*(n-len(str(bin(i)))+2)+list(map(int,str(bin(i))[2:]))
  flag=1
  for j in range(n):
    if t[j]:
      for k in range(a[j]):
        if t[syougen[j][k][0]]!=syougen[j][k][1]:flag=0
  if flag:
    if honest<t.count(1):honest=t.count(1)
print(honest)

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

a = []
xy = []

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




ans = 0

for i in range(2 ** n):
    memo = [1] * n
    for j in range(n):
        if (i >> j) & 1:
            memo[n - j - 1] = 0
    

    for p in range(n):
        flag = True
        for q in range(a[p]):
            x = xy[p][q][0] - 1
            y = xy[p][q][1]
            if memo[p] == 1 and memo[x] != y:
                flag = False
                break
            
            
            
        if not flag:
            break

    if flag:
        ans = max(ans, memo.count(1))

print(ans)

Solution (Python):
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
SYOUGEN = [[] for _ in range(N)]

for i in range(N):
  n = readi()
  for _ in range(n):
    x, y = ints()
    x -= 1

    SYOUGEN[i].append((x, y))
  
def num1(f):
  s = 0
  while f>0:
    s += f%2
    f //= 2
  return s

def success(f):
  shoujikimono = []
  for _ in range(N):
    shoujikimono.append(f%2)
    f //= 2

  for i in range(N):
    if shoujikimono[i]:
      for x, y in SYOUGEN[i]:
        if shoujikimono[x]!=y:
          return False
  return True

maxn = 0
for f in range(2**N):
  n = num1(f)
  if success(f):
    maxn = max(maxn, n)


print(maxn)

Solution (Python):
n=int(input())
evi=[]
for i in range(n):
    a=int(input())
    l=[list(map(int,input().split())) for i in range(a)]
    evi+=[l]
ans=0
for i in range(2**n):
    mujyun=[]
    h_list=[]
    count=0
    for j in range(n):
        if ((i>>j)&1):
            count+=1
            mujyun+=[[j+1,0]]
            h_list+=evi[j]
        else:
            mujyun+=[[j+1,1]]
        
    for k in mujyun:
        if k in h_list:
            count=0
            break
        
    ans=max(ans,count)
print(ans)

Solution (Python):
n = int(input())
A = []
proofs = []
for i in range(n):
    A.append(int(input()))
    proof = [tuple(map(int, input().split())) for _ in range(A[i])]
    proofs.append(proof)

def check_amb(true_men, proofs):
    for true_man in true_men:
        proof = proofs[true_man]
        for x, y in proof:
            if (x-1 in true_men) and (y == 0):
                return True
            if (x-1 not in true_men) and (y == 1):
                return True
    return False


max_pat = 0
for i in range(1 << n):
    true_men = []
    for j in range(n):
        if ((i >> j) & 1) == 1:
            true_men.append(j)
    is_amb = check_amb(true_men, proofs)
    if is_amb is False:
        max_pat = max(len(true_men), max_pat)

print(max_pat)

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

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

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

ans = 0

for i in range(1, 2 ** n):
    ok = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for x, y in g[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):










N = int(input())
syoujiki = []
fusin = []
for _ in range(N):
    a = int(input())
    syou = set()
    fusi = set()
    for _ in range(a):
        x, y = list(map(int, input().split()))
        if y == 1:
            syou.add(x - 1)  
        else:
            fusi.add(x - 1)
    syoujiki.append(syou)
    fusin.append(fusi)


def is_ok(n):  
    
    ret = 0
    katei = set()
    for i in range(N):
        if (n >> i) % 2:  
            katei.add(i)
            ret += 1

    
    

    for i in katei:  
        cond1 = syoujiki[i].issubset(katei)  
        cond2 = fusin[i].isdisjoint(katei)
        
        
        if (not cond1) or (not cond2):
            return 0
    return ret


ans = 0
for katei in range(1 << N):
    ans = max(is_ok(katei), ans)

print(ans)

Solution (Python):










N = int(input())
syoujiki = []
fusin = []
for _ in range(N):
    a = int(input())
    syou = set()
    fusi = set()
    for _ in range(a):
        x, y = list(map(int, input().split()))
        if y == 1:
            syou.add(x - 1)  
        else:
            fusi.add(x - 1)
    syoujiki.append(syou)
    fusin.append(fusi)


def is_ok(n):  
    
    ret = 0
    katei = set()
    for i in range(N):
        if (n >> i) % 2:  
            katei.add(i)
            ret += 1

    
    

    for i in katei:  
        cond1 = syoujiki[i].issubset(katei)  
        cond2 = fusin[i].isdisjoint(katei)
        
        
        if (not cond1) or (not cond2):
            return 0
    return ret


ans = 0
for katei in range(1 << N):
    ans = max(is_ok(katei), ans)

print(ans)

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for x,y in A[j]:
                if (i >> x) & 1 != y:
                    flag = False
                    break
    if flag:
        ans = max(ans, bin(i)[2:].count("1"))

print(ans)

Solution (Python):
n = int(input())
xy = [[]] * n
cnt = 0

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

bit = '0' + str(n) + 'b'
for k in range(2**n):
  cnt_current = 0
  flg = True
  katei = format(k, bit)
  
  for l in range(len(xy)):
    if flg == False:
      break
    if katei[l] == '0':
      continue
    else:
      for m in range(len(xy[l])):
        if int(xy[l][m][1]) != int(katei[xy[l][m][0]-1]):
          flg = False
          break
  if flg == True:
    cnt_current = katei.count('1')
  if cnt_current > cnt:
    cnt = cnt_current
    
print(cnt)

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

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

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

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

shogen = [[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    person, state = map(int, input().split())
    shogen[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 person, state in shogen[j]:
        
        if (i>>person)&1 != state:
          flag = 1
          break
  
  if flag == 0:
    honest = max(honest, bin(i)[2:].count('1'))
print(honest)

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

xyss = [[] for i in range(n)]

for i in range(n):
  num_a = int(input())
  for j in range(num_a):
    x, y = [int(i) for i in input().split()]
    xyss[i].append([x, y])

cnt = 0

for i in range(2 ** n - 1, 0, -1):
  b = format(i, '0' + str(n) + 'b')
  ok = True

  for j in range(n):
    if b[j] == "0":
      continue
    
    for xy in xyss[j]:
      x, y = xy[0], xy[1]
      if b[x - 1] != str(y):
        ok = False
        continue
  
  if ok == True:
    num = sum([int(s) for s in list(b)])
    if cnt < num:
      cnt = num
  
print(cnt)

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):
n=int(input())
testimony_list=[[[-1,0] for _ in range(n-1)] for i in range(n)]
for i in range(n):
	a=int(input())
	for j in range(a):
		x,y=map(int,input().split())
		testimony_list[i][j][0]=x-1
		testimony_list[i][j][1]=y

ans=0
for i in range(2**n):
	kind_l=[0 for _ in range(n)]
	for j in range(n):
		if ((i>>j) & 1):
			kind_l[j]=1
	flag=True
	for k in range(n):
		if kind_l[k]:
			for m in range(n-1):
				subject=testimony_list[k][m][0]
				judge=testimony_list[k][m][1]
				if subject==-1:continue
				if kind_l[subject]!=judge:
					flag=False
	if flag:
		ans=max(ans,sum(kind_l))
print(ans)

Solution (Python):
g = [[-1] * 15 for _ in range(15)]
n = int(input())
for i in range(n):
    m = int(input())
    for j in range(m):
        a, x = map(int, input().split())
        a -= 1
        g[i][a] = x
def count_ones_by_minus(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count
ans = 0
for i in range(1 << n):
    d = [0] * n
    for j in range(n):
        if i >> j & 1:
            d[j] = 1
    ok = True
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, count_ones_by_minus(i))
print(ans)

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

tf = [0]*n
ans = 0
for i in range(2**n):
  for j in range(n):
    if (i >> j) & 1:
      tf[j] = 1
    else:
      tf[j] = 0
  b = 1
  for k in range(n):
    if tf[k] == 1:
      for l in range(a[k]):
        if tf[xy[k][l][0]-1] != xy[k][l][1]:
          b = 0
          break
  if b == 1 and sum(tf) > ans:
    ans = sum(tf)

print(ans)

Solution (Python):

G = [[-1] * 15 for _ in range(15)]
N = int(input())
for i in range(N):
    Ai = int(input())
    for _ in range(Ai):
        x, y = map(int, input().split())
        G[i][x - 1] = y;
        
ans = 0
for i in range(1<<N):
    d = [0] * N
    for j in range(N):
        if (i>>j&1):  
            d[j] = 1  
            
    ok = True
    for j in range(N):
        if d[j] == 1:
            for k in range(N):
                if G[j][k] == -1:
                    continue
                if G[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, bin(i).count('1'))
    
print(ans)

Solution (Python):
import sys

def kensho(x,tlist):
    for lis in tlist:
        if((x>>(lis[1]-1)) & 1 == lis[2]):
            pass
        else:
            return -1

    return bin(x).count('1')


def main():
    N = int(input())
    xy=[]
    ans=0

    for i in range(1,N+1):
        An= int(input())
        for j in range(0,An):
            x, y = map(int, input().split())
            xy.append([i,x,y])

    cnt = N

    tlist=[]
    for x in range (2 ** cnt):
        for y in range(cnt):
            if((x>>y) & 1):
                for z in xy:
                    if(z[0]==y+1):
                        tlist.append(z)

        anstack = kensho(x,tlist)
        if(ans<anstack):
            ans=anstack

        del tlist[:]

    print(ans)

main()

Solution (Python):

    

test = ""

"""
3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0
ans 0
"""

"""
3
1
2 1
1
1 1
1
2 0
ans 2
"""

"""
2
1
2 0
1
1 0
ans 1
"""

test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()


n = int(input2())
a = [None] * (n+1)
for i in range(1, n+1):
    ai = int(input2())
    a[i] = [tuple(map(int, input2().split())) for i in range(ai)]
    

def bitsearch(bit, *, start=0):
    end = 2 ** bit
    len0 = len(format(end, "b"))
    return [format(i, "b").zfill(len0) for i in range(start, end)] 


cand = [0]
for b in bitsearch(n):
    lie, i = 0, 1
    while (not lie) and i < n+1:
        for c in a[i]:
            if int(b[i]) and c[1] ^ int(b[c[0]]):
                lie += 1            
        i += 1
        
    if not lie:
        cand.append(b.count("1"))
        
print(max(cand))

Solution (Python):
import itertools
import copy

n = int(input())
indexes = [_ for _ in range(1, n+1)]

def ifCorrect(data, fakes):
    answer_sheet = [-1 for i in range(n+1)]
    for i in fakes:
        answer_sheet[i] = 0

    
    for i in range(len(data)):
        for j in data[i]:
            if not i in fakes:
                if answer_sheet[j[0]] == -1:
                    if j[1] == 0 and not j[0] in fakes:
                        return False
                    else:
                        answer_sheet[j[0]] = j[1]
                elif not answer_sheet[j[0]] == j[1]:
                    return False
                    
    return True

data = [[] for _ in range(n+1)]
for i in range(n):
    id = int(input())
    for _ in range(id):
        x, y = map(int, input().split(" "))
        data[i+1].append([x,y])

fakePersonCount = 0
flag = True
while fakePersonCount <= n and flag:
    comb = itertools.combinations(indexes, fakePersonCount)
    for fakePeople in comb:
        if ifCorrect(data, fakePeople):
            print(n - fakePersonCount)
            flag = False
            break
    fakePersonCount += 1

if flag:
    print(0)

Solution (Python):
import itertools
import copy

n = int(input())
indexes = [_ for _ in range(1, n+1)]

def ifCorrect(data, fakes):
    answer_sheet = [1 for i in range(n+1)]
    answer_sheet[0] = -1
    for i in fakes:
        answer_sheet[i] = 0

    
    for i in range(len(data)):
        for j in data[i]:
            if not i in fakes and not answer_sheet[j[0]] == j[1]:
                return False
                    
    return True

data = [[] for _ in range(n+1)]
for i in range(n):
    id = int(input())
    for _ in range(id):
        x, y = map(int, input().split(" "))
        data[i+1].append([x,y])

fakePersonCount = 0
flag = True
while fakePersonCount <= n and flag:
    comb = itertools.combinations(indexes, fakePersonCount)
    for fakePeople in comb:
        if ifCorrect(data, fakePeople):
            print(n - fakePersonCount)
            flag = False
            break
    fakePersonCount += 1

if flag:
    print(0)

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

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

import itertools
assumptions = list(itertools.product((0, 1), repeat = N))

answers = []
for i in assumptions:
    assumptions2 = []
    for j in range(N):
        assumptions2.append((j + 1, i[j]))
        if i[j] == 1:
            for k in testimonies_all[j]:
                assumptions2.append(k)
    assumptions2.sort()
    count = 0
    for j in range(len(assumptions2) - 1):
        if assumptions2[j][0] == assumptions2[j + 1][0] and assumptions2[j][1] != assumptions2[j + 1][1]:
            count += 1
            break
    if count == 0:
        answers.append(sum(i))

print(max(answers))

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
S = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    temp = []
    for _ in range(A):
        temp.append([str(x) for x in input().split()])
        S[i] = temp
ans = 0
for i in range(2 ** N - 1, -1,-1):
    biti = list(bin(i)[2:].zfill(N))
    flag = 0
    for j in range(N):
        if biti[j] == "1":
            for k in S[j]:
                if biti[int(k[0])-1] != k[1]:
                    flag = 1
                    break
        if flag:
            break
    if not flag:    
        biti = np.array(biti)
        ans = max(ans, np.count_nonzero(biti == "1"))
print(ans)

Solution (Python):
class Info:
    def __init__(self, A):
        self.A = A
        self.info = [[0] * 2 for i in range(A)]
        for i in range(A):
            x, y = map(int, input().split())
            self.info[i][0] = x - 1
            self.info[i][1] = y

def solve():
    N = int(input())
    infos = []
    for i in range(N):
        A = int(input())
        infos.append(Info(A))
    
    mx = 0
    for i in range(2 ** N):
        isKind = []
        for j in range(N):
            if (i >> j) & 1:
                isKind.append(1)
            else:
                isKind.append(0)
        
        isConsistent = True
        p = 0
        for info in infos:
            for j in range(info.A):
                if isKind[p]==1 and isKind[info.info[j][0]] != info.info[j][1]:
                    isConsistent = False
            p += 1
        
        if isConsistent:
            Nkind = sum(isKind)
            mx  = max(mx, Nkind)


    print(mx)


if __name__ == '__main__':
    solve()

Solution (Python):

import sys
INF = float("inf")


def main():
    N = int(input())
    A = [None]*N
    X = [None]*N
    Y = [None]*N
    for i in range(N):
        A[i] = int(input())
        x, y = [None]*A[i], [None]*A[i]
        for j in range(A[i]):
            x_, y_ = map(int, input().split())
            x[j] = x_
            y[j] = y_
        X[i] = x
        Y[i] = y

    m = 0
    for table in range(2**N):
        
        flag = True
        for i in range(N):
            
            if table & (1 << i):
                for j in range(A[i]):
                    if not ((table >> (X[i][j]-1)) & 1) == Y[i][j]:
                        flag = False
                        break
            if flag == False:
                break
        if flag == True:
            
            tot = 0
            for i in range(N):
                tot += (table >> i) & 1
            m = max(tot, m)

    print(m)
    pass


if __name__ == '__main__':
    main()

Solution (Python):



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])

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

    flag = True
    
    for idx, j in enumerate(bit):
        if not flag:
            break
        if j == 1:
            for k in [x for x in info if x[0] == idx]:
                
                if bit[k[1]] != k[2]:
                    flag = False
    if flag:
        ans = max(ans, sum(bit))
    
print(ans)

Solution (Python):
import itertools


def main():
    N = int(input())
    remarks = []
    for i in range(N):
        A = int(input())
        remark = []
        for j in range(A):
            x, y = [int(i) for i in input().split()]
            remark.append((x-1, y))
        remarks.append(remark)

    ans = 0
    for is_honest in itertools.product([1, 0], repeat=N):
        
        ok = True
        for i, h in enumerate(is_honest):
            if not ok:
                break
            
            if h == 0:
                continue
            
            
            for one_remark in remarks[i]:
                if is_honest[one_remark[0]] != one_remark[1]:
                    ok = False
                    break
        if ok:
            ans = max(ans, sum(is_honest))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def popcnt(n):
    return bin(n).count("1")

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



ans = 0
for i in range(2**N) :
    d = [0 for _ in range(N)]
    for j in range(N) :
        if((i >> j) & 1) :
            d[j] = 1
    flg = True
    for j in range(N) :
        if(d[j]) :
            for k in range(N) :
                if(evi[j][k] == -1): continue
                if(evi[j][k] != d[k]): flg=False
    if(flg) :
        ans = max(ans, popcnt(i))
        
print(ans)

Solution (Python):
N=int(input())
llie=[[] for i in range(N)]
ltrue=[[] for i in range(N)]
for i in range(N):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            llie[i].append(x)
        else:
            ltrue[i].append(x)
ans=0
for i in range(2**N):
    dlie={}
    dtrue={}
    tmpsum=0
    f=0
    for j in range(N):
        if i&1:
            if j+1 in dlie:
                f=1
                break
            else:
                for x in llie[j]:
                    if x in dtrue:
                        f=1
                        break
                    dlie[x]=1
                for x in ltrue[j]:
                    if x in dlie:
                        f=1
                        break
                    dtrue[x]=1
                if f==0:
                    tmpsum+=1
                    dtrue[j+1]=1
                else:
                    break
        else:
            if j+1 in dtrue:
                f=1
                break
            dlie[j+1]=1
        i>>=1
    if f==0:
        ans=max(ans,tmpsum)
print(ans)