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 unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([[[2, 1]], [[1, 1]], [[2, 0]]]), 2)

    def test_2(self):
        self.assertEqual(think([[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]), 0)

    def test_3(self):
        self.assertEqual(think([[[2, 0]], [[1, 0]]]), 1)

    def test_4(self):
        self.assertEqual(count_bits_one(1), 1)

    def test_5(self):
        self.assertEqual(count_bits_one(2), 1)

    def test_6(self):
        self.assertEqual(count_bits_one(3), 2)

    def test_7(self):
        self.assertEqual(count_bits_one(31), 5)


def solve():
    list_of_testimony = read()
    result = think(list_of_testimony)
    write(result)


def read():
    n = read_int(1)[0]
    list_of_testimony = []
    for _ in range(n):
        list_of_x_y = []
        a = read_int(1)[0]
        for __ in range(a):
            list_of_x_y.append(read_int(2))
        list_of_testimony.append(list_of_x_y)
    return list_of_testimony


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(data):
    max_bits = 2 ** len(data)
    result = 0
    for bits in range(max_bits):
        
        if is_legal(bits, data):
            result = max(result, count_bits_one(bits))
    return result


def is_legal(bits, data):
    n = len(data)
    for i in range(n):
        if not is_honest(i, bits):
            continue
        for x, y in data[i]:
            if y == 1:
                if not is_honest(x - 1, bits):
                    return False
            else:
                if is_honest(x - 1, bits):
                    return False
    return True


def is_honest(i, bits):
    
    return (bits >> i) % 2 == 1


def count_bits_one(bits):
    count = 0
    while bits > 0:
        if bits % 2 == 1:
            count += 1
        bits //= 2
    return count


def write(result):
    print(result)


if __name__ == '__main__':
    
    solve()

Solution (Python):
def get_switch(n):
    allswitch = []
    for i in range(0,2**n):
        bin_str = format(i,'0'+str(n)+'b')
        swt = list(map(int,list(bin_str)))
        allswitch.append(swt)
    return allswitch

def test(patarn,a,x,y,n):
    ans_sub=sum(patarn)
    for i in range(n):
        if patarn[i]==1:
            for j in range(a[i]):
                if y[i][j]==1:
                    if patarn[x[i][j]]==0:
                        return 0
                else:
                    if patarn[x[i][j]]==1:
                        return 0
        
            
            
                
    
    return ans_sub
    
def main():
    n=int(input())
    a=[]
    x=[]
    y=[]
    for i in range(n):
        a_sub=int(input())
        a.append(a_sub)
        x_sub=[]
        y_sub=[]
        for j in range(a_sub):
            tmp=list(map(int,input().split()))
            x_sub.append(tmp[0]-1)
            y_sub.append(tmp[1])
        x.append(x_sub)
        y.append(y_sub)
    
    
    ans=0
    for patarn in get_switch(n):
        ans=max(ans,test(patarn,a,x,y,n))
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import math
import queue
import bisect
import heapq
import time
import itertools

mod = 1e9+7
global a,n,xy,ans

def swap(a,b):
    return (b,a)

def gcd(a,b): 
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): 
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): 
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): 
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn


def func():
    global a,n,xy,ans
    count = 0
    for i in range(n):
        for j in xy[i]:
            if a[i]:
                if a[j[0]]!=j[1]:
                    return
        if a[i]:
            count += 1
    ans = max(ans,count)

def dfs(pos):
    global n
    if pos==n:
        func()
        return
    a[pos] = 0
    dfs(pos+1)
    a[pos] = 1
    dfs(pos+1)

def main():
    global a,n,xy,ans
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([])
        for j in range(a):
            x,y = map(int,input().split())
            xy[i].append([x-1,y])
    a = [0 for i in range(n)]
    ans = 0
    dfs(0)
    print(ans)
    return

if __name__=='__main__':
    main()

Solution (Python):
from itertools import product
n = int(input())
li = list(product([1,0], repeat=n))
A = [[]] * n
for i in range(n):
  a = int(input())
  A[i] = [list(map(int, input().split())) for _ in range(a)]
  
