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())
saying =[]
people =[]
result = 0

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

for i in range(2**N):

    for j in range(N):
        if(i & 1<<j):
            people[j]=1
        else:
            people[j]=0
    honest = 0
    for j in range(N):
        if people[j]==1:
            for k in range(0, len(saying[j]),2):
                if people[saying[j][k]-1] != saying[j][k+1]:
                    break
            else:
                honest += 1
                continue
            break
    else:
        if honest>result:
            result = honest

print(result)

Solution (Python):
from itertools import product
n = int(input())
a = [[] for i in range(n)]

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

ans = 0
for c in product([1, 0], repeat=n):
    f = True
    for i, p in enumerate(c):
        if p == 1:
            for x, y in a[i]:
                if c[x] != y:
                    f = False
                    break
        if not f:
            break
    if f:
        ans = max(ans, sum(c))
print(ans)

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

testimony = []

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

ans = 0

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

    for k in range(n):
        if good[k]:
            for l,m in testimony[k]:
                if good[l] != m:
                    f = 0
    
    if f:
        ans = max(ans,sum(good))

print(ans)

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

shogen = []

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

ans = 0

for i in range(2**N):
    good = [0 for _ in range(N)]
    f = 1
    for j in range(N):
        if ((i >> j)&1):
            good[j] = 1
    
    for k in range(N):
        
        if good[k]:
            for l, m in shogen[k]:
                
                if good[l] != m:
                    f = 0
    
    if f:
        ans = max(ans, sum(good))

print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os



def resolve():
    
    
    
    n = int(input())

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

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

        unable = False
        
        
        
        a = 0
        for j in range(n):
            
            if not i & 1 << j:
                continue

            a += 1

            
            for testimony in testimonies[j+1]:

                
                
                target = testimony[0] - 1
                
                if testimony[1] == 1 and not i & 1 << target:
                    unable = True
                    break
                
                elif testimony[1] == 0 and i & 1 << target:
                    unable = True
                    break

            
            if unable:
                break

        if unable:
            continue

        ans = max(ans, a)

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

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

jud = [[-1 for i in range(n)] for j in range(n)]
xy = []
ayasi = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        jud[i][x-1] = y
Max = 0
for i in range(2**n):
    li = []
    flag = True
    cnt = 0
    for j in range(n):
        if ((i >> j) & 1):
            li.append(1)

        else:
            li.append(0)
    for k in range(n):
        if li[k] == 1:
         for l in range(n):
             if jud[k][l] != -1:
                 if jud[k][l] != li[l]:
                     flag = False
                     break

    if flag:
        Max = max(sum(li),Max)
print(Max)

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

jud = [[-1 for i in range(n)] for j in range(n)]
xy = []
ayasi = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        jud[i][x-1] = y
Max = 0
for i in range(2**n):
    li = []
    flag = True
    cnt = 0
    for j in range(n):
        if ((i >> j) & 1):
            li.append(1)

        else:
            li.append(0)
    for k in range(n):
        if li[k] == 1:
         for l in range(n):
             if jud[k][l] != -1:
                 if jud[k][l] != li[l]:
                     flag = False
                     break

    if flag:
        Max = max(sum(li),Max)
print(Max)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for i in range(N):
	A = INT()
	xy.append([LIST() for _ in range(A)])

ans = 0
for X in product((0, 1), repeat=N):
	for j in range(N):
		if X[j] == 1:
			for x, y in xy[j]:
				if X[x-1] != y:
					break
			else:
				continue
			break
	else:
		ans = max(ans, sum(X))

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for i in range(N):
	A = INT()
	xy.append([LIST() for _ in range(A)])

ans = 0
for i in range(1<<N):
	i = list("{:b}".format(i).zfill(N))
	for j in range(N):
		if i[j] == "1":
			for x, y in xy[j]:
				if y != int(i[x-1]):
					break
			else:
				continue
			break
	else:
		tmp = sum([int(x) for x in i])
		ans = max(ans, tmp)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for _ in range(N):
	A = INT()
	xy_A = []
	for _ in range(A):
		xy_A.append(LIST())
	xy.append(xy_A)

ans = 0
for X in product((0, 1), repeat=N):
	honest = [-1]*N
	for j in range(N):
		if X[j] == 0:
			if honest[j] == -1:
				honest[j] = 0
			elif honest[j] == 1:
				break
		elif X[j] == 1:
			if honest[j] == -1:
				honest[j] = 1
			elif honest[j] == 0:
				break

			for x, y in xy[j]:
				if honest[x-1] == -1:
					honest[x-1] = y
				elif honest[x-1] != y:
					break
			else:
				continue
			break
	else:
		ans = max(ans, sum(X))

print(ans)

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

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

