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())
T = [[] for x in range(N)]

for i in range(N):
    for _ in range(int(input())):
        idx, t = map(int, input().split())
        T[i].append((idx-1, t))

ans = 0
for i in range(1, 2**N):
    ok = True
    ans_t = 0
    for j in range(N):
        if (i>>j) & 1 == 0:
            continue
        ans_t += 1
        for (x,y) in T[j]:
            if (i>>x) & 1 != y:
                ok = False
                break
        if not ok:
            break
    if ok:
        ans = max(ans, ans_t)
print(ans)

Solution (Python):

import sys
import time
import unittest
from io import StringIO




def resolve():
    N = int(input())
    aa = []
    for i in range(N):
        xy = {}
        aa.append(xy)
        for _ in range(int(input())):
            x, y = [int(i) for i in input().split()]
            xy[x - 1] = 1 == y
    maxsum = 0
    for comb in range(2**N - 1, -1, -1):
        sum = 0
        for i in range(N):
            if (comb >> i) & 1:
                sum += 1
                for x in aa[i].keys():
                    if aa[i][x]:
                        if not ((comb >> x) & 1):
                            break
                    else:
                        if (comb >> x) & 1:
                            break
                else:
                    continue
                break
        else:
            maxsum = max(maxsum, sum)
    print(maxsum)


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

    def checkTLE(self, input):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin

    def debugIO(self, input):
        stdin = sys.stdin
        sys.stdin = StringIO(input)
        resolve()
        sys.stdin = stdin

    def setUp(self):
        self.startTime = time.time()

    def tearDown(self):
        t = time.time() - self.startTime
        print('%s: %.3f' % (self.id(), t), flush=True)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    if "IS_LOCAL" in locals():
        suite = unittest.TestLoader().loadTestsFromTestCase(TestClass)
        unittest.TextTestRunner(verbosity=0).run(suite)
    else:
        resolve()

Solution (Python):
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(2**n):
	flag = False
	cnt = 0
	for j in range(n):
		if (i >> j) & 1:
			cnt += 1
			for x, y in xy[j]:
				if y == 1:
					if (i >> x & 1) == 0:
						flag = True
				elif y == 0:
					if (i >> x & 1) == 1:
						flag = True
	if not flag:
		ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(1 << n):
	true_or_false = [0] * n
	flag = False
	for j in range(n):
		if (i>>j)&1:
			true_or_false[n-1-j] = 1
	for i, l in enumerate(xy):
		for x, y in l:
			if true_or_false[i] == 1:
				if true_or_false[x-1] != y:
					flag = True
	if not flag:
		ans = max(ans, len([i for i in true_or_false if i == 1]))
print(ans)

Solution (Python):
def main():

    N = int(input())

    testimony_person = []
    testimony_judge = []

    for i in range(N):
        n = int(input())
        tmp_person = []
        tmp_judge = []
        
        for j in range(n):
            per, jud = map(int, input().split())
            tmp_person.append(per)
            tmp_judge.append(jud)
        
        testimony_judge.append(tmp_judge)
        testimony_person.append(tmp_person)


    max_honest = 0


    for i in range(2 ** N):
        N_honest = 0
        person_A = [0 for i in range(N)]
        person_T = [-1 for i in range(N)]
        FLAG = 1
        
        
        for j in range(N):

            bits = i >> j
            if (bits & 1):
                N_honest += 1
                person_A[j] = 1
                
                for k in range(len(testimony_person[j])):
                    p = testimony_person[j][k]
                    judge = testimony_judge[j][k]

                    if (person_T[p - 1] == -1):
                        person_T[p - 1] = judge
                    elif (person_T[p - 1] != judge):
                        FLAG = 0
                        break
        
        for i in range(N):
            if (person_T[i] != -1 and person_A[i] != person_T[i]):
                FLAG = 0
                break
        
        
        if (FLAG):
            max_honest = max(max_honest, N_honest)

    print(max_honest)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(2**n):
	true_or_false = [0] * n
	flag = False
	for j in range(n):
		if (i>>j)&1:
			true_or_false[n-1-j] = 1
	for i, l in enumerate(xy):
		for x, y in l:
			if true_or_false[i] == 1:
				if true_or_false[x-1] != y:
					flag = True
	if not flag:
		ans = max(ans, len([i for i in true_or_false if i == 1]))
print(ans)

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

