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

L = [0] * N

for i in range(N):
  A = int(input())
  if A == 0:
    L[i] = []
  else:
    L[i] = [list(map(int, input().split()))]
  for j in range(1,A):
    L[i].append(list(map(int, input().split())))
    


ans = 0
for i in range(2**N):
  pat = str(format(i, '0' + str(N) + 'b'))
  flg = True
  
  for j in range(N):
    if pat[j] == "1": 
      for rule in L[j]:
        if pat[rule[0]-1] == "0" and rule[1] == 1:
          flg = False
          break
        if pat[rule[0]-1] == "1" and rule[1] == 0:
          flg = False
          break
  
  if flg:
    work = 0
    for ch in pat:
      if ch == "1":
        work += 1
    
    ans = max(ans, work)
    
print(ans)

Solution (Python):
n = int(input())
a =[]
for _ in range(n):
    m = int(input())
    a.append([list(map(int, input().split())) for _ in range(m)])
c = 0
for i in range(1 << n):
    Flag = True
    for j in range(n):
        if ((i>>j)&1) == 1:
            for k in a[j]:
                if i>>(k[0]-1)&1 != k[1]:
                    Flag = False
        if Flag == False:break
    else:
        honest = sum([i>>j&1 for j in range(n)])
        c = max(c,honest)
print(c)

Solution (Python):


graph = [[-1 for _ in range(15)] for _ in range(15)]

def main():
    n = int(input())
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            graph[i][x-1] = y
            
    ans = 0
    for i in range(1<<15):
        h = [0]*15
        for k in range(n):
            if (i >> k) & 1:
                h[k] = 1

        f = True
        for i in range(15):
            if h[i] == 1:
                for j in range(n):
                    if graph[i][j] == -1:
                        continue
                    if graph[i][j] != h[j]:
                        f = False

        if f:
            ans = max(ans, sum(h))

    print(ans)
main()

Solution (Python):
from collections import*
n=int(input())

d=defaultdict(list)
for i in range(n):
    a=int(input())
    for j in range(a):
        d[i+1].append(list(map(int,input().split())))
        


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

    f=0
    for p,b in enumerate([i>>j&1for j in range(n)]):
        if b:
            for s,t in d[p+1]:
                if bol[s-1]!=t:
                    f=1
    if f==0:

        ans.append(sum(bol))
print(max(ans))

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

comments = []
for i in range(person_num):
    comments_num = int(input())
    comment = []
    for j in range(comments_num):
        comment.append(list(map(int, input().split())))
    comments.append(comment)

honest_max = 0
for i in range(2 ** person_num):
    check = list(bin(i)[2:].zfill(person_num))
    for j in range(person_num):
        if check[j] == "1":
            for comment in comments[j]:
                if check[comment[0]-1] != str(comment[1]):
                    break
            else:
                continue
            
            break
    else:
        if honest_max < check.count("1"):
            honest_max = check.count("1")

print(honest_max)

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

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

ans = 0

for p in itertools.product([1,0], repeat=n):
  ok = 1
  for l in ll:
    if p[l[0]] == 1 and p[l[1]] != l[2]:
      ok = 0
      break
  if ok:
    ans = max(ans, sum(p))

print(ans)

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

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

from itertools import product

lb = [''.join(b) for b in product('01', repeat=n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

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

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

lb = []
for i in range(2**n):
  lb += [str(bin(i))[2:].zfill(n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

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

lb = []
for i in range(2**n):
  lb += [str(bin(i))[2:].zfill(n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

Solution (Python):
def main():
    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))

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

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
testimony_table = [[] for _ in range(n)]

for i_witness in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        testimony_table[i_witness].append((xij-1,yij))

ans = 0
for i in range(2**n):
    isConflict = False

    for j_witness in range(n): 
        if (i >> j_witness) & 1 == 0: 
            continue


        for x_suspect, y_testimony in testimony_table[j_witness]:
            if ((i >> x_suspect) & 1) != y_testimony:
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))

print(ans)

Solution (Python):
def dudge(k):
    for i in range(n):
        p = (k >> i) % 2
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))

