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())
A_list = []
XY_list = []
for i in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for i in range(a)]
    A_list.append(a)
    XY_list.append(xy)

result = 0

for i in range(2 ** N):
    bit = str(format(i, 'b')).zfill(N)
    flag = 0
    for j in range(N):
        if bit[j] == '1':
            for k in range(A_list[j]):
                man = XY_list[j][k][0]
                judge = XY_list[j][k][1]
                if int(bit[man - 1]) != judge:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = 0
        for j in range(N):
            tmp += int(bit[j])
        if tmp > result:
            result = tmp
print(result)

Solution (Python):
N=int(input())
A=[]
g=[[-1]*(N) for i in range(N)]

for i in range(N):
    a=int(input())
    A.append(a)
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        g[i][x]=y
"""
num=[]
for i in range(2 **N):
  chars = list(f"{i:0{N}b}")
  chars=list(map(int,chars))
  num.append(chars)
"""
num=[]
for i in range(2**N):
    x=[]
    for j in range(N):
        if i>>j & 1:
            x.append(1)
        else:
            x.append(0)
    num.append(x)

ans=[]
for x in num:
    ok = True
    for k in range(N):
        if x[k]:
            for j in range(N):
                if g[k][j]==-1:
                    continue
                elif g[k][j]!=x[j]:
                    ok=False
    if ok:
        ans.append(x.count(1))
print(max(ans))

Solution (Python):
N=int(input())
A=[]
g=[[-1]*(N) for i in range(N)]

for i in range(N):
    a=int(input())
    A.append(a)
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        g[i][x]=y
""""
num=[]
for i in range(2 **N):
  chars = list(f"{i:0{N}b}")
  chars=list(map(int,chars))
  num.append(chars)
"""
num=[]
for i in range(2**N):
    x=[]
    for j in range(N):
        if i>>j & 1:
            x.append(1)
        else:
            x.append(0)
    num.append(x)

ans=[]
for x in num:
    ok = True
    for k in range(N):
        if x[k]:
            for j in range(N):
                if g[k][j]==-1:
                    continue
                elif g[k][j]!=x[j]:
                    ok=False
    if ok:
        ans.append(x.count(1))
print(max(ans))

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

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

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

ans=0
for i in range(2**n):
    s=bin(i)[2:].zfill(n)  
    f=True
    for j,k in enumerate(lst):  
        for x,y in k:   
            if s[x-1]!=str(y) and s[j]=='1':    
                f=False                                
    if f:                                   
        ans=max(ans,s.count('1'))   
print(ans)

Solution (Python):
n = int(input())
A = [[]]*n

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

mx = 0
for i in range(2**n):
  B = [[0]*3 for _ in range(n)]
  uso = 0
  men_cnt = 0
  for j in range(n):
    if i>>j&1:
      men_cnt += 1
      B[j][2] = 1
      for k in range(len(A[j])):
        x, y = A[j][k]
        B[x][y] = 1
  for i in range(n):
    if (B[i][0] and B[i][1]) or (B[i][1] and B[i][2]==0) or (B[i][0] and B[i][2]):
      uso = 1
  if uso==0:
    if men_cnt>mx:
      mx = men_cnt
   
      
print(mx)

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    all_A = []
    for _ in range(N):
        a = int(input())
        A = []
        for _ in range(a):
            x, y = map(int, input().split())
            x -= 1
            A.append((x, y))
        all_A.append(A)

    res = 0
    for i in range(2 ** N):
        honest = []
        for j in range(N):
            if ((i >> j) & 1):
                honest.append(j)
        if len(honest) == 0:
            continue
        feasible = True
        for h in honest:
            for x, y in all_A[h]:
                if y == 1:
                    if x not in honest:
                        feasible = False
                        break
                else:
                    if x in honest:
                        feasible = False
                        break
        if feasible:
            res = max(res, len(honest))

    print(res)


if __name__ == '__main__':
    main()

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

ans = 0
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1 
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))

