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
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def judge(bit):
    
    for i in range(N):
        
        if not (bit & (1<<i)):
            continue
        for v in V[i]:
            x = v[0]
            y = v[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())
    V[i] = []
    for j in range(A):
        x, y = input_nums()
        V[i].append((x-1, y)) 

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)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def judge(bit):
    
    for i in range(N):
        
        if not (bit & (1<<i)):
            continue
        for v in V[i]:
            x = v[0]
            y = v[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())
    V[i] = []
    for j in range(A):
        x, y = input_nums()
        V[i].append((x-1, y)) 

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)

Solution (Python):
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))


n = load()
sm = []
for _ in range(n):
    speak = {}
    a = load()
    for _ in range(a):
        x, y = load_list()
        speak[x-1] = bool(y)
    sm.append(speak)

def bit_count(bit):
    c = 0
    while bit > 0:
        bit &= bit - 1
        bit = bit >> 1
        c += 1
    return c


mx = 0
for bit in range(0, 1<<n):
    bf = False
    for i in range(0, n):
        if bit & (1 << i):
            for other, honest in sm[i].items():
                if (((bit & (1 << other))) > 0) == honest:
                    pass
                else:
                    bf = True
                    break
        if bf:
            break
    if not bf:
        mx = max(mx, bit_count(bit))
        
print(mx)

Solution (Python):



N = int(input())

m = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        m[i].append(list(map(int, input().rstrip().split())))
        
def dfs(i, state):
    if i == N:
        for j, s in enumerate(state):
            if s == 1:
                for x, y in m[j]:
                    if y == 1 and state[x-1] == 0:
                        return 0
                    elif y == 0 and state[x-1] == 1:
                        return 0
        return sum(state)
        
    max_honest = 0
    max_honest = max(max_honest, dfs(i+1, state + [0]))
    max_honest = max(max_honest, dfs(i+1, state + [1]))
    
    return max_honest
    
print(dfs(0, []))

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

N = int(input())
testimony = [[] for _ in range(N)]
for i in range(N):
    for j in range(int(input())):
        xy = tuple(map(int, input().split(' ')))
        testimony[i].append(xy)

def judge(is_honest):
    res = True
    for i in range(N):
        if is_honest[i]:
            for t in testimony[i]:
                x = t[0]-1
                y = t[1]
                if is_honest[x] == True and y == 0:
                    res = False
                if is_honest[x] == False and y == 1:
                    res = False
    return res

ans = 0
for bit in range(2**N):
    is_honest = [False] * N
    for i in range(N):
        if bit & 1<<i:
            is_honest[i] = True
    if judge(is_honest) == True:
        ans = max(ans, is_honest.count(True))

print(ans)

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

res = 0

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

print(res)

Solution (Python):
N = int(input())
shou = []
for f in range(N):
    x = int(input())
    for i in range(x):
        a, b = map(int, input().split())
        shou.append([f, a - 1, b])
max_count = 0
for i in range(1, 2 ** N):
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for z, x, y in shou:
            if (i >> x) & 1 != y and z == j:
                flag = False
                break
        if not flag:
            break
    if flag == 1:
        max_count = max(bin(i)[2:].count('1'), max_count)
print(max_count)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
li = [[-1 for i in range(n)] for j in range(n)]
for i in range(n):
    a = ni()
    for j in range(a):
        x, y = na()
        li[i][x-1] = y

ans = 0
for i in range(2 ** n):
    t_li = [-1 for i in range(n)]
    flag = False
    ct = 0
    for j in range(n):
        if ((i >> j) & 1):
            t_li[j] = 1
            ct += 1
        else:
            t_li[j] = 0
    
    for j in range(n):
        if ((i >> j) & 1):
            tmp = li[j]
            for k in range(n):
                if tmp[k] != -1:
                    if t_li[k] == tmp[k]:
                        continue
                    else:
                        flag = True
                        break
        if flag:
            break
    
    if flag is False:
        
        ans = max(ans, ct)
print(ans)

Solution (Python):
import itertools

n = int(input())
testimonials = []

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

ans = 0
for item in itertools.product([0, 1], repeat=n):
    flag = 1
    for i, testimonial in enumerate(testimonials):
        if item[i]:
            for (x, y) in testimonial:
                if item[x] != y:
                    flag = 0
                    break
    if flag:
        ans = max(ans, sum(item))

print(ans)

Solution (Python):
n = int(input())
message = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    message[i].append([int(x) for x in input().split()])
ans = 0
for i in range(2**n):
  key = [0]*n
  sub = 0
  flag = True
  for j in range(n):
    if (i >> j) & 1:
      key[j] = 1
      sub += 1
  
  for j in range(n):
    if key[j] == 0:
      continue
    for k in range(len(message[j])):
      pq = message[j][k]
      p, q = pq[0], pq[1]
      if key[p-1] == q:
        continue
      else:
        flag = False
        break
    if not flag:
      break
  
  if flag and ans < sub:
    ans = sub

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



