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):
import sys
import numpy as np 

n = int(sys.stdin.readline().rstrip())
graph = [None] * n
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if not a: continue
    graph[i] = np.array([sys.stdin.readline().split() for _ in range(a)], dtype=np.int16).T

def main():
    comb = (np.arange(1 << n)[:, None] >> np.arange(n) & 1).astype(np.bool)
    ok = np.full(1 << n, True, dtype=np.bool)
    for i in range(n):
        if graph[i] is None: continue
        x, y = graph[i]
        ok &= ~comb[:, i] | np.all(comb[:, x-1] == y.astype(np.bool), axis=1)

    print(np.amax(comb[ok].sum(axis=1)))

if __name__ ==  '__main__':
    main()

Solution (Python):
N = int(input())
rela = [[0] * N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            rela[i][x] = 1
        else:
            rela[i][x] = -1  
def kensyou(person):
    for i in range(N):
        for j in range(N):
            if person[i] == 1:
                if rela[i][j] == 1:
                    if person[j] == -1:
                        return 0
                elif rela[i][j] == -1:
                    if person[j] == 1:
                        return 0
    return 1
ans = 0
for i in range(2 ** N):
    person = []
    for j in range(N):
        if ((i >> j) & 1):
            person.append(1)
        else:
            person.append(-1)
    
    if kensyou(person):
        ans = max(ans, person.count(1))
print(ans)

Solution (Python):










mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    """n = int(input())
    v = []
    for i in range(n):
        v.append([])
    for i in range(n):
        A = int(input())
        for j in range(A):
            human,lie = readInts() 
            v[human-1].append([human - 1,lie]) 
    print(v)
    def judge(bit):
        
        print(bin(bit))
        for i in range(n):
            
            
                
            for x,y in v[i]:
                print(x,y,bit)
                
                if y == 1 and not (bit & (1 << x)):
                    return False
                
                if y == 0 and (bit & (1 << x)):
                    return False
        return True
    res = 0
    for bit in range(1 << n):
        if judge(bit):
            count = 0
            for i in range(n):
                if bit & (1 << i):
                    count += 1
            res = max(res,count)
    print(res)
    """
    n = int(input())
    xy = [[] for _ in range(n)]
    for i in range(n):
        A = int(input())
        for j in range(A):
            x,y = readInts()
            xy[i].append([x,y])
    ans = 0
    for b in range(1 << n):
        for m in range(n):
            if (b >> m) & 1:
                for x,y in xy[m]:
                    if y != (b >> (x-1) & 1):
                        break
                else:
                    continue
                break
        else:
            ans = max(ans,bin(b).count("1"))
    print(ans)
if __name__ == '__main__':
  main()

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

g_list = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
    m = int(input())
    for j in range(m):
        a_x = list(map(int, input().split()))
        a = a_x[0]
        a -= 1
        x = a_x[1]
        g_list[i][a] = x

ans = 0

for i in range(1 << N):
    d = [0 for l in range(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_list[j][k] == -1:
                    continue
                if g_list[j][k] != d[k]:
                    ok = False
    if ok:
        total = list(bin(i)[2:].rjust(N, '0'))
        count = 0
        for t in total:
            if t == '1':
                count += 1
        ans = max(ans, count)

print(ans)

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

def is_valid(s):
	for i in range(n):
		if s[i] == 0:
			continue
		for x, y in a[i]:
			if s[x] != y:
				return False
	return True

ans = 0
for i in range(1 << n):
	s = [0] * n
	for j in range(n):
		if (i >> j) & 1:
			s[j] = 1
	if is_valid(s):
		ans = max(ans, sum(s))

print(ans)

Solution (Python):
import collections

N = int(input())
edges = [[None] * N for _ in range(N)]
for i in range(N):
    num_prop = int(input())
    for j in range(num_prop):
        x, y = map(int, input().split())
        edges[i][x-1] = y


def check(hs, us):
    for h in hs:
        for h2 in hs:
            if edges[h][h2] == 0:
                return False
        for u in us:
            if edges[h][u] == 1:
                return False
    return True


def search():
    maxv = 0
    maxhs = None
    maxus = None
    for i in range(1 << N):
        hs = []
        us = []
        for j in range(N):
            if (i >> j) & 1 == 1:
                hs.append(j)
            else:
                us.append(j)
        if check(hs, us):
            if maxv < len(hs):
                maxv = len(hs)
                maxhs = hs
                maxus = us
    return maxv  

print(search())

Solution (Python):
n = int(input())
xy = [[] for i 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))
ans = 0
for i in range(2**n):
    tf = [0]*n 
    flag = True
    for j in range(n):
        if (i>>j)&1:
            tf[j] = 1
    for j in range(n):
        if tf[j]==1:
            for x,y in xy[j]:
                if tf[x] !=y:
                    flag = False
                    break
    if flag:ans = max(ans,sum(tf))
print(ans)

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

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

"""
    矛盾したらFalse
    矛盾しなければTrue
    正直者と仮定した者の証言
        正直&正直者と仮定されている
        不親切&不親切と仮定されている
"""
def check(i, xiyj, HoU):
    
    if HoU ^ ((i >> xiyj) & 1):
        return False

    return True

max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    is_contradiction = True
    for j in range(len(XY)):
        
        if not ((i >> j) & 1): continue
        count+=1
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
                break 
                
        if not is_contradiction:
            break 

    
    if is_contradiction and (count > max_honest):
        max_honest =count
            
print(max_honest)

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

XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    
    if ((i >> xiyj) & 1) ^ HoU:
        return False

    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    is_contradiction = True
    for j in range(len(XY)):
        
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
                break
                
        if not is_contradiction:
            break

    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)

Solution (Python):
n = int(input())
 
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    
    if ((i >> xiyj) & 1) ^ HoU:
        return False
 
    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    honest = [0] * len(XY)
    is_contradiction = True
    for j in range(len(XY)):
        
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
 
    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)

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