result = 0
for k in range(1 << n):
    if dudge(k):
        l = [i for i in range(n) if (k >> i) % 2 == 1]
        cnt = 0
        result = max(result, len(l))

print(result)

Solution (Python):
def dudge(k):
    for i in reversed(range(n)):
        p = (k >> i) % 2
        
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))



result = 0
for k in reversed(range(1 << n)):
    

    if dudge(k):
        
        l = [i for i in range(n) if (k >> i) % 2 == 1]
        cnt = 0
        
        
        
        result = max(result, len(l))
        

print(result)

Solution (Python):
def dudge(k):
    for i in reversed(range(n)):
        p = (k >> i) % 2
        
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))



result = 0
for k in reversed(range(1 << n)):
    

    if dudge(k):
        
        
        cnt = 0
        for i in range(n):
            if (k >> i) % 2 == 1: cnt += 1
        
        
        result = max(result, cnt)

print(result)

Solution (Python):
from itertools import product
N = int(input())

An = []
Xn, Yn = [], []

for i in range(N):
    An.append(int(input()))
    Xn.append([])
    Yn.append([])
    for j in range(An[i]):
        x, y = map(int, input().split())
        Xn[i].append(x)
        Yn[i].append(y)

ans = 0
for prod in product("01", repeat=N):
    
    bits = list(map(int, prod))
    flag = True

    
    for i in range(N):
        
        if bits[i] != 1:
            continue

        
        for j in range(An[i]):
            
            if Yn[i][j] == 1 and bits[Xn[i][j]-1] == 0:
                flag = False

            
            elif Yn[i][j] == 0 and bits[Xn[i][j]-1] == 1:
                flag = False

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

print(ans)

Solution (Python):


N=int(input())


say=[]
for _ in range(N):
    temp=[-1]*N
    A=int(input())
    for __ in range(A):
        x,y=map(int,input().split())
        temp[x-1]=y
    say.append(temp)



ans=0
for i in range(2**N):
    katei=list(str(bin(i))[2:])
    katei=list(map(int,katei))
    katei=[0]*(N-len(katei))+katei
    
    
    flag=True
    for num in range(N):
        if katei[num]==1:
            for num2 in range(N):
                if (say[num][num2]==0 and katei[num2]==1) or (say[num][num2]==1 and katei[num2]==0):
                    flag=False
    if flag:
        ans=max(ans,sum(katei))
    
print(ans)

Solution (Python):
import itertools

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



ans = []
for e in itertools.product("01",repeat=N):
    
    B = [int(a) for a in e]

    flag = True
    
    
    
    
    
    for i in range(N):
        
        if B[i] == 1:
            
            for j in range(A[i]):
                
                if y[i][j] == 1:
                    
                    if B[x[i][j]] == 0: flag = False
                else:
                    
                    if B[x[i][j]] == 1: flag = False

    if flag:
        
        ans.append([e == 1 for e in B].count(True))


print(max(ans))

Solution (Python):
N = int(input())
all = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        all[i].append([x, y])

max_val = 0
for i in range(2 ** N):
    check = True
    for j in range(N):
        if i >> j & 1 == 1:
            for x, y in all[j]:
                if i >> (x-1) & 1 != y:
                    check = False
                    break
    if check == True:
        max_val = max(max_val, bin(i)[2:].count('1'))
print(max_val)

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):
def main():
    N = int(input())

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

    ans = 0

    for i in range(1, 2**N):
        tmp = 0
        flag = True
        for j in range(N):
            if (i>>j)&1 == 1:
                tmp += 1
                for d in data[j]:
                    if (i>>d[0])&1 != d[1]:
                        flag = False
        if (flag) & (tmp > ans):
            ans = tmp
    print(ans)

    return 0
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [0] * N
X = [[] for _ in range(N)]
for i in range(N):
  A[i] = int(input())
  for j in range(A[i]):
    X[i].append(list(map(int, input().split())))
