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):
from queue import Queue

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

for people_index in range(n):
    this_shogens = []
    shogen_num = int(input())
    for _ in range(shogen_num):
        this_shogens.append(tuple(map(int, input().split())))

    shogens.append(this_shogens)

def make_pattern(number):
    pattern = [0 for _ in range(n)]
    index = 0
    while True:
        if number == 0:
            break
        else:
            pattern[index] = number % 2
            number //= 2
            index += 1
    return pattern


def ok(pattern):
    hantei = [None for _ in range(n)]
    seen_list = []
    q = Queue()
    ret = True
    for people_index in range(len(pattern)):
        if pattern[people_index] == 1:
            q.put(people_index)
            hantei[people_index] = 1

    while True:
        if q.empty():
            break
        else:
            people_index = q.get()
            if people_index in seen_list:
                continue
            else:
                seen_list.append(people_index)

            this_shogens = shogens[people_index]

            for this_shogen in this_shogens:
                people_sareta_index = this_shogen[0]-1
                shogen = this_shogen[1]

                if shogen == 1 and (people_sareta_index not in seen_list):
                    q.put(people_sareta_index)

                if hantei[people_sareta_index] == None:
                    hantei[people_sareta_index] = shogen

                if shogen != hantei[people_sareta_index]:
                    ret = False
                    break

    return ret

def main():
    max_num = 0
    num_list = []
    for value in range(pow(2, n)-1, -1, -1):
        pattern = make_pattern(value)

        shojiki_count = 0
        for p in pattern:
            if p == 1:
                shojiki_count += 1

        if not shojiki_count in num_list:
            if ok(pattern):
                max_num = max(max_num, shojiki_count)
                num_list.append(shojiki_count)

    print(max_num)
main()

Solution (Python):
n = int(input())
shougen = [[] for i in range(n)]
max_num = 0

def check(li):
    co = 0
    for i in li:
        if i == '1':
            co += 1
    return co

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


for i in range(2**n):
    flag = True
    people = str(format(i, 'b').zfill(n))
    if flag == True:
        for j in range(n):
            if people[j] == '1':
                if flag is True:
                    for k in range(len(shougen[j])):
                        to_people = shougen[j][k][0] - 1
                        if str(shougen[j][k][1]) != people[to_people]:
                            flag = False
                            break
                else:
                    break
    else:
        break
    if flag is True:
        num = check(people)
    if num > max_num:
        max_num = num

print(max_num)

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

n = int(input())
bit = []
for i in range(2 ** n):
    bit.append(format(i, '0{}b'.format(n)))
bit = sorted(bit, key=lambda a: -collections.Counter(a)['1'])

say = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        say[i].append([int(i) for i in input().split()])

answer = 0
for b in bit:
    failed = False
    for i, v in enumerate(b):
        if failed:
            break
        if v == '1':
            for s in say[i]:
                if int(b[s[0] - 1]) != s[1]:
                    failed = True
                    break
    if not failed:
        answer = b
        break

print(collections.Counter(b)['1'])

Solution (Python):

import copy
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()
    xy = []
    for i in range(n):
        a = II()
        xy.append(XLMIIS(a))


    def f(a):
        i = 0
        while n != i  and a[i] != -1:
            i += 1
        if i == n:
            return 0

        b = copy.copy(a)
        b[i] = 1
        b_ans = 1
        mujun = 0
        q = deque([i])
        while len(q) != 0:
            qq = q.pop()
            for j in xy[qq]:
                if b[j[0]-1] == -1 and j[1] == 1:
                    q.append(j[0]-1)
                    b[j[0]-1] = 1
                    b_ans += 1
                elif b[j[0]-1] == -1 and j[1] == 0:
                    b[j[0]-1] = 0
                elif b[j[0]-1] != j[1]:
                    mujun = 1
                    break
        if mujun == 0:
            b_ans += f(b)
        else:
            b_ans = 0

        c = copy.copy(a)
        c[i] = 0
        c_ans = f(c)

        return max(b_ans, c_ans)


    print(f([-1]*n))







if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = []
a = []
for i in range(n):
    aa = int(input())
    a.append(aa)
    c = []
    for j in range(aa):
        xy = list(map(int,input().split()))
        c.append(xy)
    s.append(c)

sy = []
ans = 0
 
