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
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok


def main():
    N = ii()
    P = [tuple(tuple(mis()) for _ in range(ii())) for __ in range(N)]
    ho = [None] * N
    ans = 0
    for b in range(2**N):
        for i in range(N):
            ho[i] = bool(b & (1<<i))
        if ans >= sum(ho):
            continue
        flag = True
        for i in range(N):
            if not flag:
                break
            if ho[i]:
                for x, y in P[i]:
                    x -= 1
                    if bool(y) !=  ho[x]:
                        flag = False
                        break
        
        if not flag:
            continue

        ans = sum(ho)
    print(ans)




main()

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

ans = 0
for i in range(1<<N):
    h=[]
    for j in range(N):
        if(i&(1<<j)):
            h.append(j)

    for j,x,y in T:
        if(j in h):
            if(not((x in h)==y)):
                break
    else:
        ans = max(ans,len(h))

print(ans)

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


def main():
    N = int(input())
    X = []
    for i in range(N):
        a = int(input())
        X.append([])
        for j in range(a):
            x, y = [int(x) for x in input().split()]
            X[i].append([x, y])

    ans = 0
    for i in range(2 ** N):
        tmp = 0
        is_mujun = False
        for j in range(N):
            if i >> j & 1:
                tmp += 1
                for k in X[j]:
                    if k[1] == 1:
                        if not i >> (k[0] - 1) & 1:
                            is_mujun = True
                            break
                    else:
                        if i >> (k[0] - 1) & 1:
                            is_mujun = True
                            break
                    if is_mujun:
                        break
        if not is_mujun:
            ans = max(ans, tmp)

    print(ans)







if __name__ == '__main__':
    main()

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

ans = 0
for pattern in range(2 ** N):
    p = pattern
    numHonest = 0
    correct = True
    for i in range(N):
        if p & 1:
            numHonest += 1
            for evid in evids[i]:
                if (pattern >> (evid[0]-1)) & 1 != evid[1]:
                    correct = False
                    break
        
        
        
        
        
        if not correct:
            break
        p >>= 1
    if correct:
        ans = ans if ans > numHonest else numHonest
print(ans)

Solution (Python):
n = int(input())
time = [0 for _ in range(n)]
def nex(time):
  for i in range(n):
    if time[i] == 0:
      time[i] = 1
      return time
      break
    else:
      time[i] = 0
  else:
    return 'over'

wit = []
for i in range(n):
  a = int(input())
  add = [2 for _ in range(n)] 
  add[i] = 1
  for _ in range(a):
    x,y = map(int,input().split())
    x -= 1
    add[x] = y
  wit.append(add)
can = []
while time != 'over':
  for i in range(n):
    if time[i] == 1:
      for j in range(n):
        if wit[i][j] == 1 - time[j]:
          break
      else:
        continue
      break
  else:
    can.append(sum(time))
  time = nex(time)

print(max(can))

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

shougen = []

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


m = 0
for i in range(2 ** N):
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for shou in shougen[j]:
                if shou[1] != (i >> shou[0]) & 1:
                    flag = False

    if flag:
        wa = 0
        for j in range(N):
            wa += (i >> j) & 1
        m = max(m, wa)

print(m)

Solution (Python):

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

m = 0
for b in range(1 << n):
    f = True
    for i in range(n):
        if b >> i & 1 == 0:
            continue
        for j in range(a[i]):
            if y[i][j] == 1:
                if b >> x[i][j] & 1 == 0:
                    f = False
                    break
            else:
                if b >> x[i][j] & 1 == 1:
                    f = False
                    break

    if f:
        m = max(m, sum(map(int, bin(b)[2:])))

print(m)