ans = 0
for i in range(2 ** N):
  ok = True
  for j in range(N):
    if (i >> j) & 1:
      
      for s in statement[j]:
        person = s[0]
        flag = s[1]
        if ((i >> person) & 1) != flag:
          
          ok = False
          break
    if not ok:
      break
  if ok:
    honest = str(bin(i)).count("1")
    if ans < honest:
      ans = honest
print(ans)

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

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

for l in sorted(itertools.product([0, 1], repeat=n),reverse=True):
    bl = True
    for i, a in enumerate(l):
        if a == 1:
            for b in xy[i]:
                if l[b[0] - 1] != b[1]:
                    bl = False
                    break
    if bl:
        print(sum(l))
        exit()
print('0')

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

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

ans = 0

for l in list(itertools.product([0, 1], repeat=n)):
    bl = True
    for i,a in enumerate(l):
        if a == 1:
            for b in xy[i]:
                if l[b[0] - 1] != b[1]:
                    bl = False
    if bl:
        ans = max(ans, sum(l))
print(ans)

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums

def main():
    num = int(input())
    say_count = []
    say_data = []
    for i in range(num):
        aaa = int(input())
        say_count.append(aaa)
        data = [list(map(int, input().split())) for i in range(aaa)]
        say_data.append(data)


    ans = 0
    for i in range(2 ** num):
        bin_data = list(map(int, ternary(i, 2, num)))
        kari_ans = bin_data.count(1)

        people_flg = [-1 for i in range(num)]
        dame_flg = 0
        for j in range(num):
            if people_flg[j] == -1:
                people_flg[j] = bin_data[j]
            else:
                if people_flg[j] != bin_data[j]:
                    dame_flg = 1

            if people_flg[j] == 0:
                continue

            for k in range(say_count[j]):
                people, flg = say_data[j][k]
                people -= 1
                if people_flg[people] == -1:
                    people_flg[people] = flg
                else:
                    if people_flg[people] != flg:
                        dame_flg = 1

            if dame_flg:
                break
        if dame_flg:
            continue
        ans = max(ans, kari_ans)

    print(ans)






if __name__ == '__main__':
    main()

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

def saiki(A):
    if len(A)==N:
        honest=set()
        honest_kari=set()
        unkind=set()
        count=0
        unkind_kari=set()
        for i in range(N):
            if A[i]==1:
                honest.add(i)
            else:
                unkind.add(i)
        for i in range(N):
            if i in honest:
                for j in range(len(shogen[i])):
                    if shogen[i][j][1]==0:
                        unkind_kari.add(shogen[i][j][0]-1)
                    else:
                        honest_kari.add(shogen[i][j][0]-1)
        
        for i in unkind_kari:
            if i in unkind:
                count+=1
        for i in honest_kari:
            if i in honest:
                count+=1
        if count==len(unkind_kari)+len(honest_kari):
            kari=set(list(honest)+list(honest_kari))
            
            count_ans.append(len(kari))

        
        return
    for i in range(2):
        A.append(i)
        saiki(A)
        A.pop()
saiki([])
print(max(count_ans))

Solution (Python):
n = int(input())
xy = [[] for i in range(n)]
maxh = 0
for i in range(n):
  a = int(input())
  for j in range(a):
    xy[i].append(list(map(int, input().split())))
for i in range(1<<n):
  tmp = [-1] * n
  try:
    for j in range(n):
      if i & (1<<j):
        if tmp[j] == -1:
          tmp[j] = 1
        elif tmp[j] == 0:
          raise
        for k, l in xy[j]:
          if tmp[k-1] == -1:
            tmp[k-1] = l
          elif tmp[k-1] != l:
            raise
      else:
        if tmp[j] == -1:
          tmp[j] = 0
        elif tmp[j] == 1:
          raise
  except:
    pass
  else:
    hoge = tmp.count(1)
    if hoge > maxh:
      maxh = hoge
print(maxh)

Solution (Python):
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def judge(x,y,a,bit):
    for i in range(len(a)):
        if bit&(1<<i):
            for j in range(a[i]):
                if ((bit>>x[i][j])&1)^y[i][j]:
                    return False
    return True

n = I()
a = []
x = []
y = []
for i in range(n):
    A = I()
    a.append(A)
    xt = []
    yt = []
    for _ in range(A):
        tmp = LI()
        xt.append(tmp.pop(0)-1)
        yt.append(tmp.pop(0))
    x.append(xt)
    y.append(yt)

ans = 0
length = 2**n
for i in range(length):
    result = judge(x,y,a,i)
    if result:
        ans = max(ans,bin(i).count('1'))
    
print(ans)

Solution (Python):
import numpy as np


N = int(input())
XY = []
ANS = []


for _ in range(N):
    a = int(input())
    tmp = []

    for _ in range(a):
        xy = tuple(map(int, input().split()))
        tmp.append(xy)
    XY.append(tmp)