def syojiki(sy,count):
    if count == n:
     
        check = [[] for i in range(n)]
        for i in range(n):
            if sy[i] == 1:
                check[i].append(1)
        for i in range(n):
            if sy[i] == 1:
                for j in range(a[i]):
                    if s[i][j][1] not in check[s[i][j][0]-1]:
                        check[s[i][j][0]-1].append(s[i][j][1])
    
        check2 = 0
        for i in range(n):
            if len(check[i]) == 0:
                check2 += 1
            elif len(check[i]) == 1 and check[i][0] == sy[i]:
                check2 += 1
   
        if check2 == n:
            global ans
            ans = max(ans,check.count([1]))
   
    else:
        syojiki(sy+[0],count+1)
        syojiki(sy+[1],count+1)
 
syojiki(sy,0)
print(ans)

Solution (Python):
from itertools import combinations
import sys

N = int(input())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
C = [[] for _ in range(N + 1)]
num_hint = []

for i in range(1, N + 1):
    num_i = int(input())
    num_hint.append(num_i)
    for j in range(num_i):
        x, y = map(int, input().split())
        A[i].append((x, y))
        if y == 1:
            B[i].append(x)
        if y == 0:
            C[i].append(x)
        
        
        
        
        

for i in range(N + 1, 0, -1):
    for combi in combinations(range(1, N + 1), i):
        remain = set(range(1, N + 1)) - set(combi)
        s = set()
        t = set()
        hint_dict = {}
        for j in combi:
            s |= set(B[j])
            t |= set(C[j])
            for x, y in A[j]:
                if hint_dict.get(x) is None:
                    hint_dict[x] = {0: [], 1: []}
                    hint_dict[x][y].append(i)
                else:
                    hint_dict[x][y].append(i)
        good1 = True
        for value in hint_dict.values():
            if len(value[0]) != 0 and len(value[1]) != 0:
                good1 = False
                break
        good2 = True
        if len(s & remain) != 0:
            good2 = False
        good3 = True
        if len(t & set(combi)) != 0:
            good3 = False
        if good1 and good2 and good3:
            print(i)
            sys.exit()
print(0)

Solution (Python):
N = int(input())
A = list()
x = list()
y = list()

for i in range(N):
    A_tmp = int(input())
    A.append(A_tmp)
    x_tmp = list()
    y_tmp = list()
    for k in range(A_tmp):
        tmp = [int(j) for j in input().split()]
        x_tmp.append(tmp[0])
        y_tmp.append(tmp[1])
    x.append(x_tmp)
    y.append(y_tmp)

def DFS(acc_list, depth):
    if depth < N:
        acc_list[depth] = 0
        result1 = DFS(acc_list, depth+1)
        acc_list[depth] = 1
        result2 = DFS(acc_list, depth+1)
        return max(result1, result2)

    acc_dict = dict()
    for i in range(N):
        acc_dict[i] = None

    for i in range(N):
        if acc_list[i] == 1:
            for j in range(A[i]):
                if acc_dict[x[i][j]-1] == None:
                    acc_dict[x[i][j]-1] = y[i][j]
                else: 
                    if acc_dict[x[i][j]-1] == y[i][j]:
                        pass
                    else: 
                        return 0

    flag = 1
    for i in range(N):
        if acc_dict[i] == acc_list[i]:
            pass
        else:
            if acc_dict[i] == None:
                pass
            else:
                flag = 0
    if flag == 1:
        return sum(acc_list)
    else:
        return 0

acc_list = [0]*N

result = DFS(acc_list, 0)
print(result)

Solution (Python):
N = int(input())
li = list()
for i in range(N):
    Ai = int(input())
    Alist = list()
    for j in range(Ai):
        x,y = map(int,input().split())
        Alist.append([x-1,y])
    li.append(Alist)
num =(2**(N))
while True:
    ok = True
    num -=1
    numlist = format(num, 'b')
    
    zero = str()
    if N != len(numlist):
        for i in range(N-len(numlist)):
            zero += "0"

        numlist = zero + numlist
    
    for i in range(len(numlist)):
        if numlist[i] == "1":
            for j in range(len(li[i])):
                if int(numlist[li[i][j][0]]) != li[i][j][1]:
                    ok = False
                    break
        if ok == False:
            break
    if ok == True:
        print(numlist.count("1"))
        break
    if num == 0:
        print(0)
        break