honest=0
binstr="0" + str(n+2) + "b"
for i in range(2**n):
	hl = list(map(int,format(i,binstr)))
	hl = hl[2:]
	
	flag=True
	
	for j,hatsu in enumerate(hatsugen):
		for hat in hatsu:
			if hat[1] != hl[hat[0]-1]:
				if hl[j] == 1:
					flag = False

	

	if flag:
		honest = max(honest,hl.count(1))

print(honest)

Solution (Python):
def solve(N, A, X, Y):
    ret = 0
    for i in range(2 ** N):
        tmp = []
        for j in range(N):
            if i >> j & 1:
                tmp.append(j)
        if not tmp:
            continue

        is_valid = True
        for a_idx in tmp:
            for idx in range(A[a_idx]):
                if (Y[a_idx][idx] and X[a_idx][idx] - 1 not in tmp) \
                        or (not Y[a_idx][idx] and X[a_idx][idx] - 1 in tmp):
                    is_valid = False
                    break
        ret = max(ret, len(tmp)) if is_valid else ret
    return ret

if __name__ == "__main__":
    N = int(input())
    A = []
    X, Y = [], []
    for _ in range(N):
        A.append(int(input()))
        tmp_x, tmp_y = [], []
        for _ in range(A[-1]):
            x, y = map(int, input().split())
            tmp_x.append(x)
            tmp_y.append(y)
        X.append(tmp_x)
        Y.append(tmp_y)
    print(solve(N, A, X, Y))

Solution (Python):
"""
有向グラフ, シフト演算
"""

n = int(input())

g = [[0]*15 for i in range(15)]

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

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

print(ans)

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

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

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

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

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

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

Solution (Python):
import itertools
 
N = int(input())
 
 
As = []
xys = []
for i in range(N):
    tmp = []
    As.append(int(input()))
    for i in range(As[-1]):
        tmp.append(list(map(int, input().split())))
    
    xys.append(tmp)
 

bit_list = list(itertools.product(range(2), repeat = N))
 

ans = 0 
for bit in bit_list:
    unkind_count = 0
    for Aindex, A in enumerate(As):
        if(bit[Aindex] == 0):
            continue 
        for xy in xys[Aindex]:

            
            honest_to_unkind = (xy[1] == 0 and bit[xy[0]-1] == 1)
            unkind_to_honest = (xy[1] == 1 and bit[xy[0]-1] == 0)
 
            if(honest_to_unkind or unkind_to_honest):
                unkind_count +=1
    
    if(unkind_count == 0):

        ans = max(ans, sum(bit))
 
print(ans)

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

cnt = 0
for bit in product([0,1],repeat=n):
    fl = [1] * n 
    hantei = True
    for i,j in enumerate(bit):
        if j == 1:
            fl[i] = 0
    counter = 0
    for k in range(n):
        for l in range(a[k]):
            
            if fl[k] == 1 and fl[xy[counter][0]-1] != xy[counter][1]:
                hantei = False
                break
            counter += 1
    if hantei:
        cnt = max(cnt,sum(fl))

print(cnt)

Solution (Python):
from itertools import product


def solve(bit):
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    return 0
    return sum(bit)


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

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

ans = 0
for bit in product([0, 1], repeat=n):
    ans = max(ans, solve(bit))
print(ans)

Solution (Python):
import itertools

N = int(input())


As = []
xys = []
for i in range(N):
    tmp = []
    As.append(int(input()))
    for i in range(As[-1]):
        tmp.append(list(map(int, input().split())))
    
    xys.append(tmp)


bit_list = list(itertools.product(range(2), repeat = N))


ans = 0 
for bit in bit_list:
    unkind_count = 0
    for Aindex, A in enumerate(As):
        if(bit[Aindex] == 0):
            continue 
        for xy in xys[Aindex]:

            
            honest_to_unkind = (xy[1] == 0 and bit[xy[0]-1] == 1)
            unkind_to_honest = (xy[1] == 1 and bit[xy[0]-1] == 0)

            if(honest_to_unkind or unkind_to_honest):
                unkind_count +=1
    
    if(unkind_count == 0):

        ans = max(ans, sum(bit))

print(ans)

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

ans = 0
for i in range(2**N):
  flag = True
  for j in range(N):
    for k in range(A[j]):
      
      if (i >> j) & 1:
        if ((i >> (x[j][k]-1)) & 1) != y[j][k]:
          flag = False
          break
  if flag:
    count = sum([int(b) for b in bin(i)[2:]])
    ans = max(ans, count)
print(ans)

Solution (Python):
N = int(input())
shougens = []
for _ in range(N):
    A = int(input())
    s = [] 
    for _ in range(A):
        s.append(tuple(map(int, input().split())))
    shougens.append(s)