ans = 0

for i in range(2**n):
    flag = True
    for j in range(n):  
        if (i >> j) & 1 == 1:  
            for k in range(a_list[j]):  
                if xy_list[j][k][1] == 1:
                    m = xy_list[j][k][0]
                    if (i >> m-1) & 1 != 1:  
                        flag = False
                        break

                elif xy_list[j][k][1] == 0:
                    m = xy_list[j][k][0]
                    if (i >> m-1) & 1 == 1:
                        flag = False
                        break
    if flag:
        i_bin = format(i, 'b')
        if ans < i_bin.count('1'):
            ans = i_bin.count('1')

print(ans)

Solution (Python):

import numpy as np


def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        A.append([])
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
            A[i].append(xy)
    

    c=0
    for bit in range(1,2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        
        ok=True
        for i in range(N):
            if bs[i]:
                for j in range(len(A[i])):
                    x, y = A[i][j]
                    if y==1 and bs[x-1]==0:
                        ok=False
                        break
                    if y==0 and bs[x-1]!=0:
                        ok=False
                        break
                else:
                    continue
                break

        if ok:
            
            
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

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

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

Solution (Python):
num = int(input())
coms = []

ans_num = 0

for com in range(num):
    b = []
    n = int(input())
    for _ in range(n):
        xi,yi = [int(j) for j in input().split(" ")]
        b.append([int(xi) - 1, int(yi)])
    coms.append(b)

for i in range(2 ** num):
    selects = []
    ans_array = [0 for _ in range(num)]
    indexes = []
    flag = True

    
    for j in range(num):
        if((i >> j) & 1):
            selects.append(coms[j])
            indexes.append(j)
            ans_array[j] = 1
    
    for index in indexes:
        for com in coms[index]:
            if ans_array[com[0]] != com[1]:
                flag = False
                break

    if flag and (len(indexes) >= ans_num):
        ans_num = len(indexes)

print(ans_num)

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

answers=[]
counts=[]


for i in range(N):
    A=int(input())
    answer=[]
    for a in range(A):
        x,y=map(int,input().split())
        answer.append([x,y])
    answers.append(answer)


for i in range(pow(2,N)):
    hypo=str(bin(i))[2:].rjust(N,"0")
    judge=True
    count=0
    
    for n in range(N):
        if judge==False:
            break
        elif hypo[n]=="1":
            count+=1
            for ans in answers[n]:
                if hypo[ans[0]-1]==str(ans[1]):
                    pass
                else:
                    judge=False
                    break
    if judge==False:
        pass
    else:
        counts.append(count)

print(max(counts))

Solution (Python):
N=int(input())
xy=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        xy[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if xy[j][k]==-1:
                    continue
                if xy[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)

Solution (Python):
N=int(input())
a=[]
for i in range(N):
	A=int(input())
	B=[]
	for i in range(A):
		b=list(map(int,input().split()))
		B.append(b)
	a.append(B)
ans=0
for i in range(2**N):
	bi=list(str(bin(i)))
	bi=bi[2:]
	bi=[0]*(N-len(bi))+bi
	bi=list(map(int,bi))
	p=1
	for j in range(N):
		if bi[j]==1:
			for k in range(len(a[j])):
				m=a[j][k][0]
				n=a[j][k][1]
				if bi[m-1]!=n:
					p=0
					break
	if p==1:
		ans=max(ans,sum(bi))
print(ans)

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

A = []

for _ in range(n):
    t = int(input())
    A.append([list(map(int, input().split())) for _ in range(t)])

ans = 0
max = 0
flag = 0

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

Solution (Python):
N = int(input())
A = [0]*N
X = []
for i in range(N):
    A[i] = int(input())
    t = []
    for j in range(A[i]):
        t.append(tuple(map(int, input().split())))
    X.append(t)
    
ans = 0
for i in range(2**N):
    Flg = True
    cnt = 0
    for j in range(N):
        if((i>>j)&1): 
            for m in range(A[j]):
                x, y = X[j][m]
                if((i>>(x-1))&1 != y):
                    Flg = False
                    break
    if(Flg):
        ans = max(ans, bin(i).count("1"))
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]):
        k, l = map(int, input().split())
        x[i].append(k)
        y[i].append(l)