Solution (Python):
import itertools
n=int(input())
tl=[[-1]*n for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        tl[i][x-1]=y
ans=0
ll=list(itertools.product(range(2),repeat=n))
for l in ll:
    for i in range(n):
        if l[i]==0:
            continue
        for j in range(n):
            if tl[i][j]<0:
                continue
            if tl[i][j]!=l[j]:
                break
        else:
            continue
        break
    else:
        ans=max(ans,sum(l))
print(ans)

Solution (Python):
import itertools

s = raw_input()
N = int(s)

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


for i in range(N):
    n = int(raw_input())
    for j in range(n):
        [x,y] = raw_input().split()
        x = int(x)
        y = int(y)
        
        A[i][x-1] = y



List = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
lst = List[0:N]


def consistency_check(lst):
    
    for i in range(N):
        if i in lst:
            continue
        for j in range(N):
            if A[i][j] == 0 and not(j in lst):
                return 0
            if A[i][j] == 1 and j in lst:
                return 0
    return 1

for i in range(N+1):
    lierlist = list(itertools.combinations(lst,i))
    for j in range(len(lierlist)):
        if consistency_check(lierlist[j]):
            print N-i
            exit (0)


print 0

Solution (Python):
N = int(input())
L = []
candidates = [list(bin(i)[2:].zfill(N)) for i in range(2**N)]

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

ans = 0
for pattern in candidates:
    tmp = 0
    flag = 1
    for j in range(N): 
        if pattern[j] == "1":
            for said in L[j]:
                if pattern[said[0] - 1] != str(said[1]):
                    flag = 0
        else:
            pass
    if flag == 1:
        ans = max(ans, pattern.count("1"))

print(ans)

Solution (Python):
import copy

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

def rec(condition, i):
  if i==N:
    return condition.count(1)
  _X = X[i]
  _condition = copy.copy(condition)
  through_condition = copy.copy(condition)
  through_condition[i] = 0
  if condition[i]==0:
    return rec(copy.copy(through_condition), i+1)
  for x in _X:
    if _condition[ x[0]-1 ] == -1:
      _condition[ x[0]-1 ] = x[1]
    elif _condition[ x[0]-1 ] != x[1]:
      return 0 if _condition[i]==1 else rec(copy.copy(through_condition), i+1)
  _condition[i] = 1
  return max(rec(copy.copy(through_condition), i+1), rec(copy.copy(_condition), i+1))

print( rec([-1 for _ in range(N)], 0) )

Solution (Python):
def popcnt(n):
    return bin(n).count("1")

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

for i in range(n):
    p = int(input())
    for j in range(p):
        array = [i] +list(map(int, input().strip().split(' ')))
        array[1] = array[1] - 1
        grid.append(array)


truth = 0
count = 0

for i in range(2**n):
    k = (bin(i)[2:]).zfill(n)
    count = 0
    for j in range(len(grid)):
        if int(k[grid[j][0]]) == 1:
            if (int(k[grid[j][1]]) == 1 and grid[j][2] == 0) or (int(k[grid[j][1]]) == 0 and grid[j][2] == 1):
                count = 1
                break
    if count == 0:
        if truth < popcnt(i):
            truth = popcnt(i)

print(truth)

Solution (Python):
n = int(input())
A = []
X_Y = [[] for _ in range(n)]

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

ans = 0


for bit in range(1<<n):
    check = str(bin(bit)).count('1')
    for i in range(n):
        
        if (bit>>i)&1 == 1 :
            
            count = 0
            for obj in X_Y[i]:
                
                if (obj[1] == 0) and (bit>>obj[0]&1 == 0):
                    count += 1
                
                elif (obj[1] == 1) and (bit>>obj[0]&1 == 1):
                    count += 1
                else:
                    pass

            
            if count == A[i]:
                check -= 1
            
            
            
    
    if check == 0:
        can = str(bin(bit)).count('1')
        
        if ans <= can:
            ans = can
print(ans)

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


ans = []
for i in range(1<<n):
    s = ''.join(str(bin(i)).replace('0b', '')).zfill(n)
    for j in range(n):
        if s[j] == '1':
            for word in xy[j]:
                if int(s[word[0]-1]) != word[1]:
                    break
            else:
                continue
            break
    else:
        ans.append(s)
        continue

cnt = 0
for x in ans:
    k = x.count('1')
    if cnt < k:
        cnt = k
print(cnt)

Solution (Python):
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
N = int(stdin.readline().rstrip())
An = []
xy = {}
count = 0
for el1 in range(N):
    ai = int(stdin.readline().rstrip())
    An.append(ai)
    Tmp = []
    for el2 in range(ai):
        tmp = [int(s) for s in stdin.readline().rstrip().split()]
        Tmp.append(tmp)
    xy[count] = Tmp
    count += 1
Checker = []
for el in range(2 ** N):
    bin(el)
    checker = list(str(bin(el)))
    del checker[0:2]
    checker = [int(s) for s in checker]
    for n in range(N - len(checker)):
        checker.insert(0, 0)
    Checker.append(checker)

res = 0
for el1 in Checker:
    pos = 0
    tes0 = []  
    tes1 = []  
    for el2 in el1:
        if el2 == 0:
            pos += 1
            continue
        else:
            tes1.append(pos)
            n = xy[pos]
            for el3 in n:
                if el3[1] == 1:
                    tes1.append(el3[0]-1)
                if el3[1] == 0:
                    tes0.append(el3[0]-1)
            pos += 1
    check = True
    for el2 in tes1:
        if (el1[el2] != 1):
            check = False

    if (len(set(tes0) & set(tes1)) == 0 and check):
        if (el1.count(1) >= res):
            res = el1.count(1)
print(res)

Solution (Python):
N = int(input())
tes_l = [[-1 for i in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(int(input())):
        target,TFflg = list(map(int,input().split()))
        tes_l[i][target-1] = TFflg 


ans = 0
flg = False
for k in range(2**N):
    tmpans = list(map(int,bin(k)[2:].zfill(N)))
    for i,eachtes in enumerate(tes_l):
        for j,tes in enumerate(eachtes):
            if(tmpans[i]==1):
                if(tes!=-1 and tmpans[j]!=tes):
                    flg = True
            """
            if(tes==0 and tmpans[i]==1):
                if(tmpans[j]==1):
                    continue
            elif(tes==1 and tmpans[i]==1):
                if(tmpans[j]==0):
                    continue
            """
    if(not flg):
        ans = max([sum(tmpans),ans])
    flg = False

print(ans)

Solution (Python):

import sys

N = int(input())

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

    witnesses.append(witness)

honest_binary = 2 ** N - 1
while (honest_binary > 0):
    honest_list = [int(i) for i in list(format(honest_binary, '0' + str(N) + 'b'))]

    
    
    flag = False
    for i in range(len(honest_list)):
        if honest_list[i] == 0:
            continue

        witness = witnesses[i]
        for w in witness:
            (x, y) = w
            if honest_list[x] != y:
                flag = True
                break
        if flag is True:
            break
    else:
        print(honest_list.count(1))
        sys.exit()

    honest_binary -= 1

print(0)

Solution (Python):
import itertools

N = int(input())

syougen_list = []
people = [-1] * N
for i in range(N):
    a_i = int(input())
    a_i_list = []
    for j in range(a_i):
        a_i_list.append(list(map(int, input().split())))
    syougen_list.append(a_i_list)


output = 0
for i in itertools.product([1,0], repeat=N):
    legal = True
    for index, j in enumerate(i):
        if j == 1:
            syougen = syougen_list[index]
            for k in syougen:
                if i[k[0] - 1] != k[1]:
                    legal = False
                    break
    if not legal:
        continue

    match = True
    honest_syougen_list = []
    for index, j in enumerate(i):
        if j == 1:
            honest_syougen_list += syougen_list[index]
    for j in honest_syougen_list:
        if people[j[0] - 1] == -1:
            people[j[0] - 1] = j[1]
        elif people[j[0] - 1] != j[1]:
            match = False
            break
    if match:
        number = i.count(1)
        if number >= output:
            output = number

print(output)

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

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

max_=0
one_hot=[[] for _ in range(n)]
for i in range(2**n):
  temp=i
  count=0
  for j in range(n):
    one_hot[j]=temp%2
    temp//=2
    if one_hot[j]==1:
      count+=1
  flg=True
  for j in range(n):
    for k in range(len(s[j])):
      if one_hot[j]==1:
        if one_hot[s[j][k][0]-1]!=s[j][k][1]:
          flg=False
          break
      if not flg:
        break
  if flg and max_<count:
    max_=count
  count=0
print(max_)

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = True

p = None
XY = None
N = None


def dfs(XY, cur, ans_list):
    if cur == N:
        
        return len([i for i in ans_list if i != 0])

    flag = True
    _ans_list = [i for i in ans_list]
    for xy in XY[cur]:
        if _ans_list[xy[0]-1] == -1 or _ans_list[xy[0]-1] == xy[1]:
            _ans_list[xy[0]-1] = xy[1]
        else:
            flag = False

    ret0 = 0
    ret1 = 0

    if flag:
        if _ans_list[cur] == -1 or _ans_list[cur] == 1:
            _ans_list[cur] = 1
            ret0 = dfs(XY, cur+1, _ans_list)

    _f_ans_list = [i for i in ans_list]
    
    if _f_ans_list[cur] == -1 or _f_ans_list[cur] == 0:
        _f_ans_list[cur] = 0
        ret1 = dfs(XY, cur+1, _f_ans_list)

    return max(ret0, ret1)


def main():
    global p
    global XY
    global N
    N = I()
    XY = [[] for i in range(N)]
    p = [[] for i in range(N+1)]

    for i in range(N):
        a = I()
        for j in range(a):
            x, y = MI()
            XY[i].append((x, y))
            p[x].append(y)

    
    print(dfs(XY, 0, [-1] * N))
    
    
    
    
    
    

    
    
    

    
    
    
    
    

    


if __name__ == '__main__':
    main()

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

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

    
    ans = 0
    flag = False
    for num in range(1, 2**n):
        num = bin(num)[2:].rjust(n, '0')
        for i in range(len(li)):
            if num[i] == '1':
                for j, key in enumerate(li[i]):
                    if num[key-1] != str(li[i][key]):
                        flag = True
                        break
                if flag:
                    flag = False
                    break
        else:
            
            ans = max(num.count('1'), ans)
    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
p = [[] for j in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij, yij = map(int, input().split())
        p[i].append([xij -1, yij])
cands = []
ans = 0
def bits(l):
    if len(l) == n:
        cands.append(l)
        return
    bits(l + [0])
    bits(l + [1])
bits([])
for cand in cands:
    f = 0
    for i, man in enumerate(cand):
        if man:
            for x, y in p[i]:
                if cand[x] != y:
                    f = 1
                    break
        if f:
            break
    if not f:
        ans = max(ans, sum(cand))
print(ans)

Solution (Python):
from sys import stdin
from collections import defaultdict
import itertools
 
d = defaultdict(list)
N = int(stdin.readline().rstrip())
p = [[0,1] for i in range(N)]
 
for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x,y = [int(x) for x in stdin.readline().rstrip().split()]
        d[i].append((x,y))
ans = 0
 
for ind,i in enumerate(itertools.product(*p)):
    cnt = 0
    flag = True
    for m in range(N):
        if i[m] == 1:
            for j,k in d[m]:
                if i[j-1] != k:
                    flag = False
            if flag:
               cnt += 1
        else:
            continue
    if flag:
       ans = max(ans,cnt)
    cnt = 0
print(ans)

Solution (Python):
N = int(input())
A = [0] * N
data = [[] for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        new = list(map(int,input().split()))
        new[0] -= 1
        data[i].append(new)

m = -1
for n in range(2**N):
    nn = n
    cur = [0] * N
    for i in range(N):
        cur[i] = nn % 2
        nn = nn // 2
    s = sum(cur)
    if s <= m:
        continue
    det = 1
    for i in range(N):
        if cur[i] == 0:
            continue
        for j in range(A[i]):
            if data[i][j][1] != cur[data[i][j][0]]:
                det = 0
                break
        if det == 0:
            break
    if det == 1:
        m = s
    


print(m)

Solution (Python):
from itertools import product

def main():
    n = int(input())
    a = []
    ls = []
    ans = 0
    for _ in range(n):
        ai = int(input())
        a.append(ai)
        ls.append([tuple(map(int, input().split())) for i in range(ai)])
    ptns = list(product([0,1], repeat=n))
    for ptn in ptns:
        flag = 0
        lsls = list(ptn)
        for j in range(n):
            if ptn[j] == 1:
                for i in range(a[j]):
                    if ls[j][i][1] == 1 and lsls[ls[j][i][0]-1] == 1:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    elif ls[j][i][1] == 0 and lsls[ls[j][i][0]-1] == 0:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    else:
                        flag = 1
        if flag == 0:
            if list(ptn) == lsls:
                if ans < sum(ptn):
                    ans = sum(ptn)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
C = []

flg = False
for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    if a:
        flg=True
    C.append(comment)
if not flg :
    print(N)
    exit()


def bit_tbl2(length):
    _format = "{:0" + str(length) + "b}"
    for i in range(int('1' * length, 2) + 1):
        yield _format.format(i)


ans = 0
for b in bit_tbl2(N):
    
    syo = [-1] * (N + 1)
    flg = False

    for i in range(N):
        if b[i] == '1':
            syo[i+1] = 1

    for i in range(N):
        if b[i] != '1': continue

        for x, y in C[i]:
            if y == 1 and syo[x] != 1:
                flg = True
                break
            if syo[x] != -1 and y != syo[x]:
                flg = True
                break
            syo[x] = y

        if flg: break

    if not flg:

        v = 0
        for x in syo:
            if x == 1: v += 1
        

        ans = max(ans, v)
print(ans)

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

word = []

for i in range(N):
  A = int(input())
  B = []
  for i in range(A):
    x = list(map(int, input().split()))
    B.append(x)
  word.append(B)
answer = 0
for i in range(2**N):
  check = True
  a = format(i, 'b').zfill(N)
  count = 0
  for j in range(len(a)):
    if a[j] == "1":
      count += 1
      for x, y in word[j]:
        if not int(a[x-1]) == y:
          check = False
  if check == True:
    answer = max([answer, count])
print(answer)

Solution (Python):
N = int(input())
A = [0] * N
B = []
for n in range(N):
    A[n] = int(input())
    bn = []
    for i in range(A[n]):
        x, y = map(int, input().split())
        bn.append((x-1, y))
    B.append(bn)

ans = 0

for bit in range(1 << N):
    ok = [False] * N
    for n in range(N):
        if ((bit >> n) & 1) == 1:
            if all([((bit >> B[n][i][0]) & 1) == B[n][i][1] for i in range(A[n])]):
                ok[n] = True
        else:
            ok[n] = True
    if all(ok):
        ans = max(ans, sum(list(map(int, format(bit, "b")))))

print(ans)

Solution (Python):
from itertools import product

def main():
    n = int(input())
    a = []
    ls = []
    ans = 0
    for _ in range(n):
        ai = int(input())
        a.append(ai)
        ls.append([tuple(map(int, input().split())) for i in range(ai)])
    ptns = list(product([0,1], repeat=n))
    for ptn in ptns:
        flag = 0
        lsls = list(ptn)
        for j in range(n):
            if ptn[j] == 1:
                for i in range(a[j]):
                    if ls[j][i][1] == 1 and lsls[ls[j][i][0]-1] == 1:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    elif ls[j][i][1] == 0 and lsls[ls[j][i][0]-1] == 0:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    else:
                        flag = 1
        if flag == 0:
            if list(ptn) == lsls:
                if ans < sum(ptn):
                    ans = sum(ptn)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
n = int(input())
a_dict = {i : {0 : [i], 1:[]} for i in range(n)}
for i in range(n):
    a = int(sys.stdin.readline().strip())
    for j in range(a):
        x, y = [int(i) for i in sys.stdin.readline().split()]
        x -= 1
        if y == 1:
            a_dict[i][0].append(x)
        else:
            a_dict[i][1].append(x)
best = 0
for i in range(1 << n):
    true_set = set()
    false_set = set()
    _i = bin(i)[2:].zfill(n)
    for j, k in enumerate(_i[::-1]):
        if k == "1":
            t = a_dict[j][0]
            f = a_dict[j][1]
            if true_set.intersection(set(f)) or false_set.intersection(set(t)):
                true_set = {}
                break
            true_set.update(t)
            false_set.update(f)
    res = "".join(["0" if i not in true_set else "1" for i in range(n)])[::-1]
    res = len(true_set) if res == _i else 0
    best = max(best, res)
print(best)

Solution (Python):

N = int(input())
anslist = []
ret = []
for i in range(N):
    A = int(input())
    tmp = []
    for j in range(A):
        X = list(input().split())
        tmp.append(X)
    anslist.append(tmp)

for i in range(2**N):
    ans = 0
    op = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            op.append("1")
        else:
            op.append("0")
    
    flag = 0
    for j in range(N):
        if op[j] == "1":
            for k in anslist[j]:
                if op[int(k[0])-1] != k[1]:
                    flag = 1
    if flag == 0:
        ret.append(op.count("1"))

print(max(ret))