Solution (Python):
N = int(input())
xs = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xs[i].append((x-1,y))
ans = 0
for b in range(1<<N):
    mujun = False
    for k,z in enumerate(xs):
        for x,y in z:
            if b&(1<<k):
                if b&(1<<x):
                    if y==0:
                        mujun = True
                else:
                    if y==1:
                        mujun = True
            if mujun:
                break
        if mujun:
            break
    if not mujun:
        tmp = bin(b).count('1')
        ans = max(ans, tmp)
print(ans)

Solution (Python):
import itertools

N = int(input())
A = []
lst = [[] for _ in range(N)]

for i in range(N):
	A.append(int(input()))
	for j in range(A[-1]):
		a, b = map(int, input().split())
		lst[i].append([a, b])
		
ans = 0
		
for cur in itertools.product(list(range(2)), repeat = N):
	flg = 0
	for i in range(N):
		if flg: break
		if cur[i] == 0: continue
		for j in range(len(lst[i])):
			if not cur[lst[i][j][0] - 1] == lst[i][j][1]:
				flg = 1
				break
	if not flg:
		ans = max(ans, sum(cur))
		
print(ans)

Solution (Python):
n = int(input())
g = [[[],[]] for _ in range(n)]
for i in range(n):
  a = int(input())
  g[i]=[tuple(map(int,input().split())) for _ in range(a)]
ans = 0
for num in range(1<<n):
  p = [j for j in range(n) if num&(1<<j)]
  fl = 0
  for v in p:
    for x,y in g[v]:
      if bool(num&(1<<(x-1))) != y:
        fl = 1
        break
    if fl:
      break
  else:
    if ans < len(p):
      ans = len(p)
print(ans)

Solution (Python):
from itertools import product
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    ai = int(input())
    for j in range(ai):
        x, y = map(int, input().split())
        x = x - 1
        A[i].append([x, y])


ans = 0
flg = False
for pattern in product([0, 1], repeat=N):
    Y = list(pattern)
    Truth = set()

    for i, p in enumerate(pattern):
        if p == 0:
            continue

        for j, yi in A[i]:
            if Y[j] == yi:
                continue
            else:
                flg = True
                break

        if flg:
            flg = False
            break

    else:
        ans = max(ans, sum(pattern))


print(ans)

Solution (Python):
import sys
n = int(input())
maps = []
for i in range(n):
    ud = []
    a = int(sys.stdin.readline().rstrip())
    for j in range(a):
        x, y = map(int, sys.stdin.readline().split())
        ud.append([x, y])
    maps.append(ud)
result = 0
for i in range(2**n)[::-1]:
    bf = False
    for j in range(n):
        if (i >> j) &1 > 0:
            for k in maps[j]:
                if (i >> (k[0]-1))&1 != k[1]:
                    bf = True
                    break
        if bf:
            break
    if bf == False:
        rc = bin(i).count('1')
        if rc > result:
            result = rc


print(result)

Solution (Python):

import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        A[i].append(tuple(map(int,input().split())))
for i in range(2**n):
    tr=set()
    fr=set()
    f=1
    count=0
    for k in range(n):
        if i>>k & 1:
            if (k+1) in fr:
                f=0
            tr.add(k+1)
            count+=1
            for xi,yi in A[k]:
                if yi:
                    if xi in fr:
                        f=0
                    tr.add(xi)
                else:
                    if xi in tr:
                        f=0
                    fr.add(xi)
        else:
            if (k+1) in tr:
                f=0
            fr.add(k+1)
    if f:
        ans=max(ans,count)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)



N = int(input())

T = [[]for i in range(N)]

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


ans = 0
def judge():
	global ans
	f=True
	for i in range(N):
		if l[i]==1:
			for g in T[i]:
				if l[g[0]] != g[1]:
					f=False
					break

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





def dfs(x):
	if x>=N:
		judge()
		return

	l[x] = 1
	dfs(x+1)
	l[x] = 0
	dfs(x+1)

l=[0]*N
dfs(0)
print(ans)