print(ans)

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if i >> j & 1 == 1:  
            for k in range(a[j]):
                if xy[j][k][1] == 1 and i >> (xy[j][k][0]-1) & 1 != 1:
                    flag = False
                    break
                elif xy[j][k][1] == 0 and i >> (xy[j][k][0]-1) & 1 != 0:
                    flag = False
                    break
            else:
                continue
            break
    if flag and ans < str(bin(i)).count("1"):
        ans = str(bin(i)).count("1")


print(ans)

Solution (Python):


def solve():
    N = int(input())
    testimonies = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        testimonies.append(XYs)

    
    ans = 0
    for bit in range(2**N):
        is_continue = False
        total = 0
        
        for i in range(N):
            if bit>>i&1:
                
                total += 1
                for testimony in testimonies[i]:
                    x, y = testimony
                    if bit>>x&1 != y:
                        
                        is_continue = True
                        break
            if is_continue:
                break
        if is_continue:
            continue
        ans = max(ans, total)

    print(ans)



if __name__ == "__main__":
    solve()

Solution (Python):
def check(pat):
  honest = [1 if i in pat else 0 for i in range(N)]
  li = pat + [i for i in range(N) if i not in pat]
    
  for i in li:
    if honest[i] == 1:
      n = len(x[i])
      for j in range(n):
        y = x[i][j]
        if honest[y[0]] != y[1]:
          return -1
    
  return len(pat)

N = int(input())
x = [0]*N
for i in range(N):
  A = int(input())
  x[i] = []
  for j in range(A):
    y1,y2 = map(int,input().split())
    x[i].append((y1-1,y2))
max_honest = 0
l = [i for i in range(N)]
n = len(l)
for i in range(2 ** N):
    pat = []
    for j in range(n):  
        if ((i >> j) & 1):  
            pat.append(l[j])  
    max_honest = max(max_honest,check(pat))
print(max_honest)

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
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Solution (Python):
import itertools

n = int(input())
xy_map = []
for i in range(n):
    xy_map.append([9]*n)

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xj, yj = [int(_) for _ in input().split()]
        xy_map[i][xj-1] = yj

def judge_ox(i, j, set_01):
    if set_01[j] == '1':
        if 0 in [xy_map[i][j], xy_map[j][i]]:
            return False
        else:
            return True
    else:
        if xy_map[i][j] in [0, 9]:
            return True
        else:
            return False

res = 0
for set_01 in itertools.product('01', repeat=n):
    flag = 1
    for i in range(n):
        if set_01[i] != '1':
            continue
        for j in range(n):
            if i == j:
                continue
            if not judge_ox(i, j, set_01):
                flag = 0
                break
    if flag:
        res = max(res, sum([int(x) for x in set_01]))
print(res)

Solution (Python):
import itertools

n = int(input())
an_list = []
xy_list = []
for _ in range(n):
  an_list.append(int(input()))
  xy_list.append([list(map(int, input().split())) for __ in range(an_list[-1])])




max_honest = 0

h_or_u = [0, 1]
for i in itertools.product(h_or_u, repeat=n):
  honest = []
  unkind = []
  for j in range(n):
    if i[j] == 1:
      honest.append(j+1)
      for k in range(an_list[j]):
        if xy_list[j][k][1] == 1:
          honest.append(xy_list[j][k][0])
        else:
          unkind.append(xy_list[j][k][0])
    else:
      unkind.append(j+1)
  b = 0
  for l in set(honest):
    if l in unkind:
      b += 1
  if b == 0:
    max_honest = i.count(1)
  
  
    

print(max_honest)

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

ans=0
for i in range(2**n):
    flag=0
    for j in range(n):
        if (i>>j)&1:
            for k in l[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):
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: 
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag = 1
                    break
    if flag == 0:  
    
        honest = max(honest, bin(i)[2:].count('1'))  
print(honest)

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

















from collections import deque
N = int(input())
xy = [[0,0]]*N
A = [0]*N
for i in range(N):
    a = int(input())
    A[i] = a
    xy[i] = [list(map(int,input().split())) for _ in range(a)]