maxcount = 0
for i in range(2**N):
    vi = [(i>>k) & 1 for k in range(N)]
    for j in range(N):
        ss = shougens[j]
        is_break = False
        if vi[j]:
            for x, y in ss:
                x -= 1
                if vi[x] ^ y:
                    is_break = True
                    break
        if is_break:
            break
    else:
        
        maxcount = max(maxcount, bin(i).count('1'))

print(maxcount)

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

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

ans = 0
def judge(f):
    for i in range(n):
        if flag[i] == 1:
            for j in xy[i]:
                if f[j[0] - 1] != j[1]:
                    return False
        
    return True

for i in range(2 ** n):
    flag = [0] * n
    for j in range(n):
        if i >> j & 1:
            flag[j] = 1
    if judge(flag):
        ans = max(ans, sum(flag))
print(ans)

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

num_honest = 0
for i in range(2 ** n):
    honests = []
    dishonests = []
    flag = 0
    for j in range(n):
        if flag:
            break
        if i & (1 << j):
            if j not in honests and j not in dishonests:
                honests.append(j)
            elif j in dishonests:
                flag = 1
                break
            for p in depositions[j]:
                a, b = p
                if b == 1:
                    if a not in honests and a not in dishonests:
                        honests.append(a)
                    elif a in dishonests:
                        flag = 1
                        break
                else:
                    if a in honests:
                        flag = 1
                        break
                    elif a not in dishonests:
                        dishonests.append(a)
        elif j in honests:
            flag = 1
            break
        elif j not in dishonests:
            dishonests.append(j)
    if flag == 0:
        num_honest = max(num_honest, len(honests))
print(num_honest)

Solution (Python):
import itertools
N = int(input())
shougens = []
for _ in range(N):
    A = int(input())
    s = [] 
    for _ in range(A):
        s.append(tuple(map(int, input().split())))
    shougens.append(s)

maxcount = 0
for li in itertools.product([0, 1], repeat=N):
    for man, shojiki in enumerate(li):
        ss = shougens[man]
        is_break = False
        for x, y in ss:
            x = x - 1
            if shojiki and li[x] != y:
                
                is_break = True
                break
            
        if is_break:
            break
    else:
        
        maxcount = max(maxcount, sum(li))

print(maxcount)

Solution (Python):


import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())


honest_claims = [0 for _ in range(N)]
unkind_claims = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i] |= 1<<(j-1)
        else:
            unkind_claims[i] |= 1<<(j-1)




def get_unkind_claim(honests):
    unkinds = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            unkinds |= unkind_claims[i]
        honests = honests >> 1
        i += 1
    return unkinds

def get_honest_claim(honests):
    honest_claim = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            honest_claim |= honest_claims[i]
        honests = honests >> 1
        i += 1
    return honest_claim

def count_1(honests):
    count = 0
    while(honests>0):
        if honests & 1 > 0:
            count += 1
        honests = honests >> 1
    return count

max_honests = 0

for honests in range(1,2**N):
    unkind_claim = get_unkind_claim(honests)
    honest_claim = get_honest_claim(honests)
    if unkind_claim & honests > 0:
        continue
    if (honest_claim | honests) > honests:
        continue
    else:
        max_honests = max(max_honests, count_1(honests))

print(max_honests)

Solution (Python):
n = int(input())
XY = []
for _ in range(n):
    a = int(input())
    XY.append([list(map(int, input().split())) for __ in range(a)])
ans = 0
for i in range(1, 2 ** n):
    S = []
    F = []
    for j in range(n):
        if i >> j & 1:
            S.append(j + 1)
        else:
            F.append(j + 1)
    consistent = True
    for s in S:
        xy = XY[s - 1]
        for x, y in xy:
            if y == 1 and x in F: consistent = False
            if y == 0 and x in S: consistent = False
    if consistent:
        ans = max(ans, len(S))
print(ans)

Solution (Python):
from itertools import product

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

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

ans = 0
for bit in product([0, 1], repeat=n):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Solution (Python):
from itertools import product

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

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