cnt = 0
for i in li:
  flg = False
  for itr, val in enumerate(i):
    if val == 1:
      if not all([i[x[0]-1] == x[1] for x in A[itr]]):
        flg = True
        break
  if flg == False:
    cnt = max(cnt, sum(i))
print(cnt)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bit_count(i):

    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
A = []
for i in range(N):
    a = []
    for j in range(INT()):
        x, y = MAP()
        a.append((x-1, y))
    A.append(a)

def check(a):
    for x, y in a:
        if honest[x] == -1:
            honest[x] = y
            if y == 1:
                if not check(A[x]):
                    return False
        elif honest[x] != y:
            return False
    return True

ans = 0
for S in range(1<<N):
    honest = [-1] * N
    valid = True
    for i in range(N):
        if S & (1<<i):
            honest[i] = 1
    for i in range(N):
        if S & (1<<i):
            if not check(A[i]):
                valid = False
    if valid:
        ans = max(ans, bit_count(S))
print(ans)

Solution (Python):
def f(s):
    cnt=0
    for i in range(len(s)):
        if s[i]=="1":
            cnt+=1
    return cnt
n=int(input())
a=[0]*n
x=[0]*n
for i in range(n):
    a[i]=int(input())
    x[i]=[list(map(int,input().split())) for j in range(a[i])]
    for j in range(a[i]):
        x[i][j][0]-=1

b=2**n
s = [bin(i)[2:] for i in range(b)]
for i in range(b):
    s[i]='0'*(n-len(s[i]))+s[i]
    s[i]=s[i][::-1]
ans=0

for i in range(b):
    cnt=0
    z=False
    for j in range(n):
        if s[i][j]=="1":
            for k in range(a[j]):
                if int(s[i][x[j][k][0]])!=x[j][k][1]:
                    z=True
                    break
            if z:
                break
        if j==n-1:
            cnt=f(s[i])
    ans=max(ans,cnt)
print(ans)

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


def check(a):
  for i in range(N):
    if a[i] == 0:
      continue
    for x, y in xy[i]:
      if a[x-1] != y:
        return -1
  return a.count(1)

r = 0
for i in range(2**N):
  bstr = format(i, '0%db' % N)
  a = tuple(map(int, bstr))
  
  t = check(a)
  if t > r:
    r = t 
print(r)

Solution (Python):
import sys

N = int(input())
evid_lst = []
for i in range(N):
    tmp_a = int(input())
    tmp_lst = []
    for j in range(tmp_a):
        tmp_lst.append(tuple(map(int, input().split())))
    evid_lst.append(tmp_lst)

honest_sets = []
for i in range(2 ** N - 1, 0, -1):
    honest_expect = set()
    for j in range(N):
        if ((i >> j) & 1):
            honest_expect.add(j + 1)
    honest_sets.append(honest_expect)

honest_sets.sort(key=lambda x: -len(x))
for h in honest_sets:
    flag = False
    for i in h:
        for evid in evid_lst[i - 1]:
            if evid[1] == 0:
                if evid[0] in h:
                    flag = True
                    break
            else:
                if not evid[0] in h:
                    flag = True
                    break
        if flag:
            break
    if not flag:
        print(len(h))
        sys.exit()
print(0)

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

xy = []
a_list = []

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



num = 2**n
hito = []
flag = True

for i in reversed(range(num)):
    
    hito = []
    tmp = i
    while tmp != 0:
        if tmp % 2 == 1:
            hito.append(1)
        else:
            hito.append(0)
        tmp //= 2
    """
    if len(hito) == 2:
        hito.append(0)
    elif len(hito) == 1:
        hito.append(0)
        hito.append(0)
    elif len(hito) == 0:
        hito.append(0)
        hito.append(0)
        hito.append(0)
    """
    if len(hito) != n:
        for j in range(n-len(hito)):
            hito.append(0)
    
    hito = hito[::-1]
    
    
    number = 0
    flag = True
    
    
    for j in range(n):
        
        for k in range(a_list[j]):
            
            if hito[j] == 1:
                
                if hito[xy[number][0]-1] != xy[number][1]:
                    flag = False
            number += 1
    if flag == True:
        print(sum(hito))
        exit()
        
print(0)
exit()

Solution (Python):
import itertools as it