Max = 0
for i in range(2**N):
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): 
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    cc = 0
    for i in range(N):
        c = 0
        if bitlist[i] == 1:
            for k in range(A[i]):
                if xy[i][k][1] == 1:
                    if bitlist[xy[i][k][0]-1] == 0:
                        c = 1
                        break
                else:
                    if bitlist[xy[i][k][0]-1] == 1:
                        c = 1
                        break
        if c == 1:
            cc = 1
            break
    if cc == 0:
        ss = 0
        for jj in bitlist:
            ss += jj
        Max = max(Max,ss)
print(Max)

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

def main():
    n = int(input())
    
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) 

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


    from copy import deepcopy
    max_sum = 0 
    for i in li: 
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): 
            if i[k] == 0: 
                continue
            else: 
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: 
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

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

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

















from collections import deque
N = int(input())
xy = [[0,0]]*N
A = [0]*N
for i in range(N):
    a = int(input())
    A[i] = a
    xy[i] = [list(map(int,input().split())) for _ in range(a)]
Max = 0
for i in range(2**N):
    bitlist = deque()
    for j in range(N):
        if ((i >> j) & 1): 
            bitlist.appendleft(1)
        else:
          	bitlist.appendleft(0)
    bitlist = list(bitlist)
    cc = 0
    for i in range(N):
        c = 0
        if bitlist[i] == 1:
            for k in range(A[i]):
                if xy[i][k][1] == 1:
                    if bitlist[xy[i][k][0]-1] == 0:
                        c = 1
                        break
                else:
                    if bitlist[xy[i][k][0]-1] == 1:
                        c = 1
                        break
        if c == 1:
            cc = 1
            break
    if cc == 0:
        ss = 0
        for jj in bitlist:
            ss += jj
        Max = max(Max,ss)
print(Max)

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

As = [[] for _ in range(N)]

for i in range(N):
    n = int(input())
    for j in range(n):
        person, state = map(int, input().split())
        As[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 As[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())

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())
xy = []
for _ in range(n):
    i = int(input())
    ls = []
    for _ in range(i):
        ls.append(list(map(int, input().split())))
    xy.append(ls)

ans = 0
for i in range(2**n):
    _true = [0]*n
    bl = True
    cnt = 0
    for j in range(n):
        if (i >> j) & 1:
            _true[j] = 1
    for j in range(n):
        if _true[j] == 1:
            for x, y in xy[j]:
                if _true[x-1] != y:
                    bl = False
                    break
    if bl:
        cnt = sum(_true)
    ans = max(ans, cnt)

print(ans)

Solution (Python):
from collections import  deque
import sys
import bisect

import itertools
from queue import deque


INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))



N = inp()
A = [0 for _ in range(N)]
xx = [[] for _ in range(N)]
yy = [[] for _ in range(N)]

for i in range(N):
    A[i] = inp()
    for _ in range(A[i]):
        x, y = inp_list()
        xx[i].append(x)
        yy[i].append(y)





ans = 0
for bit in range(1 << N):
    """
        例： bit == 10 のとき、2進数では 001010 
            右から人 1, 2, ..., 6 と対応させる。
    """
    is_inconsistent = False
    
    is_honest = [(bit >> i) & 1 for i in range(N)]
    for i in range(N):
        if not is_honest[i]: continue
        for (x, y) in zip(xx[i], yy[i]):
            if is_honest[x - 1] != y:
                is_inconsistent = True 
    if not is_inconsistent:
        ans = max(ans, sum(is_honest))
print(ans)

Solution (Python):
from collections import  deque
import sys
import bisect

import itertools
from queue import deque


INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))



N = inp()
A = [0 for _ in range(N)]
xx = [[] for _ in range(N)]
yy = [[] for _ in range(N)]

for i in range(N):
    A[i] = inp()
    for _ in range(A[i]):
        x, y = inp_list()
        xx[i].append(x)
        yy[i].append(y)





ans = 0
for bit in range(1 << N):
    """
        例： bit == 10 のとき、2進数では 001010 
            右から人 1, 2, ..., 6 と対応させる。
    """
    is_inconsistent = False
    
    is_honest = [(bit >> i) & 1 for i in range(N)]
    for i in range(N):
        if not is_honest[i]: continue
        for (x, y) in zip(xx[i], yy[i]):
            if is_honest[x - 1] != y:
                is_inconsistent = True 
    if not is_inconsistent:
        ans = max(ans, sum(is_honest))