Truth = 2 ** N
ans = 0
while(bin(Truth) != bin(2 ** (N + 1))):
  for i in range(N):
    if(bin(Truth)[i+3] == "1"):
      for j in range(A[i]):
        if(int(bin(Truth)[X[i][j][0] + 2]) != X[i][j][1]):
          break
      else:
        continue
      Truth += 1
      break
  else:
    ans = sum(list(map(int,list(bin(Truth)[3:]))))
    Truth += 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):
from itertools import product
 
 
def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)
 
    assumptions = product([0, 1], repeat=N)
    assumptions = sorted(assumptions, key=lambda x: x.count(0))
    for assumption in assumptions:
        for i in range(N):
            if assumption[i]:
                for testimony in testimonies[i]:
                    if not assumption[testimony[0] - 1] == testimony[1]:
                        break
                else:
                    continue
                break
        else:
            print(assumption.count(1))
            break
        continue
 
 
if __name__ == '__main__':
    main()
from itertools import product


def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)

Solution (Python):

def dfs(i,evid,honest):
    
    

    global ans
    if i==n:
        count = len(honest)

        
        for i in range(1,n+1):

            if i in honest:
                if [i,0] in evid:
                    count=0
            else:
                if [i,1] in evid:
                    count=0

        ans=max(ans,count)

    else:
        dfs(i+1,evid+l[i],honest+[i+1])
        
        dfs(i+1,evid,honest)
        

n=int(input())
l=[]
for i in range(n):
    a=int(input())
    b=[list(map(int,input().split())) for i in range(a)]
    l+=[b]

ans=0
dfs(0,[],[])
print(ans)

Solution (Python):
from itertools import product


def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)

    assumptions = product([0, 1], repeat=N)
    assumptions = sorted(assumptions, key=lambda x: x.count(0))
    for assumption in assumptions:
        for i in range(N):
            if assumption[i]:
                for testimony in testimonies[i]:
                    if not assumption[testimony[0] - 1] == testimony[1]:
                        break
                else:
                    continue
                break
        else:
            print(assumption.count(1))
            break
        continue


if __name__ == '__main__':
    main()

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).count("1"))
    print(ans)
    return


main()

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

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

ans = 0
for i in range(2**n):
    tmp = '0'*n
    for j in range(n):
        if i >> j & 1:
            tmp = tmp[:j]+'1'+tmp[j+1:]
    
    flg = True
    
    for j in range(n):
        if tmp[j] =='1':
            for k in range(len(lst[j])):
                x,y = lst[j][k]
                if tmp[x-1] == str(y):
                    continue
                else:
                    flg = False
        else:
            continue
    if flg:
        ans = max(ans, list(tmp).count('1'))

print(ans)

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

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

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

res = 0

for k in range(1 << N):
    flag = False
    for i in range(N):
        f = (k & (1 << i)) > 0

        if not f:
            continue
        for q in Q[i]:
            x, y = q
            tx = (k & (1 << x)) > 0

            if (y and not tx) or (not y and tx):
                flag = True
                break

        if flag:
            break
    else:
        res = max(res, bin(k).count("1"))

print(res)

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x, y = [int(_) for _ in stdin.readline().rstrip().split()]
        XY[i].append([x-1, y])

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

Solution (Python):
from itertools import product

N = int(input())
A = []
XY = [[] for _ 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())))

ans = 0
for pattern in product(range(2), repeat=N): 
  flag = True
  for i in range(N):
    if pattern[i]: 
      
      for a in range(A[i]):
        if pattern[XY[i][a][0]-1] != XY[i][a][1]:
          flag = False
          break
  if flag:
    ans = max(ans, sum(pattern))

print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline









N, = map(int, input().split())
L = []
for i in range(N):
    c = int(input())
    a = [[int(v) for v in input().split()] for _ in range(c)]
    L.append(a)

def dfs(index, al):
    for v in L[index]:
        c = v[0] - 1
        if c not in al:
            if v[1]:
                al = dfs(c, al + [c])

    return al

t = [None] * N
for i in range(N):
    t[i] = dfs(i, [i])

ans = 0
for i in range(1 << N):
    a = set()
    for j in range(N):
        if (i >> j) & 1:
            a.add(j)

    for p in list(a):
        for v in t[p]:
            a.add(v)

    s = [-1] * N
    f = True

    for v in a:
        s[v] = 1

    for v in a:
        for x, y in L[v]:
            if s[x-1] == -1:
                s[x-1] = y
            elif s[x-1] != y:
                f = False
    if f:
        ans = max(ans, len(a))

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):
a = int(input())
l = []

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

def is_honest(i,j):
    return (i >> j)%2 ==1

def honest_cnt(i):
    ans = 0
    for j in range(a):
        ans += is_honest(i,j)
    return ans
ans =0

for i in range(1 << a):
    ok = True
    for j in range(a):
        if not is_honest(i,j):continue
        for (x,y) in l[j]:
            if y == 0 and is_honest(i,x):ok = False
            if y == 1 and not is_honest(i,x):ok = False
        
    if ok:
        ans = max(ans, honest_cnt(i))
print(ans)

Solution (Python):
N = int(input())
A =[0]*N
S =[[] for i in range(N)]
ans = 0
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        S[i].append(list(map(int, input().split())))
form = "0" + str(N) + "b"
for i in range(2**N):
    p = list(map(int, list(format(i,form))))

    if all([all([p[j] == 0 or p[S[j][k][0]-1] == S[j][k][1] for k in range(len(S[j]))]) for j in range(N)]):
        ans = max(ans,sum(p))
print(ans)

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

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


def check(honest):  
    for i in range(n):
        if not honest[i]: continue  
        for j in range(a[i]):
            
            if y[i][j] == 1 and not honest[x[i][j]]: return False
            
            if y[i][j] == 0 and honest[x[i][j]]: return False
    
    return True


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


print(dfs([]))

Solution (Python):


N = int(input())
tf = [[] for _ in range(N)]
pl = []
for i in range(N):
    p = int(input())
    pl.append(p)
    for j in range(p):
        tf[i].append(list(map(int, input().split())))

ans = 0
import itertools
for flags in itertools.product([1, 0], repeat=N):
    f = True
    for i in range(N):
        for j in range(pl[i]):
            if flags[i] == 1:
                if flags[tf[i][j][0] - 1] != tf[i][j][1]:
                    f = False
            
            
            
            
            
            
            if not f:
                break
        if not f:
            break
    if f:
        ans = max(sum(flags), ans)

print(ans)

Solution (Python):
N=int(input())
shogen=[]
for i in range(N):
  a=int(input())
  ash=[]
  for j in range(a):
    xy=tuple(map(int,input().split()))
    ash.append(xy)
  shogen.append(ash)
cnt="0000"
for i in range(1<<N):
  flag=True
  fact="0"*(N-len(bin(i)[2:]))+bin(i)[2:]
  for j in range(N):
    if fact[j]=='1':
      s=shogen[j]
      for xy in s:
        if fact[xy[0]-1]!=str(xy[1]):
          flag=False
          break
  if flag:
    cnt=fact
ans=0
for c in cnt:
  ans+=int(c)
      
print(ans)

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

XY=[[list(map(int,input().split())) for i in range(int(input()))] for n in range(N)]
for i in range(N):
    for m in range(len(XY[i])):
        XY[i][m][0]-=1