N = int(input())
xy = []
for i in range(N):
    A_i = int(input())
    xy_i = []
    for j in range(A_i):
        tmp = [int(i) for i in input().split()]
        xy_i.append(tmp)
    xy.append(xy_i)
ans = 0
for conf in it.product(range(2), repeat=N):
    is_consist = True
    
    for i in range(N):
        if conf[i] == 0:
            continue
        
        for jth_state in range(len(xy[i])):
            if xy[i][jth_state][1] != conf[xy[i][jth_state][0] - 1]:
                is_consist = False
                break
    if is_consist:
        ans = max(ans, sum(conf))
print(ans)

Solution (Python):
import sys
n = int(input())
a = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    j = int(input())
    for s in range(j):
        x, y = map(int, input().split())
        a[i][x-1] = y
r = 0
for i in range(2**n):
    s = bin(i)
    t = s[2:]
    t = t.rjust(n, '0')
    c = 1
    for j in range(n):
        if t[j] == '0':
            continue
        else:
            for p in range(n):            
                    if int(t[p]) == a[j][p] or a[j][p] == -1:
                        continue
                    else:
                        c = 0
                        break
    if c:
        r = max(r, sum(map(int, list(t))))
print(r)

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

p = [[] for _ in range(n)]

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

ans = 0

for i in range(2 ** n):
    a = [0]*n
    for j in range(n):
        if ((i>>j) & 1):
            a[j] = 1
    chk = 0
    for j in range(n):
        if a[j] != 1:
            continue
        else:
            if not all(a[s[0]] == s[1] for s in p[j]):
                chk = 1
    if chk != 1:
        ans = max(ans,sum(a))

print(ans)

Solution (Python):
n=int(input())
root=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        root[i].append((x-1,y))
k=2**n
h=[0]*n
idx=0
for i in range(k):
    buf=i
    flag=True
    
    for j in range(n):
        h[j]=buf%2
        buf=buf//2
    for j in range(n):
        if h[j]==1:
            for x,y in root[j]:
                if h[x]!=y:
                    flag=False
                    break
        if flag==False:
            break
    if flag==True:
        idx=max(idx,sum(h))

print(idx)

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

S=[ [] * 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())
    
    S[i].append([x-1,y])

ans=0
P=[0]*N

for i in range(2**N):
  tmp=0
  for j in range(N):
    if P[j]==0:
      P[j]=1
      break
    else:
      P[j]=0
  
  if sum(P)<=ans:
    continue
  flag=0
  for p in range(len(P)):
    if P[p]==1:
      for s in S[p]:
        if s[1]!=P[s[0]]:
          flag=1
  if flag==1:
    continue
  else:
    ans=sum(P)
print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
XY = []

for i in range(N):
    alen = I()
    tmp = [-1] * N

    for j in range(alen):
        x, y = LI()
        tmp[x - 1] = y

    XY.append(tmp)

ret = 0
for i in range(2 ** N):
    if i == 0:
        continue

    ans = [(i >> j) & 1 for j in range(N)]
    
    flag = True
    for e, a in enumerate(ans):
        if a != 1:
            continue

        for b, c in zip(XY[e], ans):
            if b == -1:
                continue
            if b!= c:
                flag = False
        
    if flag:
        ttt = 0
        for d in ans:
            if d == 1:
                ttt += 1
        ret = max(ret, ttt)

print(ret)

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

max_honesty = 0
for i in range(2 ** n):
    num = bin(i + 2 ** n)[3:]
    honest = 0
    flag = True
    for j in range(len(num)):
        if num[j] == "0":
            continue
        else:
            for k in range(len(xy[j])):
                if int(num[xy[j][k][0] - 1]) == xy[j][k][1]:
                    continue
                else:
                    flag = False
                    break
            if flag == True:
                honest += 1
    if flag == True:
        max_honesty = max(max_honesty, honest)
print(max_honesty)

Solution (Python):
n = int(input())
x = [None] * n
y = [None] * n
for i in range(n):
    a = int(input())
    x[i] = [0] * a
    y[i] = [0] * a
    for j in range(a):
        x[i][j], y[i][j] = map(int, input().split())