def dfs(cur, l):
    global ok
    if cur == n:
        ok = True
        for i in range(n):
            if l[i]==1 and any([l[x[i][j]-1]!=y[i][j] for j in range(a[i])]):
                ok = False
        return sum(l) if ok else 0
    else:
        l1 = l[:]
        l1[cur] += 1
        return max(dfs(cur+1, l), dfs(cur+1, l1))

print(dfs(0, [0]*n))

Solution (Python):
n = int(input())
xy = [[] for _ in range(n)]
ans = 0

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

for b in range(1 << n): 
    cnt = bin(b).count("1") 
    judge = True
    for i in range(n):
        if judge == False:
            break
        if b & (1 << i) != 0: 
            for x, y in xy[i]:
                if y == 1 and b & (1 << x - 1) == 0:
                    
                    judge = False
                if y == 0 and b & (1 << x - 1) != 0:
                    
                    judge = False
    if judge == True:
        ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())
l = [[] for i in range(n)]

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

ans = 0

for b in range(1 << n): 
    cnt = bin(b).count("1")
    judge = True
    for j in range(n):
        if judge == False: 
            break
        if b & (1 << j) != 0: 
            for x, y in l[j]:
                if y == 1 and b & (1 << x - 1) == 0: 
                    judge = False
                if y == 0 and b & (1 << x - 1) != 0: 
                    judge = False
    if judge == True:
        ans = max(cnt, ans)
print(ans)

Solution (Python):
def judge(bit):
    for i in range(N):
        if not(bit & (1 << i)):
            continue
        for xy in v[i]:
            x = xy[0] 
            y = xy[1]
            if y == 1 and not(bit & (1 << x)):
                return False
            if y == 0 and (bit & (1 << x)):
                return False
    return True

N = int(input())
v = []
for i in range(N):
    A = int(input())
    array = []
    for i in range(A):
        a,b = map(int, input().split())
        a-=1 
        array.append((a,b))
    v.append(array)

res = 0
for bit in range(1 << N):
    if judge(bit):
        count = bin(bit).count("1")
        res = max(res, count)
    
print(res)

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

person = [0]*(N)
c = 0

for i in range(2 ** N):
  person = [0]*(N)
  for j in range(N):
    if ((i >> j) & 1):
      person[j] = 1
  cc = sum(person)
  for j in range(N):
    if person[j] == 1:
      for k in range(A[j]):
        p = xy[j][k]
        if person[p[0]-1] != p[1]:
          
          cc = 0
  c = max(c,cc)  


print(c)

Solution (Python):
import copy
from itertools import permutations, product

n = int(input())
al = []
xyl = []
for i in range(n):
    a = int(input())
    al.append(a)
    tl = []
    for j in range(a):
        t = [int(i) for i in input().split()]
        tl.append(t)
    xyl.append(tl)

l = [i for i in product([0, 1], repeat=n)]

ans_list = []

for ll in l:
    ans_flag = 1
    for i in range(n):
        flag = 1
        for j in range(al[i]):
            if ll[xyl[i][j][0]-1] != xyl[i][j][1]:
                flag = 0
        if flag != ll[i]:
            ans_flag = 0
    if ans_flag == 1:
        ans_list.append(copy.deepcopy(ll))

ans = 0
for i in ans_list:
    k = i.count(1)
    if ans < k:
        ans = k

print(ans)