def main():
    n = int(input())
    persons = [[input().split() for j in range(int(input()))] for i in range(n)]

    result = 0
    for i in range(1, 2 ** n):
        flg = True
        for j, answers in enumerate(persons):
            if (i >> j) & 1 == 1:
                for x, y in answers:
                    if not((i >> int(x) - 1) & 1 == int(y)):
                        flg = False
                        break

        if flg:
            result = max(result, bin(i)[2:].count("1"))

    print(result)


if __name__ == '__main__':
    main()

Solution (Python):
def honest_or_unkind(n, tests):
    max_honest = 0
    for i in range(pow(2, n)):
        i = format(i, 'b').zfill(n)
        if str(i).count('1') > max_honest:
            flag = True
            for j, v in enumerate(str(i)):
                if v == '1':
                    for t in tests[j]:
                        if str(i)[t[0]-1] != str(t[1]):
                            flag = False
            if flag:
                max_honest = str(i).count('1')
    print(max_honest)

tests = []
n = int(input())
for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
        tmp.append([int(k) for k in input().split()])
    tests.append(tmp)

honest_or_unkind(n, tests)

Solution (Python):


from itertools import product


def read_input():
    n = int(input())
    testimonies = {}

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

    return n, testimonies


def contradict(pattern, testimonies):
    for i, p in enumerate(pattern):
        if not p:
            continue
        else:
            for x, y in testimonies[i]:
                if pattern[x] != int(y):
                    return True    
    return False
            


def submit():
    n, testimonies = read_input()

    for pattern in product([True, False], repeat=n):
        if not contradict(pattern, testimonies):
            print(sum(pattern))
            break


if __name__ == "__main__":
    submit()

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

evidences = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j 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):
N = int(input())
array_xy=[[] for i in range(N)]


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




max_honest=0
for i in range(1<<N):
    
    isHonest=[False]*N
    for j in range(N):
        if ((i >> j) & 1) == 1:
            isHonest[j]=True
    


    
    ok = True
    for j in range(len(array_xy)):
        
        if isHonest[j]==False:
            continue
        
        for k in range(len(array_xy[j])):
            tmp_x = array_xy[j][k][0]
            tmp_y = array_xy[j][k][1]
            
            if  (isHonest[tmp_x-1]==True and tmp_y ==0) or \
                (isHonest[tmp_x-1]==False and tmp_y ==1):
                ok = False
        if ok == False:
            break
    if ok == True:
        
        if isHonest.count(True) > max_honest:
            max_honest = isHonest.count(True)
print(max_honest)

Solution (Python):
n = int(input())
testimony = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x,y = map(int, input().split())
        testimony[i].append((x,y))
honest = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i>>j)&1:
            for x,y in testimony[j]:
                if (i>>(x-1))&1 != y:
                    flag = False
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Solution (Python):
n = int(input())
a = [0] * n
xy = [0] * n
for i in range(n):
     a[i] = int(input())
     xy[i] = [list(map(int,input().split())) for _ in range(a[i])]
memo = [0] * (2**n)
for i in range(2**n):
     flag = True
     ch = [0]*n  
     for j in range(n):
          if ((i >> j) & 1):
               ch[n - j - 1] = 1
     for k in range(n):
          if ch[k] == 1:
               for l in range(a[k]):
                    if xy[k][l][1] == ch[xy[k][l][0] - 1]:
                         continue
                    else:
                         flag = False

     if flag:
          memo[i] = sum(ch)
print(max(memo))

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



max_count = 0

conflict = False
for i in range(2 ** n):
    conflict = False
    for j, answers in enumerate(whole_answers):
        if i >> j & 1:
            for x, y in answers:
                if (y == 1 and i >> (x - 1) & 1 == 0) or (y == 0 and i >> (x - 1) & 1 == 1):
                    
                    conflict = True
                    break
            if conflict:
                break
    if not conflict:
        count = bin(i)[2:].count('1')
        max_count = max(max_count, count)
print(max_count)

Solution (Python):
N = int(input())
human = []
for i in range(N):
    A = int(input())
    hatugen = {}
    for j in range(A):
        x, y = map(int, input().split())
        hatugen[x] = y
    human.append(hatugen)
    
cnt = 0
for i in range(2 ** N):
    is_ok = True
    for j in range(N):
        if (i >> j) & 1:
            for K, V in zip(human[j].keys(), human[j].values()):
                k = K - 1
                if V ^ ((i >> k) & 1):
                    is_ok = False
                    break
    if is_ok:
        cnt = max(cnt, bin(i).count('1'))

print(cnt)

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

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            honest[i].append(x - 1)
        elif y == 0:
            liar[i].append(x - 1)