ans = 0
for i in range(2 ** n):
    a = [-1] * n
    cnt = 0
    for j in range(n):
        tmp = (i >> j) & 1
        cnt += tmp
        if tmp == 1:
            for p, q in zip(x[j], y[j]):
                if ((i >> (p - 1)) & 1) != q:
                    break
                a[p - 1] = q
            else:
                continue
            break
    else:
        for j in range(n):
            tmp = (i >> j) & 1
            if a[j] != -1 and a[j] != tmp:
                break
        else:
            ans = max(ans, cnt)
print(ans)

Solution (Python):
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())))

ans = 0
for bits in range(2**N):
  l = [0] * N
  for i in range(N):
    l[i] = (bits >> i) % 2

  fail = False
  for i in range(N):
    if fail: break
    if l[i] == 0: continue 
    for x, y in A[i]:
      if y != l[x-1]:
        fail = True
        break
  else:
    if not fail:
      ans = max(ans, sum(l))

print(ans)

Solution (Python):
from itertools import product

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

ans = 0
for C in product([0,1], repeat=N):
  if sum(C) <= ans:
    continue
  for i, c in enumerate(C):
    if c:
      for x, y in XY[i]:
        if C[x-1] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans, sum(C))

print(ans)

Solution (Python):
from itertools import combinations
from collections import defaultdict


N = int(input().strip())

Pos = defaultdict(set)
Neg = defaultdict(set)
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().strip().split())
        if y == 1:
            Pos[i + 1].add(x)
        else:
            Neg[i + 1].add(x)


def check(positive):
    positive_set = set(positive)
    for x in positive_set:
        if len(Pos[x] - positive_set) != 0:
            return False
        if len(Neg[x].intersection(positive_set)) != 0:
            return False
    return True


people_list = list(range(1, N + 1))
ans = 0
for i in range(N, 0, -1):
    positives = combinations(people_list, i)
    for p in positives:
        if check(p):
            ans = i
            break
    if ans > 0:
        break

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = []
    for i in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            x, y = list(map(int, input().split()))
            xy.append([x, y])
        A.append(xy)

    
    P = []
    for i in range(2 ** N):
        b = format(i, 'b').zfill(N)
        P.append(b)

    ans = 0  
    for p in P:
        bits = list(p)  
        t = list(p)
        mujun = False
        for i, b in enumerate(bits):
            if b == '1':
                ss = A[i]  
                for x, y in ss:  
                    if t[x-1] == str(y):
                        pass
                    else:
                        mujun = True
        if not mujun:
            syojiki = bits.count('1')
            ans = max(ans, syojiki)

    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):






from sys import stdin,setrecursionlimit










setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
info=[]
num=[]
ans=0
for _ in range(n):
    a=int(input().rstrip())
    num.append(a)
    x=[tuple(map(int,input().split())) for _ in range(a)]
    info.append(x)
for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    now=s.count("1")
    check=[bool(int(ii)) for ii in s]
    ch=True
    for j in range(n):
        if (not ch) or (not check[j]): continue
        for k in range(num[j]):
            if check[info[j][k][0]-1]!=bool(info[j][k][1]):
                ch=False
                break
    if ch:
        ans=max(ans,now)
print(ans)

Solution (Python):
N = int(input())
x = []
y = []

x.append([])
y.append([])
for i in range(N):
    A = int(input())
    xtmp = []
    ytmp = []
    for _ in range(A):
        xx, yy = [int(x) for x in input().split()]
        xtmp.append(xx)
        ytmp.append(yy)
    x.append(xtmp)
    y.append(ytmp)

num_honest = 0

for i in range(2**N):
    is_honest_inv = '{:015b}'.format(i) + '0' 
    is_honest = [int(is_honest_inv[15-i]) for i in range(N+1)]
    
    is_ok = True
    for j in range(1, N+1):
        for xx, yy in zip(x[j], y[j]):
            
            if is_honest[j] == 1:
                if is_honest[xx] != yy:
                    is_ok = False
                    break
        if not is_ok:
            break
    if is_ok:
        num_honest = max(num_honest, sum(is_honest))
        
print(num_honest)

Solution (Python):
N = int(input())
A = []
for i in range(N):
  A.append([])
  A_tmp = int(input())
  for j in range(A_tmp):
    XY = [int(k) for k in input().split()]
    XY[0]-=1
    A[i].append(XY)