Solution (Python):
n = int(input())
xy = [[] for i 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

for b in range(1 << n): 
    cnt = bin(b).count("1")
    ok = True
    for j in range(n):
        if ok == False:
            break
        if b&(1 << j) != 0:
        
        
            for x, y in xy[j]: 
                if y == 1 and b&(1 << x - 1) == 0:
                
                    ok = False
                if y == 0 and b&(1 << x - 1) != 0:
                
                    ok = False
    if ok == True:
        ans = max(cnt, ans)
print(ans)

Solution (Python):
N=int(input())
people=[]
test=[]
for i in range(N):
    a=int(input())
    bufs=[list(map(int,input().split())) for _ in range(a)]
    test.append(bufs)

num=0
for i in range(pow(2,N)):
    flag=1
    flag2=1
    truthtable=[0]*N
    honestunkind=[-1]*N
    for j in range(N):
        if (i>>j)&1:
            truthtable[j]=1
    
    for j in range(N):
        if truthtable[j]==0:
            for k in test[j]:
                people=k[0]-1
                horu=k[1]
                if honestunkind[people]==-1:
                    honestunkind[people]=(horu+truthtable[j]+1)%2
                else:
                    if honestunkind[people]!=(horu+truthtable[j]+1)%2:
                        flag=0
                        break
            if flag==0:
                break
    if flag==1:
        for j in range(N):
            if (truthtable[j]!=honestunkind[j])and(honestunkind[j]!=-1):
                flag2=0
                break
        if flag2==1:
            
            num=max(num,truthtable.count(0))
        
print(num)

Solution (Python):
N = int(input())
xy = [[] for i 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])

res = 0
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        ok = True
        if i >> j & 1:
            cnt += 1
            for k in range(len(xy[j])):
                if (i >> (xy[j][k][0] - 1) & 1) != xy[j][k][1]:
                    ok = False
                    break
        if ok == False:
            cnt = 0
            break
    res = max(res, cnt)
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
chk = [[set(),set()] for _ in range(n)]
for o in range(n):
  a = int(input())
  for i in range(a):
    x,y = [int(i) for i in input().split()]
    if y == 0:
      chk[o][0].add(x-1)
    if y == 1:
      chk[o][1].add(x-1)
    
chk = tuple(chk)
answer = 0
for i in range(2**n):
  b = format(i,'b')
  b = b.zfill(n)[::-1]
  chk_0 = set()
  chk_1 = set()
  p = []
  for j in range(n):
    if b[j] == '1':
      p.append(j)
      chk_1.add(j)
    if b[j] == '0':
      chk_0.add(j)
  for i in p:
    if not chk[i][0] <= chk_0:
      break
    if not chk[i][1] <= chk_1:
      break
    if i == p[len(p)-1]:
      answer = max(answer,len(p))
      
print(answer)

Solution (Python):
n = int(input())
chk = [[set(),set()] for _ in range(n)]
for o in range(n):
  a = int(input())
  for i in range(a):
    x,y = [int(i) for i in input().split()]
    if y == 0:
      chk[o][0].add(x-1)
    if y == 1:
      chk[o][1].add(x-1)
    
chk = tuple(chk)
answer = 0
for i in range(2**n):
  b = format(i,'b')
  b = b.zfill(n)[::-1]
  chk_0 = set()
  chk_1 = set()
  p = []
  for j in range(n):
    if b[j] == '1':
      p.append(j)
      chk_1.add(j)
    if b[j] == '0':
      chk_0.add(j)
  
  for i in p:
    
    if not chk[i][0] <= chk_0:
      break
    if not chk[i][1] <= chk_1:
      break
    if i == p[len(p)-1]:
      
      answer = max(answer,len(p))
      
print(answer)

Solution (Python):
def main():
    n = int(input())
    tl = [[-1] * n for _ in range(n)]  
    for i in range(n):
        ts = int(input())
        for _ in range(ts):
            x, y = [int(x) for x in input().split()]
            x -= 1
            tl[i][x] = y  
    ans = set()
    for i in range(2 ** n):
        pl = [i >> d & 1 for d in range(n)]
        possible = True
        for k, p in enumerate(pl):
            if not possible:
                break
            if p != 1:
                continue
            
            for j, t in enumerate(tl[k]):
                if t == -1:
                    continue
                if t != pl[j]:
                    possible = False
                    break
        if possible:
            ans.add(bin(i).count('1'))
    return max(ans)


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

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

g=[[-1 for n in range(N)] for m in range(N)]

for n in range(N):
    A=int(input())
    for m in range(A):
        x,y=map(int,input().strip().split())
        g[x-1][n]=y