ans = 0
for bit in product([0, 1], repeat=n):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    f = 1
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Solution (Python):
N = int(input())
people = [[-1 for __ in range(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 -= 1
        people[i][x] = y

ans = 0


for i in range(1 << N):
    ansi = 0
    flag = True
    for j in range(N):
        peoplei = 0
        if (i & 1 << j):
            peoplei = 1
            ansi += 1
        for k in range(N):
            if (i & 1 << k):
                if(people[k][j] != -1 and people[k][j] != peoplei):
                    flag = False

    if flag:
        ans = max(ans, ansi)


print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n = int(input())
a = []
xy = []
for _ in range(n):
    tmp_a = int(input())
    tmp_xy = [[int(i) for i in readline().split()] for _ in range(tmp_a)]
    a.append(tmp_a)
    xy.append(tmp_xy)
    
from itertools import product

ans_list = []

for comb in product([1,0], repeat=n):
    lie_list = [-1]*n
    flag = True
    for i in range(n):
        if comb[i] == 1:
            if lie_list[i] == -1:
                lie_list[i] = 1
            elif lie_list[i] == 1:
                pass
            elif lie_list[i] != 1:
                flag = False
                break
            for x,y in xy[i]:
                if lie_list[x-1] == -1:
                    lie_list[x-1] = y
                elif lie_list[x-1] == y:
                    pass
                elif lie_list[x-1] != y:
                    flag = False
                    break
        else:
            if lie_list[i] == -1:
                lie_list[i] = 0
            elif lie_list[i] == 0:
                pass
            elif lie_list[i] != 0:
                flag = False
                break
    if flag:
        ans_list.append(sum(comb))

if ans_list:
    print(max(ans_list))
else:
    print(0)

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

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

Solution (Python):
N = int(input())
A = []
XY = []
honest_count = []

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

for i in range(2 ** N):
    pt = [0] * N
    ck = 1
    for j in range(N):
        if (i >> j) & 1:
            pt[N - j - 1] = 1

    for k in range(N): 
        if pt[k] == 1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] - 1]:
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))


print(max(honest_count))

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

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

Solution (Python):
N = int(input())
A = []
XY = []
honest_count = []

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

for i in range(2 ** N):
    pt = [0] * N
    ck = 1
    for j in range(N):
        if (i >> j) & 1:
            pt[N - j - 1] = 1

    for k in range(N): 
        if pt[k] == 1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] - 1]:
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))


print(max(honest_count))

Solution (Python):
n = int(input())
say = {}
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int,input().split())))
    say[i] = xy
ans = 0
for i in range(2 ** n):
    c = [0 for i in range(n)]
    p = 0
    for j in range(n):
        
        if ((i >> j) & 1):
            
            c[j] = 1
    
    for j in range(n):
        
        if ((i >> j) & 1):
            
            if c[j] == -1 or c[j] == 1:
                c[j] = 1
            else:
                p = 1
                
                break
            for k in say[j]:
                if c[k[0]-1] == -1:
                    c[k[0]-1] = k[1]
                elif c[k[0]-1] != k[1]:
                    p = 1
                    
                    break
        
        if p == 1:
            break
    if p == 0 and ans < c.count(1):
        ans = c.count(1)
print(ans)

Solution (Python):
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
    a_ = int(input())
    for _ in range(a_):
        a[i].append(list(map(int, input().split())))
ans = 0
for i in range(1, 2**(n)):
    b = str(bin(i, )[2:]).zfill(n)
    t = True
    for idx, j in enumerate(b):
        if not t: break
        if j == "0": continue
        for a_i in a[idx]:
            if b[a_i[0]-1] != str(a_i[1]):
                t = False
                break
    if t:
        ans = max(ans, b.count("1"))
print(ans)

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

mx = 0


bit = 2**n
for i in range(bit):
    muzyun = 0
    dist = [False for i in range(n)]
    for j in range(n):
        if ((i>>j) & 1):
            dist[j] = True
    for j in range(n):
        if ((i>>j) & 1):
            tnt = lis[j]
            for k in tnt:
                if k[1] ==1 and dist[k[0]-1] == False:
                    muzyun = 1
                if k[1] ==0 and dist[k[0]-1] == True:
                    muzyun = 1
    if muzyun ==0:
        mx = max(dist.count(True),mx)

print(mx)

Solution (Python):
N = int(input())
check = list()
for i in range(N):
    a = int(input())
    tmp = list()
    for j in range(a):
        tmp.append(list(map(int,input().split())))
    check.append(tmp)
lis = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(2**N)]

result = 0
for i in lis:
    checker = 1
    for j in range(len(i)):
        if checker == 0:
            break
        if i[j] =="1":
            for k in range(len(check[j])):
                if i[check[j][k][0]-1] != str(check[j][k][1]):
                    checker = 0
                    break
        
    if checker ==1 and result < i.count("1"):
        result = i.count("1")
print(result)

Solution (Python):
from itertools import product