ans = 0


for i in range(2**N):
  bin_i_list = [int(x) for x in '{:0=15b}'.format(i)]
  bin_i_list.reverse()
  bin_i_list = bin_i_list[:N]
  judge = True
  
  for j in range(len(A)):
    if bin_i_list[j] != 0:
      for XY in A[j]:
        X =XY[0]
        Y =XY[1]
        if bin_i_list[X] != Y:
          judge = False
          break
  if judge:
    ans = max(ans,bin_i_list.count(1))

print(ans)

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

E = []

for n in range(N):
    A = int(input())
    for _ in range(A):
        x, y = list(map(int, input().split()))
        E.append((n, x-1, y))

ans = 0
for k in range((1<<N)-1, -1, -1):
    l = [(k>>i)&1 for i in range(N)]
    OK = True
    for e0, e1, e2 in E:
        if (l[e0]==1 and l[e1]!=e2):
            OK = False
            break
    if OK: ans = max(ans, sum(l))

print(ans)

Solution (Python):






from sys import stdin,setrecursionlimit










setrecursionlimit(10**6)
input=stdin.readline

n=int(input().rstrip())
info=[]
num=[]
ans=0
for _ in range(n):
    a=int(input().rstrip())
    num.append(a)
    x=[tuple(map(int,input().split())) for _ in range(a)]
    info.append(x)

for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    now=s.count("1")
    check=[bool(int(ii)) for ii in s]
    ch=True
    for j in range(n):
        
        if (not ch) or (not check[j]): continue
        for k in range(num[j]):
            
            if check[info[j][k][0]-1]!=bool(info[j][k][1]):
                ch=False
                break
    
    if ch:
        ans=max(ans,now)
print(ans)

Solution (Python):
from itertools import product

N=int(input())

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

s=[0,1]
lis=list(product(s,repeat=N))

L=len(lis)
ans=0
for i in range(L): 
    f=True
    for j in range(N):
        if lis[i][j]==1:
            for k in range(len(P[j])):
                if P[j][k][1]==lis[i][P[j][k][0]]:
                    continue
                else:
                    f=False
                    break
            if f==False:
                break
    if f:
        cnt=lis[i].count(1)
        ans=max(ans,cnt)

print(ans)

Solution (Python):
import sys
from itertools import islice
read = map(int, sys.stdin.read().split())

N = next(read)
candidates = [format(i, 'b').zfill(N) for i in range(2 ** N)]
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
    A[i] = next(read)
    xy[i].extend(list(islice(read, A[i] * 2)))

answer = 0

for candidate in candidates:
    tmp = 0
    truth = set()
    false = set()
    for k in range(N):
        if candidate[k] == '1':
            if k in false:
                break
            truth.add(k)
            for i, j in zip(*[iter(xy[k])] * 2):
                i -= 1
                if j == 1:
                    if i in false:
                        break
                    truth.add(i)
                else:
                    if i in truth:
                        break
                    false.add(i)
            else:
                continue
            break
        else:
            if k in truth:
                break
            false.add(k)
    else:
        if len(truth) > answer:
            answer = len(truth)

print(answer)

Solution (Python):
N = int(input())
d = [-1] * N
a = []
x = [[0, 0] for _ in range(N)]
cnt = 0
def dfs(v):
    global cnt
    if v == N:
        cntF = True
        for i in range(N):
            if d[i] != 1:
                continue
            for j in range(len(a[i])):
                if a[i][j][1] != d[a[i][j][0] - 1]:
                    cntF = False
                    break
            if cntF == False:
                break

        if cntF:
            cnt = max(cnt, sum(d))
        return

    d[v] = 0
    dfs(v + 1)
    d[v] = 1
    dfs(v + 1)
    return

for i in range(N):
    tmp = int(input())
    tmplst = [[0, 0] for _ in range(tmp)]
    for j in range(tmp):
        x1, y1 = map(int, input().split())
        tmplst[j][0] = x1
        tmplst[j][1] = y1
    a.append(tmplst)
dfs(0)
print(cnt)

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