Solution (Python):
import itertools
n=int(input())
l=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        l[i][x-1] = y
m=0
for v in list(itertools.product(range(2), repeat=n)):
    f = True
    for i in range(n):
        if v[i]==1:
            for j in range(n):
                if l[i][j] == -1 or v[j]==l[i][j]:
                    continue
                else:
                    f=False
                    break
    if f:
        m = max(sum(v),m)
print(m)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[-1 for _ in range(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())
            A[i][x-1] = y

    ans = 0
    for i in range(2 ** N):
        bit = format(i, "b").zfill(N)
        
        one = 0
        flag = True
        for j in range(N):
            if bit[j] == "1":
                for k in range(N):
                    if A[j][k] >= 0 and A[j][k] != int(bit[k]):
                        flag = False
                        break
                one += 1    
        if flag: ans = max(ans, one)

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n=int(input())
xy=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        p,q=[int(k) for k in input().split()]
        xy[i].append([p-1,q])
ans=0
for i in range(2**n):
    s=bin(i)[2:].rjust(n,'0')
    r,t=0,0
    for j in range(n):
        if s[j]=="1":
            p,q=0,0
            for x,y in xy[j]:
                p+=1
                if s[x]!=str(y):
                    break
                q+=1
            if p!=q:
                break
            else:
                r+=1
        else:
            r+=1
        t+=1
    if r==n:
        ans=max(ans,s.count("1"))
        
            
print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
S = defaultdict(dict)
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        xi, yi = map(int, input().split())
        S[i][xi - 1] = yi

ans = 0
for i in range(1 << N):
    possible = True
    c = 0
    for j in range(N):
        if i >> j & 1:
            c += 1
            for xi, yi in S[j].items():
                if i >> xi & 1 != yi:
                    possible = False
                    break
    if possible:
        ans = max(ans, c)
print(ans)

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

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



q = 2 ** n
ans = 0
for i in range(q):
    d = list(map(int, list(str(bin(q + i))[2:])))
    check = 0
    for j, x in enumerate(d[1:]):
        if x == 1:
            for c, b in a[j]:
                if d[c+1] != b:
                    check = 1
                    break
    if check == 1:
        continue
    else:
        ans = max(ans, d.count(1) - 1)

print(ans)

Solution (Python):
N = int(input())
A = [0]*N
x = [0]*N
y = [0]*N
for _ in range(N):
    a = int(input())
    A[_] = a
    x[_] = [0]*a
    y[_] = [0]*a
    for __ in range(a):
        x[_][__],y[_][__] = map(int,input().split())
        x[_][__] -= 1

def bi(x):
    i = 0
    o = [0]*N
    while x > 0:
        o[i] = x % 2
        x //= 2
        i += 1
    return o

def b(o):
    for i in range(N):
        
        if o[i] == 0:
            continue
        
        for j in range(A[i]):
            k = x[i][j]
            if o[k] != y[i][j]:
                return -1
    return sum(o)

a = 0
for i in range(2 ** N):
    
    o = bi(i)
    a = max(a,b(o))

print(a)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
A = [0]*N
x = []
y = []
for i in range(N):
    A[i] = I()
    x0,y0 = Line(A[i],2)
    for j in range(len(x0)):
        x0[j] -= 1
    x.append(x0)
    y.append(y0)

ans = 0
from itertools import product
a = list(product([0,1],repeat=N))

for b in a:
    flag = True
    for i in range(N):
        if b[i]==1:
            for k in range(len(x[i])):
                if b[x[i][k]]!=y[i][k]:
                    flag=False
                    break
    if flag:
        now = sum(b)
        if now>ans:
            ans = now
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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 = "{:b}".format(i).zfill(N)
	flag = 0
	for j in range(N):
		if i[j] == '1': 
			for x, y in xy[j]:
				if y != int(i[x-1]):
					flag = 1
					break
		if flag == 1:
			break
	else:
		tmp = sum(map(int, list(i)))
		ans = ans if ans >= tmp else tmp
print(ans)

Solution (Python):
N = int(input())
A = []
L = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for _ in range(a):
        x,y = map(int, input().split())
        L[i].append((x, y))
        
ans = 0
for i in range(2**N, 2**(N+1)):
    f = 0
    b = bin(i)
    human = [0]*N
    for j in range(3, len(b)):
        if b[j] == "1":
            human[j-3] = 1
    for j in range(N):
        if human[j] == 0:
            continue
        for k in range(A[j]):
            if human[L[j][k][0]-1] != L[j][k][1]:
                f = 1
                break
    if f == 0:
        ans = max(ans, sum(human))
        
print(ans)

Solution (Python):
N=int(input())
A=[]
xy=[]
for i in range(N):
  A.append(int(input()))
  temp=A[-1]
  xy_temp=[]
  for j in range(temp):
    x, y=map(int, input().split())
    x-=1
    xy_temp.append([x, y])
    
  xy.append(xy_temp)
  
def num2bi(x, k):
  
  out=format(x, '0'+str(k)+'b')
  return out

n=2**N
counter=0
for i in range(n):
  temp=num2bi(i, N)
  a=True
  for i in range(N):
    if temp[i]=='1':
      for j in range(A[i]):
        if temp[xy[i][j][0]]!=str(xy[i][j][1]):
          a=False
        
  if a==True:
    count=0
    for i in range(N):
      if temp[i]=='1':
        count+=1
    counter=max(counter, count)
    
print(counter)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n = ii()
    a = [0 for i in range(n+1)]
    shougen = [[] for i in range(n+1)]

    for i in range(1,n+1):
        a[i] = ii()
        for j in range(a[i]):
            x,y = mi()
            shougen[i].append([x,y])
    

    ans = 0
    for itr in range(2**n):
        ilist = [0]
        tmp = itr
        while tmp > 0:
            ilist.append(tmp%2)
            tmp//=2
        if len(ilist) < n+1:
            for i in range(n+1-len(ilist)):
                ilist.append(0)
        flag = True

        for i in range(n+1):
            if ilist[i] == 0:
                continue
            else:
                for hatugen in shougen[i]:
                    if not ilist[hatugen[0]] == hatugen[1]:
                        flag = False
                        break
            if not flag:
                break
        if flag:
            ans = max(ans,sum(ilist))
    print(ans)

        


main()

Solution (Python):
N=int(input())
XY=[[] for i in range(N)]

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


ans=0
for i in range(2**N):
  ch=1
  cnt=0
  for j in range(N):
    if i>>j & 1:
      cnt+=1
      for xy in XY[j]:
        if xy[1]==1 and (i>>(xy[0]-1)&1) or xy[1]==0 and (i>>(xy[0]-1)&1)==0:
          continue
        else:
          ch=0
          break
    if ch==0:
      break
  if ch:
    ans=max(ans,cnt)

print(ans)

Solution (Python):
N = int(input())
A = [0]*N
xy = [[] for i in range(N)]
for i in range(N):
    A[i] = int(input())
    xy[i] = [tuple(map(int, input().split())) for i in range(A[i])]

ans = 0
for i in range(2**N):
    kind = [False]*N
    for j in range(N):
        if (i >> j) % 2 == 1:
            kind[j] = True

    flag = True
    tmp = 0
    for j in range(N):
        if kind[j]:
            tmp += 1

            for x, y in xy[j]:
                if (y == 1 and kind[x-1]) or (y == 0 and kind[x-1] == False):
                    continue

                else:
                    flag = False
                    tmp = 0
                    break

        if flag == False:
            tmp = 0
            break

    ans = max(ans, tmp)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

def check(honest) :
    for i in range(N) :
        for j in range(N) :
            if honest[i] and ((honest[j] == 0 and A[i][j] == 1) or (honest[j] == 1 and A[i][j] == 0)) :
                return False
                
    return True

ret = 0
for i in range(2 ** N) :
    honest = [0] * N
    for j in range(N) :
        if i & 1 :
            honest[j] = 1
        i //= 2
    
    if check(honest) :
        ret = max(ret, sum(honest))
    
print(ret)

Solution (Python):
def main():
    n = input()
    aa = []
    for _ in xrange(n):
        a = []
        for _ in xrange(input()):
            x, y = map(int, raw_input().split())
            a.append([x - 1, y])
        aa.append(a)
    best = 0
    for x in xrange(2 ** n):
        xx = [bool(x & (1 << i)) + 0 for i in xrange(n)]
        if all(all(xx[i] == f for i, f in a) for x, a in zip(xx, aa) if x):
            best = max(best, sum(xx))
    print best


main()

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge=[[]for _ in range(N)]
    for i in range(N):
        a=I()
        for _ in range(a):
            x,y = MI()
            edge[i].append((x-1,y))

    max_bit = 1<<N
    ans = 0
    for bit in range(max_bit):
        cnt = 0
        T = []
        people = [0]*N
        for i in range(N):
            if (1<<i)&bit:
                people[i]=True
                cnt += 1
                T.append(i)
            else:
                people[i]= 2
        ok = True
        visited = set()
        while T:
            u = T.pop()
            visited.add(u)
            for v,tf in edge[u]:
                if tf==1:
                    if people[v]==0:
                        ok = False
                        break
                    people[v] = True
                    if v not in visited:
                        T.append(v)
                        visited.add(v)
                else:
                    if people[v]==1:
                        ok=False
                        break
                    people[v] = False
        if ok:
            ans = max(ans,cnt)
    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0
tf = [0]*N
for bit in range(2**N):
    jdg = True
    for i in range(N):
        tf[i] = bit%2
        bit = bit >> 1
    for a in range(N):
        if tf[a] == 1:
            for i in range(N):
                if arr[a][i] != -1:
                    if arr[a][i] != tf[i]:
                        jdg = False
                        break
        if not jdg:
            break
    if jdg:
        ans = max(ans,tf.count(1))
print(ans)

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

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


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

    f = True
    for j in range(n):
        for k in range(len(xy[j])):
            x = xy[j][k][0] - 1
            y = xy[j][k][1]

            if y == 1:
                if (h[j] == 1 and h[x] == 0):
                    f = False
            else:
                if (h[j] == 1 and h[x] == 1):
                    f = False

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

print(ans)

Solution (Python):
import itertools

N = int(input())
S = []
for _ in range(N):
    A = int(input())
    s = []
    for _ in range(A):
        x, y = map(int, input().split())
        s.append((x, y))
    S.append(s)

Ps, ans = itertools.product([0, 1], repeat=N), 0
for P in Ps:
    right = True
    for i, p in enumerate(P):
        if p == 1:
            for x, y in S[i]:
                if (y == 1 and P[x - 1] == 0) or (y == 0 and P[x - 1] == 1):
                    right = False
    if right:
        ans = max(ans, sum(P))

print(ans)

Solution (Python):
n=int(input())
s=[[]for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        s[i].append([x-1,str(y)])
an=0
for i in range(2**n):
    b=bin(i)[2:]
    b="0"*(n-len(b))+b
    c=["a"]*n
    d=0
    for i in range(n):
        if b[i]!=c[i] and c[i]!="a":
            break
        else:
            c[i]=b[i]
            if b[i]=="1":
                for (j,h) in s[i]:
                    if c[j]!="a" and h!=c[j]:
                        d=1
                        break
                    else:
                        c[j]=h
        if d==1:
            break
    else:
        an=max(an,b.count("1"))
print(an)

Solution (Python):
def f(t,a,n,hist):
    if t != n:
        return max(f(t+1,a,n,hist+[0]),f(t+1,a,n,hist+[1]))
    for i in range(n):
        if hist[i] == 1:
            for j in range(n):
                if a[i][j] == -1:
                    continue
                if a[i][j] != hist[j]:
                    return 0
    return hist.count(1)

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

Solution (Python):
n=int(input())
a=[[] for i in range(n)]
b=[[] for i in range(n)]
for i in range(n):
    ai=int(input())
    for j in range(ai):
        x,y=map(int,input().split())
        x-=1
        if y==1:
            a[i].append(x)
        else:
            b[i].append(x)
ok=0
for i in range(2**n):
    j=i
    k=0
    cnt=0
    flag=True
    while(j>0 and flag):
        if j&1:
            cnt+=1
            for x in a[k]:
                if i|(1<<x)!=i:
                    flag=False
                    break
            for x in b[k]:
                if i&(1<<x)!=0:
                    flag=False
                    break
        j//=2
        k+=1
    if flag:
        ok=max(ok,cnt)
print(ok)

Solution (Python):
N = int(input())
G = {k: [] for k in range(N)}
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        G[i].append((x-1, y))

ans = 0
for i in range(2 ** N):
    flg = True
    for j in range(N):  
        if ((i >> j) & 1):  
            for x, y in G[j]:
                if (i >> x) & 1 != y:
                    flg = False
    if flg:
        c = 0
        for k in range(N):
            if ((i >> k) & 1):  
                c += 1
        ans = max(ans, c)

print(ans)

Solution (Python):

N = int(input())
ans = 0

dic = {}

for i in range(N):

    dic[i] = []

    A = int(input())

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

ans = 0
for i in range(2 ** N):

    si = format(i,"b")
    si = si.zfill(N)

    num = 0
    for j in si:
        if j == "1":
            num += 1

    flag = True
    
    for j in range(N):

        if si[j] == "1":

            for k in dic[j]:
                x = k[0]
                y = k[1]

                
                if int(si[x-1]) != y:
                    
                    flag = False

    if flag:
        ans = max(ans,num)

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 bit in range(1<<n):
    flag = 0
    for j in range(n):
        if (bit & (1<<j)) > 0:
            for x, y in xy[j]:
                if y == 1 and ((bit & (1<<x)) == 0):
                    flag = 1
                    break
                elif y == 0 and ((bit & (1<<x)) > 0):
                    flag = 1
                    break
    if flag:
        continue
    count = 0
    for j in range(n):
        if (bit & (1<<j)) > 0:
            count += 1
    ans = max(ans, count)

print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())
	L = [[] for i in range(N)]
	for i in range(N):
		A = int(input())
		for j in range(A):
			x, y = getlist()
			x -= 1
			L[i].append([x, y])
	

	ans = 0
	for i in range(1 << N):
		output = [0] * N
		cnt = 0
		for j in range(N):
			if ((i >> j) & 1) == 1:
				output[j] = 1
				cnt += 1
		judge = "Yes"
		for j in range(N):
			if output[j] == 1:
				for x, y in L[j]:
					if output[x] != y:
						judge = "No"
						break

		if judge == "Yes":
			ans = max(ans, cnt)
	print(ans)



if __name__ == '__main__':
	main()

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def convert(i, n):
    ret = []
    for j in range(n):
        if i & (1<<j):
            ret.append(1)
        else:
            ret.append(0)
    return ret

def check(tf, people):
    for i in range(len(people)):
        if not tf[i]:
            continue
        for j in range(len(people[i])):
            say = people[i][j]
            if say[1] != tf[say[0]]:
                return False
    return True

def main():
    n = ri()
    people = []
    for i in range(n):
        a = ri()
        say = []
        for j in range(a):
            x, y = rli()
            x -= 1
            say.append([x, y])
        people.append(say)
    ans = 0
    for i in range(pow(2, n)):
        tf = convert(i, n)
        ok = check(tf, people)
        if not ok:
            continue
        ans = max(ans, sum(tf))
    print(ans)


if __name__ == '__main__':
    main()