N = int(input())
testimony ={j:[-1 for i in range(N)] for j in range(1,N+1)}
A=[]
for i in range(1,N+1):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = list(map(int, input().split()))
        testimony[i][x-1] =y



assumption_correct =[]
for assumption in product([1,0], repeat=N):
    count_2=0
    for i in range(N):      
        if assumption[i] ==1:
            count =0 
            for j in range(N):  
                         
                if testimony[i+1][j] ==assumption[j]:
                    count +=1
            if count == A[i]:
                count_2 +=1
    if count_2 ==sum(assumption):
        assumption_correct.append(sum(assumption))
print(max(assumption_correct))

Solution (Python):
import itertools
import math
import fractions
import functools

import math
import itertools





N = int(input())
ans = [[-1] * N for i in range(N)]


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


def is_ok(num):
    
    
    
    people = []
    for i in range(N):
        if (num >> i) & 1:
            people.append(1)
        else:
            people.append(0)


    for i in range(N):
        if people[i] == 1:
            for j in range(N):
                if ans[i][j] == 1 and people[j] != 1:
                    return False
                if ans[i][j] == 0 and people[j] != 0:
                    return False
    return True


    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    


def countBit(num):
    ori = num
    count = 0
    while(num > 0):
        if(num & 1):
            count += 1
        num = num >> 1
    return count


out = 0

for i in range(1 << N):
    if(is_ok(i)):
        out = max(out, countBit(i))

print(out)

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

shougen = [[]for i in range(0,N+1,1)]
A = [0]*(N+1)
for i in range(1,N+1,1):
    A[i] = int(input())
    for j in range(0,A[i],1):
        shougen[i].append(list(map(int,input().split())))

maxshoujiki =0
for i in range(0,pow(2,N),1):
    is_shoujiki = [0]*(N+1)
    for j in range(0,N,1):
        if((i>>j)&1):
            is_shoujiki[j+1]=1

    isBAD = False
    for j in range(1,N+1,1):
        if is_shoujiki[j] == 1:
            for k in range(0,A[j],1):
                if is_shoujiki[shougen[j][k][0]]!=shougen[j][k][1]:
                    isBAD = True
    if not isBAD:
        maxshoujiki = max(maxshoujiki,sum(is_shoujiki))

print(maxshoujiki)

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

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

Solution (Python):
N = int(input())
ans = 0
xy = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x, y = map(int, input().split())
    xy[i].append([x-1, y])
for i in range(1<<N):
  flag = 1
  count = list()
  for j in range(N):
    if i>>j & 1:
      count.append(j)
  for k in count:
    for x, y in xy[k]:
      if(y == 1):
        if x not in count:
          flag = 0
      else:
        if x in count:
          flag = 0
  
  if(flag == 1):
    ans = max(ans, len(count))
print(ans)

Solution (Python):
import itertools
n = int(input())
li = []
for _ in range(n):
    lee = int(input())
    tmp = []
    for i in range(lee):
        tmp.append(list(map(int,input().split())))
    li.append(tmp)


kumi = list(itertools.product(range(2), repeat=n))



ans_li = []
for kk in kumi:
    flag = True
    for i,k in enumerate(kk):
        if k == 1:
            target = li[i]
            for t in target:
                
                if kk[t[0]-1]!=t[1]:
                    flag = False
    if flag:
        ans_li.append(sum(kk))
if len(ans_li)==0:
    print(0)
else:
    print(max(ans_li))

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

ans = 0
for i in range(2**n):
    b = format(i, 'b')
    b = str(b).rjust(n,'0')
    b = b[::-1]
    cou = 0
    p = 0
    for j in range(n):
        if p == 1:
            break
        if b[j] == "1":
            cou += 1
            for k,g in syo[j]:
                if int(b[k-1]) != g:
                    p = 1
                    break
    if p == 0:
        ans = max(ans,cou)
print(ans)

Solution (Python):
import itertools
N=int(input())
A=[]
arr=[]
ans=0
li=list(itertools.product([0,1], repeat=N))

for n in range(N):
  a=int(input())
  A.append(a)
  arr.append([ list(map(int,input().split())) for  _ in range(a)])
  
for l in li:
  
  flg=0
  for n in range(N):
    if l[n]==1:
      for m in range(A[n]):
        if l[arr[n][m][0]-1]!=arr[n][m][1]:
          flg=1
          break
      if flg==1:
        break
  if flg==1:
    continue
  count=l.count(1) 
  ans=max(ans,count)
      
print(ans)