for b in range(2 ** N):
    status = []
    for i in range(N):
        j = b >> i & 1
        status.append(j)
    status = np.array(status)

    f = 1
    ans = 0

    for i in range(N):
        j = b >> i & 1
        if not j:
            continue
        for x, y in XY[i]:
            s = status[x - 1]
            if s != y:
                f = 0
                break
        if not f:
            break

    if f:
        ans = np.sum(status)
    ANS.append(ans)


print(max(ANS))

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

def check(ps,honests):
    for x, y in ps:
        x -= 1
        if y == 1 and honests[x] == 0:
            return False
        if y == 0 and honests[x] == 1:
            return False
    return True
        


ans = 0
for b in range(2**n):
    honests = []
    is_ok = True
    for j in range(n):
        honests.append(b & (1<<j)>0)
    for ps,h in zip(As,honests):
        if h:
            is_ok &= check(ps,honests)
    if is_ok:
        ans = max(ans,sum(honests))
print(ans)

Solution (Python):
def main():
    xy = []
    n = int(input())
    for _ in range(n):
        a = int(input())
        xy.append([list(map(int, input().split())) for _ in range(a)])
    ans = 0
    
    for a in range(2**n):
        c = []
        for b in range(n):
            c.append(a >> b & 1)
       
        flag = True
        for i in range(n):
            if c[i] == 1:
                for x, y in xy[i]:
                    if c[x - 1] != y:
                        flag = False
                        
        if flag:
            ans = max(ans, sum(c))
    
    print(ans)
        
    
if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l=[[float('inf')]*n for i in range(n)]
ans=0
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=[int(s) for s in input().rstrip().split()]
    l[i][x-1]=y

for i in range(2**n):
  d=[0 for j in range(n)]
  for j in range(n):
    if i>>j & 1:
      d[j]=1
      
  flag=1
  for j in range(n):
    if d[j]==1:
      for k in range(n):
        if l[j][k]==float('inf'):
          continue
        if l[j][k]!=d[k]:
          flag=0

  if flag==1:
    ans=max(ans,sum(d))

print(ans)

Solution (Python):
n=int(input())
a=[0]*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]):
    tmp = list(map(int,input().split()))
    x[i].append(tmp[0])
    y[i].append(tmp[1])


res=0
for bit in range(2**n):
  p_cnt = 0
  fact = 1
  for i in range(n):
    if bit >> i & 1:
      p_cnt += 1
      for j in range(a[i]):
        if  y[i][j] ^ (bit >> x[i][j] -1) & 1:
          fact=0
          break
  if fact and res < p_cnt:
    res = p_cnt
print(res)

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

res = 0
for i in range(1 << n):
    p = [-1] * n
    contradiction_flag = False
    for j in range(n):
        if (i >> j) & 1:
            if p[j] == 0:
                contradiction_flag = True
                break
            p[j] = 1

            for person, h_or_u in t[j]:
                if h_or_u == 0:
                    if p[person-1] == 1:
                        contradiction_flag = True
                        break
                    p[person-1] = 0
                else:
                    if p[person-1] == 0:
                        contradiction_flag = True
                        break
                    p[person-1] = 1
        
        else:
            if p[j] == 1:
                contradiction_flag = True
                break
            p[j] = 0
    
    if not contradiction_flag:
        res = max(res, n - p.count(0))

print(res)

Solution (Python):
def solve(li):
    for i in range(n):
        if li[i] == 0:
            continue
        else:
            for name, honest in L[i]:
                if li[name-1] != honest:
                    return 0
    else:
        return li.count(1)

n = int(input())
L = []
for _ in range(n):
    a = int(input())
    A = [list(map(int, input().split())) for _ in range(a)]
    L.append(A)
ans = 0
for i in range(2 ** n):
    li = [0] * n
    for j in range(n):
        if ((i >> j) & 1 != 0):
            li[j] = 1
    ans = max(ans, solve(li))
print(ans)

Solution (Python):
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

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

max=0


for l in range(0,2**n):
    i=2**n-1-l
    flag=1
    if max<bin(i).count("1"):
        for j in range(0,n):
       
        
            if  bin( i& 2**j).count("1")>0:
                 for k in range(0,n):
                      if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                          flag=0 
                          break
                       
            if flag==0:
                break
        if flag==1 and max<bin(i).count("1"):
             max=bin(i).count("1")
         

print(max)

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())
patt=[]  
for i in range(2 ** n): 
  bag = []
  for j in range(n):  
    if ((i >> j) & 1):
      bag.append(1)  
    else:
      bag.append(0)
  patt.append(bag)
per=[[-1 for i in range(n)] for l in range(n)] 
for s in range(n): 
  a=int(input())
  for t in range(a):    
    x, y = map(int, input().split())
    per[s][x-1]=y