ans = 0
for i in range(2 ** N):
    flag = True
    for j in range(N)[::-1]:
        if i >> j & 1:
            for k in honest[N - j - 1]:
                if not i >> (N - k - 1) & 1:
                    flag = False
            for k in liar[N - j - 1]:
                 if i >> (N - k - 1) & 1:
                     flag = False
            if flag is False:
                break
    if flag is True:
        ans = max(ans, bin(i).count("1"))

print(ans)

Solution (Python):
N  = int(input())
testimony = [[]for i in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1,state])
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if(i>>j)&1 == 1:
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag =1
                    break
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Solution (Python):
N  = int(input())
testimony = [[]for i in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1,state])
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if(i>>j)&1 == 1:
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag =1
                    break
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Solution (Python):
n = int(input())
lis = []
for i in range(n):
    l = []
    a = int(input())
    for j in range(a):
        x, y = map(int,input().split())
        l.append([x-1,y])
    lis.append(l)
    
ho_maxcnt = 0
for i in range(1, 2**n):
    ho_cnt = bin(i).count("1")
    if ho_cnt <= ho_maxcnt: continue
    is_ok = True
    for j in range(n):
        jhonest = (i >> j) & 1
        if jhonest == 0:
            continue
        for say in lis[j]:
            if ((i >> say[0]) & 1) ^ say[1]:
                
                is_ok = False
                break
        if not is_ok:
            break
    if not is_ok:
        continue
    if ho_cnt > ho_maxcnt:
        ho_maxcnt = ho_cnt
print(ho_maxcnt)

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

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

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        g[i][x] = y
ans = 0
for i in range(1 << n):
    d = [0] * n
    for j in range(n):
        if i >> j & 1:
            d[j] = 1

    cnt = 0
    ok = 1
    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 = 0

    if ok:
        ans = max(ans, sum(d))
print(ans)

Solution (Python):
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

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

    ans = 0
    for i in range(1 << N):
        f = True
        
        partial = int_to_list(i, N)
        for p in partial:
            for (a, b) in A[p]:
                if b == 1:
                    if not a in partial:
                        f = False
                else:
                    if a in partial:
                        f = False
        if f:
            ans = max(ans, len(partial))

    return ans

print(solve())

Solution (Python):
n = int(input())
a=[]
for i in range(n):
    len_A = int(input())
    arr = []
    for j in range(len_A):
        x,y=map(int,input().split())
        x -= 1
        arr.append((x,y))
    a.append(arr)
def is_honest(i,j):
    return (i>>j)&1

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

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



print(ans)

Solution (Python):
def bitcnt(n):
  n=(n&0x55555555)+(n>>1&0x55555555)
  n=(n&0x33333333)+(n>>2&0x33333333)
  n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f)
  n=(n&0x00ff00ff)+(n>>8&0x00ff00ff)
  n=(n&0x0000ffff)+(n>>16&0x0000ffff)
  return n
N = int(input())
xy = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    x, y = map(int, input().split())
    x -= 1
    xy[i][x] = y
r = 0
for i in range(1<<N):
  t = [i>>j&1 for j in range(N)]
  ok = True
  for j in range(N):
    if t[j]:
      for k in range(N):
        if xy[j][k] == -1:
          continue
        if xy[j][k] != t[k]:
          ok = False
          break
  if ok:
    r = max(r, bitcnt(i))
print(r)

Solution (Python):
import math
import itertools

M = 0
N = int(input())
C = list(itertools.product([0,1],repeat=N))
A = [0]*N
x = [0]*N
y = [0]*N

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


for c in C:
  
  marker = True
  for i in range(N):
    for j in range(A[i]):
      if c[i] == 1 and c[x[i][j]-1] != y[i][j]:
        
        marker = False
  if marker == True:
    M = max(M,sum(c))
  
print(M)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(1, n+1):
        for comb in combinations(range(n), i):
            yield check(set(comb))

    yield 0

print(max(main()))

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(n+1):
        for comb in combinations(range(n), i):
            yield check(set(comb))

    yield 0

print(max(main()))

Solution (Python):
import sys
input = sys.stdin.readline
from operator import eq, ne

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y

def main():
    n = int(input())
    graph = []

    for _ in range(n):
        a = int(input())
        graph.append(list(readlines(a)))

    def check(bits):
        for pre_honest, asserts in zip(bits, graph):
            if pre_honest == "0":
                continue
            for x, y in asserts:
                if bits[x] != y:
                    return -1
        
        return len([b for b in bits if b == "1"])

    for i in range(2**n-1, -1, -1):
        bit = format(i, "0{}b".format(n))
        ans = check(bit)
        if ans > -1:
            print(ans)
            return
    
    print(0)

main()

Solution (Python):










import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)


N = intinput()
dic = {}
ans = 0
true_person = 0
flag_contradiction = 0
for i in range(N):
    dic[i] = {}