print(ans)

Solution (Python):
from collections import  deque
import sys
import bisect

import itertools
from queue import deque


INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))



N = inp()
A = [0 for _ in range(N)]
xx = [[] for _ in range(N)]
yy = [[] for _ in range(N)]

for i in range(N):
    A[i] = inp()
    for _ in range(A[i]):
        x, y = inp_list()
        xx[i].append(x)
        yy[i].append(y)




honest_count = 0

ans = 0
for bit in range(1 << N):
    """
        例： bit == 10 のとき、2進数では 001010 
            右から人 1, 2, ..., 6 と対応させる。
    """
    ok = True
    is_honest = [(bit >> i) & 1 for i in range(N)] 
    for i in range(N):
        if not is_honest[i]: continue
        for (x, y) in zip(xx[i], yy[i]):
            if is_honest[x - 1] != y:
                ok = False
    if ok:
        ans = max(ans, sum(is_honest))
print(ans)

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

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

l = []
ans = 0
for i in range(2**n):
	l = []
	torf = [0 for _ in range(n)]
	
	for j in range(n):
			if i & (1<<j):
				torf[j] = 1
				l.append(j)
	flag = False
	for j in range(n):
		
		if torf[j] == 1:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] != xy[j][k][1]:
					flag = True
					break
		
		"""
		else:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] == xy[j][k][1]:
					flag = True
					break
		"""
		if flag:
			break
	if not flag:
		ans = max(ans,len(l))

print(ans)

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

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

Solution (Python):
n = int(input())
a = []
xy = []

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

ans = 0
for i in range(2**n):
    
    _true = [0]*n
    bl = True
    for j in range(n):
        if (i >> j) & 1:
            _true[j] = 1
    for j in range(n):
        
        if _true[j] == 1:
            
            for x, y in xy[j]:
                if _true[x-1] != y:
                    bl = False
                    break
    if bl:
        ans = max(ans, sum(_true))

print(ans)

Solution (Python):

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




ans = 0
for i in range(2**N):
    s = str(bin(i))[2:].zfill(N)
    flag = True
    d = [k for k in range(len(s)) if s[k]=='1']
    honest = [1 if s[k]=='1' else 0 for k in range(len(s))]
    for j in d:
        for k in range(A[j]):
            if honest[xy[j][k][0]-1]^xy[j][k][1]==1:
                flag = False
                break
            else:
                continue
        if not flag:
            break
    if flag:
        ans = max(ans,len(d))
print(ans)

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

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

max_res = 0
for i in range(2 ** n):           
    ok_flg = True
    bin_i = format(i, "015b")[::-1] 
                                    
    for j in range(n):
        for x, y in xy_arr[j]: 
            if bin_i[j] == "1" and y != int(bin_i[x - 1]):
                ok_flg = False
                break
        else:
            continue
        break
        
    if ok_flg:
        res = sum(int(x) for x in bin_i)
        max_res = max(max_res, res)
        
print(max_res)

Solution (Python):
import sys,itertools as it
f=sys.stdin.readline
n=int(f())
ll=[]
for i in range(n):
  a=int(f())
  for _ in range(a):
    x,y=map(int,f().split())
    ll+=[(i,x-1,y)]
c=0
for p in it.product([0,1],repeat=n):
  if all(p[i]<1 or p[x]==y for i,x,y in ll):
    c=max(c,sum(p))
print(c)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in range(2**n):
  if all(p>>i&1<1 or p>>x&1==y for i,x,y in ll):
    c=max(c,sum(p>>i&1 for i in range(n)))
print(c)

Solution (Python):
import sys,itertools as it
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in it.product([0,1],repeat=n):
  b=1
  for i,x,y in ll:
    if p[i] and p[x]!=y:
      b=0
      break
  if b: c=max(c,sum(p))