ma=0
for i in patt: 
  check=0
  for l in range(n): 
    if i[l]==1: 
      for t in range(n): 
        if per[l][t]!=i[t] and per[l][t]!=-1:
          check=-1
          break
        else:
          continue
  if check==0:
    ma=max(ma, sum(i))
        
print(ma)

Solution (Python):
n = int(input())
data = [[[],[]] for _ in range(n)]
ans = 0
for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        data[i][y].append(x-1)
for i in range(1,2**n):
    S1 = set([])
    S2 = set([])
    for j in range(n):
        if (i >> j) & 1:
            S1.add(j)
        else:
            S2.add(j)
    flag = True
    for i in S1:
        for j in range(2):
            if data[i][j]:
                if j == 0:
                    for k in data[i][j]:
                        if k in S1:
                            flag = False
                else:
                    for k in data[i][j]:
                        if k in S2:
                            flag = False
    else:
        if flag:
            ans = max(ans,len(S1))
print(ans)

Solution (Python):

"""
C - HonestOrUnkind2
https://atcoder.jp/contests/abc147/tasks/abc147_c

"""
import sys


from itertools import product

def solve(N, data):
    ans = 0
    for prd in product([0, 1], repeat=N):
        res = [0] + list(prd)
        is_valid = True
        for i, p in enumerate(prd, start=1):
            if p == 0:
                continue
            for x, y in data[i]:
                if y != res[x]:
                    is_valid = False
                    break
        if is_valid:
            ans = max(ans, sum(res))
    return ans


def main(args):
    N = int(input())
    data = [[] for _ in range(N+1)]
    for a in range(1, N+1):
        for _ in range(int(input())):
            x, y = map(int, input().split())
            data[a].append([x, y])
    ans = solve(N, data)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

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

result = 0

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

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    testify = [[] for _ in range(N)]
    for i in range(N):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            testify[i].append((x, y))
    
    ans = 0
    for i in range(2**N):
        honest = set()
        for j in range(N):
            if (i>>j) & 1:
                honest.add(j)
        if len(honest) <= ans:
            continue
        liar = set(range(15)) - honest
        flag = True
        for j in honest:
            honesttmp = set()
            for s, t in testify[j]:
                if t == 1 and s-1 not in honest:
                    flag = False
                    break
                if t == 0 and s-1 in honest:
                    flag = False
                    break
        if flag:
            ans = max(len(honest), ans)
            
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
 
talk = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        talk[i].append([person-1, state])


from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)


for i in range(len(ptns)):
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in talk[j]:
                if ptns[i][k[0]] != k[1]:
                    break
            else:
                continue
            break
    else:
        print(sum(ptns[i]))
        exit()

Solution (Python):
n = int(input())
 
testimony = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])


from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)


for i in range(len(ptns)):
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    break
            else:
                continue
            break
    else:
        print(sum(ptns[i]))
        exit()

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


ans = 0
for bit in range(1, 2**n):
    flg = True
    
    for i in range(n):
        if not flg:
            break

        
        if not (bit >> i & 1):
            continue

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

            
            
            
            if (bit >> (x - 1) & 1) ^ y:
                flg = False
                break
    if flg:
        ans = max(ans, bin(bit).count('1'))

print(ans)

Solution (Python):
n = int(input())
 
testimony = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])


from itertools import product
s = [0,1]
ptns = list(product(s, repeat=n))
ptns = list(reversed(ptns))


for i in range(len(ptns)):
    error = 0
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    error = 1

    if error == 0:
        print(sum(ptns[i]))
        exit()

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

for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])


from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)


for i in range(len(ptns)):
    
    error = 0
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    error = 1

    if error == 0:
        print(sum(ptns[i]))
        exit()

Solution (Python):

import itertools
n = int(input())
word_g = []
for i in range(n):
    m = int(input())
    part_word = []
    for j in range(m):
        part_word.append(list(map(int, input().split())))
    word_g.append(part_word)

state = list(itertools.product([0,1], repeat = n))  

def abc147c(n, word, i):
    word_i = []
    
    for j1 in range(n):
        if i[j1]  == 0:
            word_i.append([])
        else:
        	word_i.append(word[j1])
          
    
    check_mujun = [[] for i in range(n)]
    
    for j in word_i:
        for k in j:
            check_mujun[k[0] -1].append(k[1])
    
    
    counter = 0
    
    for x, j in enumerate(check_mujun):
        
        if len(set(j)) == 0  :
            counter += i[x]
            
        elif len(set(j)) == 1 and sum(set(j)) == i[x]:
            counter += i[x]
            
        else:
            return -1
            break
    return counter

output = 0 
for i in state:
    output = max(output, abc147c(n,word_g,list(i) ) )
    
print(output)