for i in range(N):
    A = intinput()
    for j in range(A):
        x,y = splitintinput()
        dic[i][x-1] = y

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)
    true_person = tmp.count('1')
    flag_contradiction = 0
    for j in range(N):
        if int(tmp[j]) == 1:
            for k in dic[j]:
                if dic[j][k] != int(tmp[k]):
                    flag_contradiction = 1
                    break
    if flag_contradiction == 0:
        ans = max(ans,true_person)

print(ans)

Solution (Python):
n = int(input())
a = [0 for i in range(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]):
        xx, yy = map(int,input().split())
        x[i].append(xx)
        y[i].append(yy)
ans = 0
for i in range(2**n):
    ok = True
    for j in range(n):
        if ((1 << j) & i):
            for k in range(a[j]):
                if y[j][k] == 0:
                    if (1 << (x[j][k] - 1)) & i:
                        ok = False
                else:
                    if not((1 << (x[j][k] - 1)) & i):
                        ok = False
    if ok:
        cnt = bin(i).count('1')
        ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())
a = [0 for i in range(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]):
        xx, yy = map(int,input().split())
        x[i].append(xx)
        y[i].append(yy)
ans = 0
for i in range(2**n):
    ok = True
    for j in range(n):
        if ((1 << j) & i):
            for k in range(a[j]):
                if y[j][k] == 0:
                    if (1 << (x[j][k] - 1)) & i:
                        ok = False
                else:
                    if not((1 << (x[j][k] - 1)) & i):
                        ok = False
    if ok:
        cnt = 0
        while i:
            cnt += i & 1
            i >>= 1
        ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())
sa = []
ans = 0
for i in range(n):
    a = int(input())
    k = []
    for j in range(a):
        x,y = map(int, input().split())
        k.append([x, y])
    sa.append(k)

for b in range(2 ** n):
    f = True
    for i in range(len(sa)):
        if ((b >> i) & 1):
            for x1, y1 in sa[i]:
                if (b >> (x1-1))&1 != y1:
                    f = False
                    break
    if f:
        ans = max(ans, bin(b)[2:].count("1"))

print(ans)

Solution (Python):
import itertools 
N = int(input())
evidence_dit = {} 
for i in range(N):
    A = int(input())
    x_y = []
    if A == 0:
        evidence_dit[i] = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))        
        evidence_dit[i] = x_y 
ans = 0
attribute = [0,1] 
for i in itertools.product(attribute,repeat=N):
    flag = False    
    for j in range(N):
       if i[j] == 1:            
            for k in evidence_dit[j]:
                if i[k[0]-1] != k[1]:
                    flag = True
                    break
            if flag:
                break 
    if flag == False:
        ans = max(ans,sum(i))        
print(ans)
'''
入力:辞書型で置いておくことにした。
{0: [[2, 1], [3, 0]], 1: [[3, 1], [1, 0]], 2: [[1, 1], [2, 0]]}
証言が無い場合に [ ] を入れる。
attribute = [0,1] 
for i in itertools.product(attribute,repeat=N):
正直、不正直のパターンを列挙するところ、itertoolsで0,1の重複順列
for i in range(2 ** N):
    h = [0] * N 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
ビット演算子
i >> j　i を右に j ビットシフト
5 >> 2　5 を右に 2 ビットシフト
　　　　 101｜　➡　001｜01　➡　001
　　　　 右へ２つずらして足りなくなった桁は0にする。　
5 & 1　➡　101 AND 001　➡　001
　　　　　　両方１のところだけ１になる。
if 5 & 1:　5 & 1 の答えが１なら True、他は False
[0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] 
[0, 1, 1] [1, 1, 1]、のような0,1の全パターンを出している。
'''

Solution (Python):
'''
N人の「正直者」、「不親切な人」のすべての組み合わせを生成し、
正直者の証言が組み合わせに矛盾していないか確認する. 
矛盾していない組み合わせの正直者の最大数が解答.
組み合わせは bit で表現している. Nビット用意し、
1が立っていると正直者、0だと不親切な人. 
この組み合わせ状況と正直者の証言が矛盾しないか確認する.
'''
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):
n = int(input())
comments = []
for i in range(n):
    a = int(input())
    temp = []
    for j in range(a):
        temp.append([int(x) for x in input().split()])
        
    comments.append(temp)



max_honest = 0
for member_state in range(2**n):
    flg = False
    for member_num in range(n):
        
        if member_state & 1<< member_num :
            
            for co in comments[member_num]:
                if member_state>>(co[0] - 1) & 1 != co[1] : 
                    flg = True
                    break
        if flg == True:
            break
    else:
        
        member_num = 0
        for x in range(n):
            if member_state & 1<< x:
                member_num += 1

        if max_honest < member_num:
            max_honest = member_num

print(max_honest)