def c(n,N,base):
    S=[0 for i in range(N)]
    for i in range(N):
        S[i]=n%base
        n=n//base
    return S


def honest_judge(S,g):
    honest=True
    for n in range(len(S)):
        if S[n]==1:
            for i in range(N):
                if g[i][n]!=-1 and g[i][n]!=S[i]:
                    honest=False
        if honest==False:
            break
    return honest

MAX=0
for n in range(2**N):
    S=c(n,N,2)
    if honest_judge(S,g)==True:
        if sum(S)>=MAX:
            MAX=sum(S)

print(MAX)

Solution (Python):
n=int(input())
xy=[[] for i 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
for b in range(1<<n):
  cnt=bin(b).count("1")
  ok=True
  for j in range(n):
    if not ok:break
    if b&(1<<j):
      for x,y in xy[j]:
        if y==1 and b&(1<<x-1)==0:ok=False
        if y==0 and b&(1<<x-1):ok=False
  if ok:
    ans=max(cnt,ans)
print(ans)

Solution (Python):
n=int(input())
xy=[[] for i 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
for b in range(1<<n):
  cnt=bin(b).count("1")
  if cnt<=ans:continue
  for j in range(n):
    if b&(1<<j):
      for x,y in xy[j]:
        if y==1 and b&(1<<x-1): continue
        if y==0 and b&(1<<x-1)==0: continue
        break
      else:
        continue
      break
  else:
    ans=cnt
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)])

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

Solution (Python):
N = int(input())
L = []
for k in range(N):
    t = []
    for l in range(int(input())):
        x, y = map(int,input().split())
        t.append([x-1,y])
    L.append(t)
ans = 0
for k in range(2**N):
    t = []
    for d in range(N):
        if (k>>d)&1:
            t.append(d)
    flag = 1
    for e in t:
        for f in L[e]:
            if f[0] in t and f[1] == 0:
                flag = 0
                break
            if f[0] not in t and f[1] == 1:
                flag = 0
                break
    ans = max(ans,flag*len(t))
print(ans)

Solution (Python):
n=int(input())
a=[]
for i in range(n):
    x=int(input())
    b=[[int(i) for i in input().split()] for i in range(x)]
    a.append(b)

ans=0

for i in range(2**n):
    status=[True]*n
    for j in range(n):
        if ((i>>j)&1):
            status[j]=False
    
    judge=[None]*n
    contradiction=False
    
    for x,person in enumerate(a):
        if status[x]==False:
            continue
        for testimony in person:
            if testimony[1]==1: 
                if judge[testimony[0]-1]!=False and status[testimony[0]-1]==True:
                    judge[testimony[0]-1]=True
                else:
                    contradiction=True
            else:
                if judge[testimony[0]-1]!=True and status[testimony[0]-1]==False:
                    judge[testimony[0]-1]=False
                else:
                    contradiction=True

    if contradiction==False:
        ans=max(ans,status.count(True))
print(ans)

Solution (Python):

n = int(input())
A = []
for i in range(n):
  A.append([])
  A[i].append(int(input()))
  for j in range(A[i][0]):
    A[i].append([int(_) for _ in input().split()])
    
def bit_count(num):
  cc = 0
  while num:
    cc += num & 1
    num >>= 1
  return cc


res = 0
for bit in range(2 ** n):
  for i in range(n): 
    if ((bit >> i) & 1) == 0: 
      continue
    for j in range(A[i][0]):
      x, y = A[i][j+1]
      if (bit >> (x-1)) & 1 != y:
        break
    else:
      continue
    break
  else:
    res = max(res, bit_count(bit))
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())
        x -= 1
        t[i].append([x, y])

ans = 0
for p in range(1 << n):
    cnt = 0
    is_not = False
    for i in range(n):
        if p >> i & 1:
            cnt += 1
            for ti in t[i]:
                x, y = ti
                if (p >> x & 1) != y:
                    is_not = True
                    cnt = 0
                    break
        if is_not:
            break
    ans = max(ans, cnt)
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())

ans = 0
 
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    checked = 1
    for j in range(N):
        if bit[j] == "1":
            for k in range(A[j]):
                if int(bit[x[j][k] - 1]) != y[j][k]:
                    checked = 0
                    break
    if checked == 1:
        ans = max(ans, bit.count("1"))
 
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())

ans = 0


for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    
    checked = 1
    for j in range(N):
        if bit[j] == "1":  
            for k in range(A[j]):
                if int(bit[x[j][k] - 1]) != y[j][k]:
                    checked = 0
                    break
    if checked == 1:
        ans = max(ans, bit.count("1"))

print(ans)