print(c)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in range(2**n):
  b=1
  for i,x,y in ll:
    if p>>i&1 and p>>x&1!=y:
      b=0
      break
  if b: c=max(c,sum(p>>i&1 for i in range(n)))
print(c)

Solution (Python):
N = int(input())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        XY[i].append((x-1,y))
ans = 0
for bit in range(1<<N):
    cnt = bin(bit).count('1')
    ok = True
    for i in range(N):
        if bit&(1<<i):
            for x,y in XY[i]:
                if y == 1:
                    if not bit&(1<<x):
                        ok = False
                        break
                else:
                    if bit&(1<<x):
                        ok = False
                        break
            if not ok:
                break
    if ok:
        ans = max(ans, cnt)
print(ans)

Solution (Python):
N = int(input())
A = [0]*N
X = []
Y = []
for i in range(N):
    A[i] = int(input())
    X.append([])
    Y.append([])
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i].append(x-1)
        Y[i].append(y)
ans = 0
for bit in range(1<<N):
    honest = 0
    ok = True
    for i in range(N):
        if bit&(1<<i):
            honest += 1
            for j in range(A[i]):
                if Y[i][j] == 0:
                    if bit&(1<<X[i][j]):
                        ok = False
                        break
                else:
                    if not bit&(1<<X[i][j]):
                        ok = False
                        break
            if not ok:
                break
    if ok:
        ans = max(ans, honest)
print(ans)

Solution (Python):


from collections import defaultdict
import itertools

n = int(input())
m = [[]for i in range(n)]

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


ans=0
for i in itertools.product([0,1],repeat=n):
    k=1
    for j in itertools.compress([ii for ii in range(n)],i):
        for x,y in m[j]:
            if i[x] !=-1 and i[x]!=y:
                k=0
                break
        if not k:
            break
    
    if k:
        ans=max(ans,sum(i))

print(ans)

Solution (Python):
N = int(input())
A = [0]*N
X = []
Y = []
for i in range(N):
    A[i] = int(input())
    X.append([])
    Y.append([])
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i].append(x-1)
        Y[i].append(y)
ans = 0
for bit in range(1<<N):
    honest = 0
    ok = True
    for i in range(N):
        if bit&(1<<i):
            honest += 1
            for j in range(A[i]):
                if Y[i][j] == 0:
                    if bit&(1<<X[i][j]):
                        ok = False
                else:
                    if not bit&(1<<X[i][j]):
                        ok = False
    if ok:
        ans = max(ans, honest)
print(ans)

Solution (Python):
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


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

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = judge[j]
        if not honest:
            continue
        for x, y in comment[j]:
            if honest:
                if judge[x] == y:
                    continue
                else:
                    flag = False
                    break
    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)

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

def main():
    n = int(input())
    
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) 

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


    from copy import deepcopy
    max_sum = 0 
    for i in li: 
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): 
            if i[k] == 0: 
                continue
            else: 
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: 
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

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

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

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


def check(i):
    honests = []
    for j in range(n):
        if (i >> j) & 1:
            honests.append(j)

    for j in honests:
        for k in range(len(testimony[j])):
            if testimony[j][k] == 1 and k not in honests:
                return False
            if testimony[j][k] == 0 and k in honests:
                return False

    return True


ans = 0
for i in range(1, 2 << (n-1)):
    if check(i):
        count = 0
        for j in range(n):
            if (i >> j) & 1:
                count += 1
        ans = max(ans, count)

print(ans)

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

ans = 0
for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i>>j) & 1 == 1 and flag == 0:
            for k,v in word[j]:
                if i>>(k-1) & 1 != v:
                    flag = 1
                    break

    if flag == 0:
        ans = max(ans,bin(i).count('1'))

print(ans)

Solution (Python):
n = int(input())
opinion = [{} for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        opinion[i][x-1] = y
ans = 0
for i in range(2**n):
    honest = [0]*n
    j = 0
    while i > 0:
        honest[j] = i&1
        j += 1
        i = i >> 1
    flag = 1
    for j in range(n):
        if honest[j]:
            for x,y in opinion[j].items():
                if honest[x] != y:
                    flag = 0
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

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