num=set()
for i in range(2**N):
    AC=[-1 for Z in range(N)]
    lst=(N-len(bin(i)[2:]))*"0"+bin(i)[2:]
    flag=0
    for l in range(N):
        if lst[l]=="1":
            if AC[l]==0:
                flag=1
                break
            else:
                AC[l]=1

            for x,y in XY[l]:
                if AC[x]==-1:
                    AC[x]=y
                if AC[x]==1 and y==0 or AC[x]==0 and y==1 :
                    flag=1
                    break
            if flag:
                break
        else:
            if AC[l]==1:
                flag=1
                break
            else:
                AC[l]=0
    if not flag:
        num.add(sum(AC))
print(max(num))

Solution (Python):
def is_case_possible(case):
    for i, flag in enumerate(case):
        if flag == '1':
            for x, y in XY[i]:
                x -= 1
                if case[x] != str(y):
                    return False
    return True

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

ans = 0
for i in range(2**N):
    case = bin(i)[2:].zfill(N)
    if is_case_possible(case):
        ans = max(ans, case.count('1'))
print(ans)

Solution (Python):
from collections import namedtuple
from itertools import compress, product

Testimony = namedtuple('Testimony', 'honest_persons unkind_persons')

def bin_iter(num, width=1):
    assert width > 0
    while num > 0 or width > 0:
        yield num & 1
        num >>= 1
        width -= 1

def pop_count(num):
    return sum(bin_iter(num))

def solve(testimonies):
    def is_not_contradicted(honest_persons):
        for testimony in compress(testimonies, bin_iter(honest_persons, len(testimonies))):
            if (testimony.honest_persons | honest_persons) > honest_persons:
                return False
            if testimony.unkind_persons & honest_persons:
                return False
        return True
    return max(map(pop_count, filter(is_not_contradicted, range(1 << len(testimonies)))), default=0)

def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        honest_persons, unkind_persons = 0, 0
        for _ in range(int(input())):
            x, y = list(map(int, input().split()))
            if y == 1:
                honest_persons |= (1 << (x - 1))
            else:
                unkind_persons |= (1 << (x - 1))
        testimonies.append(Testimony(honest_persons, unkind_persons))
    print(solve(testimonies))

if __name__ == '__main__':
    main()

Solution (Python):

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

def main():
    N=int(input())
    
    xy=list()
    A=list()
    for i in range(N):
        a=int(input())
        l=list()
        for _ in range(a):
            l.append(tuple(map(int, input().split())))
        A.append(a)
        xy.append(l)

    answer = 0
    for i in range(2**N):
        contradict=False
        count = 0
        for j in range(N):
            if (i>>j)&1 > 0:
                count += 1
                for x, y in xy[j]:
                    k = (i>>(x-1))&1
                    if (y==1 and k==0) or (y==0 and k==1):
                        contradict=True
                        break
            if contradict==True:
                break
        else:
            answer = max(answer, count)

    print(answer)


if __name__ == '__main__':
    main()

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

def is_honest(i,j):
    return(i >> j)%2 ==1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i,j)
    return ans

ans= 0
for i in range(1<<n):
    bl = True
    for j in range(n):
        if not is_honest(i,j):
            continue
        for (x,y) in shogen[j]:
            if y==0 and is_honest(i,x):
                bl = False
            if y==1 and not is_honest(i,x):
                bl = False
    if bl:
        ans=max(ans,honest_cnt(i))
print(ans)

Solution (Python):
N = int(input())
A = []
xy = []
for _ in range(N):
    a = int(input())
    A.append(a)
    tmp = []
    for _ in range(a):
        tmp.append(tuple(map(int, input().split())))
    xy.append(tmp)
ans = 0
for i in range(2**N)[::-1]:
    is_honest = [0] * N
    for idx, c in enumerate(bin(i)[2:][::-1]):
        if c == "1":
            is_honest[idx] = 1

    flag = True
    for i in range(N):
        a = A[i]
        for j in range(a):
            x, y = xy[i][j][0], xy[i][j][1]
            if is_honest[i]:
                if is_honest[x-1] != y:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans, sum(is_honest))
print(ans)