ans = 0
for i in range(2**N):
    flag = False
    cnt = 0
    bit = bin(i)[2:].zfill(N)
    memo2 = [int(b) for b in bit]
    
    for ii, b in enumerate(memo2):
        cnt += b
        if b:
            for x, y in memo[ii]:
                if memo2[x] == y:
                    continue
                else:
                    flag = True
                    break
        else:
            continue
            
            
            
            
            
            
        if flag:
            break
    if flag:
        continue
    ans = max(ans, cnt)
print(ans)

Solution (Python):
n = int(input())
A = [0]*n
for i in range(n):
  a = int(input())
  A[i] = [ tuple(map(int, input().split())) for _ in range(a) ]
ans = 0
for i in range(2**n):
  P = [2]*n
  f = False
  for j in range(n):
    if i >> j & 1:
      if P[j] != 2 and P[j] ^ 1:
          f = True
          break
      P[j] = 1
      for x, y in A[j]:
        if P[x-1] != 2 and P[x-1] ^ y:
          f = True
          break
        P[x-1] = y
  if f:
    continue
  c = bin(i).count("1")
  if P.count(1) <= c:
    ans = max(ans, c)
print(ans)

Solution (Python):
N = int(input())
dh = [[] for i in range(N)]
du = [[] for i in range(N)]
for i in range(N):
    t = int(input())
    for j in range(t):
        x, y = map(int, input().split())
        if y == 1: dh[i].append(x-1)
        else: du[i].append(x-1)

best = 0
def check(bitmask):
    global best
    isH = [False for i in range(N)]
    isU = [False for i in range(N)]
    
    for i in range(N):
        if bitmask % 2:
            isH[i] = True
        else:
            isU[i] = True
        bitmask //= 2
    
    valid = True
    for i in range(N):
        if isU[i]: continue
        for t in dh[i]:
            if isU[t]: valid = False
        for t in du[i]:
            if isH[t]: valid = False

    if valid: best = max(best, sum(isH))

for i in range(pow(2, N)): check(i)

print(best)

Solution (Python):
n=int(input())
s=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    s[i].append(list(map(int,input().split())))
for i in range(2**n)[::-1]:
  cnt=format(i,"b").zfill(n)
  flag=0
  for j in range(n):
    if cnt[j]=="0":
      continue
    else:
      for h in s[j]:
        if int(cnt[h[0]-1])^h[1]==1:
          flag=1
          break
      if flag:
        break
  if flag==0:
    print(cnt.count("1"))
    exit()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
A = [[] for i in range(N)]

def check(target):
    one_count = 0
    cans = 0
    for idx, flag in enumerate(target):
        if flag == "1":
            one_count += 1
            for x, y in A[idx]:
                if int(target[x]) != y:
                    return 0
    
    cans = max(cans, one_count)
    return cans

def dns(S):
    ans = 0
    if len(S) == N:
        ans = max(ans, check(S))
    else:
        ans = max(dns(S+"0"), dns(S+"1"))
    
    return ans

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

kotae = dns("")

print(kotae)

Solution (Python):

import sys
from itertools import combinations

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n = _i()
xy = list()
for _ in range(n):
    tmp = []
    for _ in range(_i()):
        x,y = _ia()
        tmp.append((x-1,y))
    xy.append(tmp)

a = set(range(n))
for f in range(n+1):
    for p in combinations(range(n),f):
        h = a - set(p)
        tmp = [ None ] * n
        flag = True
        for i in h:
            if not i in h: continue
            for x,y in xy[i]:
                if y==1 and x not in h:
                    flag = False
                    break
                if y==0 and x in h:
                    flag = False
                    break
                
                tx = tmp[x]
                if tx is None:
                    tmp[x] = y
                else:
                    if tx==y: continue
                    else:
                        flag = False
                        break
            
            if not flag: break
        if flag:
            print(n-f)
            exit()

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

mh,h = 0,0
f = True

for i in range(2**n):
    
    p = bin(i)
    p = p[2:].zfill(n)
    h = p.count("1")
    f = True
    for j in range(n):
        
        if (p[j] == "1"):
            
            for k in range(a[j]):
                
                if (y[j][k] != int(p[x[j][k]])):
                    
                    f = False
    if (f):
        if (mh < h):
            mh = h

print(mh)