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):
n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x = list(map(int, input().split()))
        a[i].append(x)
ans = 0
for i in range(2 ** n):
    i_str = format(i, '0' + str(n) + 'b')
    flag = False
    z = [-1 for _ in range(n)]
    h = []
    for j in range(n):
        if i_str[j] == '1':
            h.append(j)
    for j in h:
        for x, y in a[j]:
            if z[x - 1] >= 0 and z[x - 1] != y:
                flag = True
                break
            elif z[x - 1] < 0:
                z[x - 1] = y
        if flag:
            break
    else:
        for zj, sj in zip(z, i_str):
            if zj >= 0 and zj != int(sj):
                flag = True
                break
    if not flag:
        ans = max(ans, sum(map(int, i_str)))
print(ans)

Solution (Python):
import sys


def main():
    
    N = int(input())

    test = [dict() for _ in range(N)]

    count = 0

    for i in range(N):
        M = int(input())
        for _ in range(M):
            j, b = map(int, input().split())
            test[i][j-1] = bool(b)

    for i in range(2**N):
        bit = format(i, 'b')
        bit = '0' * 15 + bit
        bit = bit[-N:]

        honest = set()
        liar = set()
        for i, s in enumerate(bit):
            if s == '1':
                honest.add(i)
            else:
                liar.add(i)

        m = len(honest)
        for j in honest:
            for g, r in test[j].items():
                if r and g in liar:
                    m = 0
                elif not r and g in honest:
                    m = 0

        count = max(count, m)
    print(count)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
table = [[-1]*(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())
        table[i][x-1] = y



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

    hito = [0]*N
    for j in range(N):
        if i >> j & 1:
            hito[j] = 1

    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            for k in range(N):
                if table[j][k] != -1:
                    if table[j][k] != hito[k]:
                        flag = False
    if flag:
        if cnt > ans:
            ans = cnt
print(ans)

Solution (Python):
N = int(input())
T = [[]for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        t = list(map(int,input().split()))
        T[i].append(t)
S = []
for i in range(2**N):
    f = 1
    for j in range(N):
        for k in range(len(T[j])):
            x = T[j][k][0]-1
            y = T[j][k][1]
            if (i>>j)&1:
                if ((i>>x)&1)^y:
                    f = 0
    if f == 1:
        S.append(i)
n = len(S)
m = 0
for i in range(n):
    s = S[i]
    a = 0
    for j in range(N):
        if (s>>j)&1:
            a += 1
    m = max(a,m)
print(m)

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

def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res

ans = 0
patterns = power2(N)
for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):
        if p[i] == 0: 
            pass
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: 
                    flag = False 
                    break
                
    if flag: 
        ans = max(ans, p.count(1))

print(ans)

Solution (Python):
def bin_(n):
    return str(bin(n))[2: ]

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

start = 2**N-1
max_ = 0
for i in range(2**N):
    num = i
    uso = 0
    
    keta=bin(num)[2:]
    
    while(len(keta)<N):
        keta = "0"+keta
    for j in range(N):
        if(keta[j]=="1"):
            for p in range(len(syougen[j])):
                
                x,y = syougen[j][p]
                if(keta[x] != str(y)):
                    uso = 1
                    break
    
    suuji = str(bin(num))[2:]
    count  = 0
    for i in range(len(suuji)):
        if(suuji[i]=="1"):
            count += 1
            
    if(uso==0):
        max_ = max(max_,count)
        
print(max_)

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

def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res

ans = 0
patterns = power2(N)
for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):
        if p[i] == 0: 
            pass
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: 
                    flag = False 
                    break
                
    if flag: 
        ans = max(ans, p.count(1))

print(ans)

Solution (Python):
n = int(input())
a = list()
xy = list()
for i in range(n):
  A = int(input())
  XY = [tuple(map(int, input().split())) for i in range(A)]
  a.append(A)
  xy.append(XY)
honest = [None] * n
ans = 0
for i in range(2 ** n-1,-1,-1):
  mini_ans = 0
  honest = []
  for j in range(n):
    honest.append(i % 2)
    i = i // 2
  for k,v in enumerate(honest):
    if v:
      mini_ans += 1
      for x,y in xy[k]:
        x -= 1
        if honest[x] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans,mini_ans)
    continue
print(ans)

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

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

max_kind = 0
for i in range(2**n):
    state = str(format(i, 'b').zfill(n))
    flag = True
    for j in range(n):

        if (i >> j) & 1:
            for statement in claim[j]:
                person, type = statement

                if int(state[len(state)-person]) != type:
                    flag = False
                    break
        if flag != True: break
    if flag:
        max_kind = max(max_kind, list(state).count('1'))
print(max_kind)

Solution (Python):

"""
Created on Sun Dec  8 21:12:35 2019

@author: over-
"""

N=int(input())
A=dict()
x=dict()
y=dict()
for i in range(1,N+1):
    A[i]=int(input())
    x[i]=dict()
    y[i]=dict()
    for j in range(A[i]):
        a1,a2=map(int,input().split())
        x[i][j+1]=a1
        y[i][j+1]=a2

C=2**N
ans=0
for c in range(C):
    honest=[]
    unkind=[]
    B='{:0b}'.format(c)
    B='0'*(N-len(B))+B
    bool=True
    for i in range(N):
        if int(B[i])==0:
            honest.append(i+1)
        else:   
            unkind.append(i+1)
        
    for k in range(1,N+1):
        if k in honest:
            for j in range(A[k]):
                if y[k][j+1]==1:
                    if x[k][j+1] in unkind:
                        bool=False
                else:
                    if x[k][j+1] in honest:
                        bool=False
    if bool: 
        if len(honest) > ans:
            ans= len(honest)
                        
print(ans)

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

def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res

ans = 0
patterns = power2(N)
for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):
        if p[i] == 0: 
            continue
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: 
                    flag = False 
                    break
                
    if flag: 
        ans = max(ans, p.count(1))

print(ans)

Solution (Python):
def c_honest_or_unkind_2():
    N = int(input())
    Answers = []
    for _ in range(N):
        a = int(input())
        Answers.append([[int(i) for i in input().split()] for j in range(a)])

    ret = -1
    for bits in range(1 << N):
        honests = set()
        for k in range(N):
            if (bits >> k) & 1 == 1:
                honests.add(k)

        is_contradict = False
        for k, answer in enumerate(Answers):
            if k not in honests:
                continue  

            for x, y in answer:
                x -= 1
                
                if (y == 0 and x in honests) or (y == 1 and not x in honests):
                    is_contradict = True
                    break
            if is_contradict:
                break  
        else:
            
            ret = max(ret, len(honests))
    return ret

print(c_honest_or_unkind_2())

Solution (Python):
import itertools

N = int(input())

syougen_list = []
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:
                break
    if legal:
        number = i.count(1)
        if number >= output:
            output = number

print(output)

Solution (Python):
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
import bisect
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy

N = int(input())
T = [None]*N
for i in range(N):
    Ai = int(input())
    T[i] = [-1]*N
    for j in range(Ai):
        xij, yij = map(int, input().split())
        dump(i, xij-1, yij)
        T[i][xij-1] = yij
dump(T)


def imply(p, q): return (not p) or q


ans = -1
for trusts in it.product([0, 1], repeat=N):
    dump(trusts)
    ok = True
    for i, trust in enumerate(trusts):
        if trust:
            for j, tij in enumerate(T[i]):
                ok = ok and imply(tij == 1, trusts[j]) and (
                    imply(tij == 0, not trusts[j]))
    if ok:
        ans = max([ans, len([i for i in trusts if i == 1])])
    dump(ans)
print(ans)

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

testinomy = [[-1 for _ in range(N)] for _ in range(N)]

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

ans = 0

for honests in range(2 ** N):
    bit = '{:015b}'.format(honests)[::-1]
    ok_flag = True
    for i in range(N):
        if bit[i] == '1':
            for j, k in enumerate(testinomy[i]):
                str_k = str(k)
                if bit[j] == '1' and str_k != '0':
                    pass
                elif bit[j] == '0' and str_k != '1':
                    pass
                else:
                    ok_flag = False
                    break
                
                
                
                
                
                
                
                
        if ok_flag == False:
            break
    if ok_flag:
        ans = max(ans, sum(map(int, bit)))

print(ans)

Solution (Python):
n = int(input())
 
l = [[-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())
    x = x-1
    l[i][x] = y


ans = 0
for i in range(2 ** n):
  
  flag = 0
  for j in range(n):
    if ((i >> j) & 1):
      
      for k in range(n):
        if l[j][k] == 1 and ((i >> k) & 1)==1:
          continue
        elif l[j][k] == 0 and ((i >> k) & 1)==0:
          continue
        elif l[j][k] == -1:
          continue
        else:
          
          flag = 1
  if flag == 0:
    ans_ = 0
    for p in range(n):
      if ((i >> p) & 1):
        ans_ += 1
    ans = max(ans, ans_)
print(ans)

Solution (Python):
N = int(input())
S = ['']

res = []

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

allp = 2**N - 1

for i in range(allp, -1, -1):
    pat = bin(i).replace('0b', '')
    pat = pat.zfill(N)
    h_list = []
    l_list = []
    for (i, p) in enumerate(pat):
        t = i + 1
        if p == '1':
            if t in l_list:
                break
            h_list.append(t)
            for s in S[t]:
                if s[1] == 1:
                    if s[0] in l_list:
                        break
                    h_list.append(s[0])
                else:
                    if s[0] in h_list:
                        break
                    l_list.append(s[0])
            else:
                continue
            break
        else:
            if t in h_list:
                break
            l_list.append(t)
    else:
        res.append(pat)

maxA = 0
for r in res:
    maxA = max(maxA, r.count('1'))
print(maxA)

Solution (Python):
n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    if j in tmp_num_list:
      continue
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      continue
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Solution (Python):
n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    if j in tmp_num_list:
      continue
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      continue
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Solution (Python):
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
ans = 0
lst = [[] for _ in range(n)]
for i in range(n):
    a = I()
    for j in range(a):
        x,y = LI()
        lst[i].append((x-1,y))
for i in range(2**n):
    b = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            b[j] = 1
    flg = True
    for j in range(n):
        if b[j] == 0:
            continue
        for k,l in lst[j]:
            if l == 0:
                if b[k] == 1:
                    flg = False
                    break
            else:
                if b[k] == 0:
                    flg = False
                    break
        if not flg:
            break
    else:
        ans = max(ans,sum(b))
print(ans)

Solution (Python):

MOD = 10 ** 9 + 7

import math
import itertools



def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


def main():



    n = int(input())
    xy = [[] for i in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            xy[i].append(list(map(int,input().split())))
    b=[-1 for i in range(n)]
    count=0
    for c in itertools.product(range(2),repeat=n):
        k=0
        for i in range(n):
            if c[i]==1 and k==0:
                for j in xy[i]:
                    if c[j[0]-1]!=j[1]:
                        k=1
                        break
        if k==0:
            count=max(count,sum(c))




    print(count)









            

if __name__ == "__main__":
    main()

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

ans = 0
for i in range(2**n):
  results = [None] * n
  for j in range(n):
    candidate = ((i >> j) & 1) == 1
    if results[j] is None:
      results[j] = candidate
    elif results[j] != candidate:
      break
    if candidate == False:
      continue
    elif candidate == True:
      failed = False
      for comment in comments[j]:
        if results[comment[0]] is None:
          results[comment[0]] = comment[1]
        if results[comment[0]] != comment[1]:
          failed = True
          break
      if failed:
        break
  else:
    cnt = len([r for r in results if r is True])
    if cnt > ans:
      ans = cnt

print(ans)

Solution (Python):
N = int(input())
lst = [[] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    lst[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**N):
  flag = True
  bin_lst = list(bin(i)[2:].zfill(N))
  for idx,j in enumerate(bin_lst):
    if (j == '1'):
      for v, w in lst[idx]:
        if (bin_lst[v-1] != str(w)):
          flag = False
  if (flag):
    ans = max(ans,bin_lst.count('1'))
print(ans)

Solution (Python):
n = int(input())
s_dict = {}
for i in range(n):
  add_dict = {}
  a = int(input())
  for j in range(a):
    b = list(map(int, input().split()))
    add_dict[b[0]-1] = b[1]
  s_dict[i] = add_dict
max_num = 0

def rec_get_list(i, tmp_num_list, tmp_honest, tmp_unkind):
  add_dict = s_dict[i]
  tmp_num_list.add(i)
  tmp_honest.add(i)
  for k, v in add_dict.items():
      if v:
        if k not in tmp_num_list:
        	tmp_num_list, tmp_honest, tmp_unkind = rec_get_list(k, tmp_num_list, tmp_honest, tmp_unkind)
        tmp_honest.add(k)
      else:
        tmp_unkind.add(k)
  return tmp_num_list, tmp_honest, tmp_unkind

def rec_check(i, tmp_num_list, tmp_honest, tmp_unkind):
  global max_num
  global n
  for j in range(i, n):
    if j in tmp_num_list:
      continue
    use_num_list = tmp_num_list.copy()
    use_honest = tmp_honest.copy()
    use_unkind = tmp_unkind.copy()
    use_num_list, use_honest, use_unkind = rec_get_list(j, use_num_list, use_honest, use_unkind)
    check_flg = len(use_honest & use_unkind)
    if check_flg:
      continue
    else:
      if len(use_num_list) > max_num:
        max_num = len(use_num_list)
    if j+1 < n:
      rec_check(j+1, use_num_list, use_honest, use_unkind)
  
rec_check(0, set(), set(), set()) 
    
print(max_num)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = 0
lst = [[] for _ in range(n)]
for i in range(n):
    a = I()
    for j in range(a):
        x,y = LI()
        lst[i].append((x-1,y))
for i in range(2**n):
    b = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            b[j] = 1
    flg = True
    for j in range(n):
        if b[j] == 0:
            continue
        for k,l in lst[j]:
            if l == 0:
                if b[k] == 1:
                    flg = False
                    break
            else:
                if b[k] == 0:
                    flg = False
                    break
        if not flg:
            break
    else:
        ans = max(ans,sum(b))
print(ans)

Solution (Python):
n = int(input())
Adj = [[-1]*n for _ in range(n)]

for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij,yij = map(int, input().split( ))
        xij -= 1
        Adj[i][xij] = yij

ans = 0

bt = 1<<n

for b in range(bt):
    flag = True
    tmp = 0
    for i in range(n):
        for j in range(n):
            if Adj[i][j]>=0:
                if ((b>>i) &1) and not ((Adj[i][j]==0) ^ ((b>>j) &1)):
                    flag = False
                    break
        if not flag:
            break
    if flag:
        for t in range(n):
            tmp += (b>>t)&1
            
    ans = max(tmp, ans)
    
print(ans)

Solution (Python):
N = int(input())
S = ['']

res = []

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

allp = 2**N - 1

for i in range(allp, -1, -1):
    pat = bin(i).replace('0b', '')
    pat = pat.zfill(N)
    h_list = []
    l_list = []
    for (i, p) in enumerate(pat):
        t = i + 1
        if p == '1':
            if t in l_list:
                break
            h_list.append(t)
            for s in S[t]:
                if s[1] == 1:
                    if s[0] in l_list:
                        break
                    h_list.append(s[0])
                else:
                    if s[0] in h_list:
                        break
                    l_list.append(s[0])
            else:
                continue
            break
        else:
            if t in h_list:
                break
            l_list.append(t)
            
            
            
            
            
            
            
            
            
            
            
            
    else:
        res.append(pat)

maxA = 0
for r in res:
    maxA = max(maxA, r.count('1'))
print(maxA)

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        dic[i].append((x-1,y))

 
from itertools import product
P = product(range(2),repeat=N)

 
ans = 0
for p in P:
    flg = True
    for i in range(N):
        if p[i] == 1:
            for xi,yi in dic[i]:
                if p[xi] != yi:
                    flg = False
        if not flg:
            break
    if flg: ans = max(ans, sum(p))
print(ans)

Solution (Python):
n = int(input())
lst = [[-1 for _ in range(n)] for __ in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        hito, which = map(int, input().split())
        lst[i][hito-1] = which

ans = 0
muri = 0
for i in range(2**n):
    kumi = list(format(i, '0'+str(n)+'b'))
    temp = 0
    muri = 0
    for j in range(n):
        if muri == 1:
            break
        elif kumi[j] == '1':
            for k in range(n):
                if (lst[k][j] == 0 and kumi[k] == '1') or (lst[j][k] == 1 and kumi[k] == '0'):
                    muri = 1
                    break
            if muri == 0:
                temp += 1
    if muri == 0:
        ans = max(ans, temp)

print(ans)

Solution (Python):


from itertools import combinations
import numpy as np
N = int(input())

A = []
x = []
y = []
for i in range(N):
	
	Ai = int(input())
	A.append(Ai)
	x.append([])
	y.append([])
	for j in range(Ai):
		xyij = input().split(" ")
		x[i].append(int(xyij[0]) - 1)
		y[i].append(int(xyij[1]))

def judge_contradiction(honest_index, N, A, x, y):
	
	all_people_judge = np.zeros(N, dtype="int")
	all_people_judge[:] = -1
	for i in honest_index:
		all_people_judge[i] = 1
	for ind in honest_index:
		
		
		for i in range(A[ind]):
			
			target, testimony = x[ind][i], y[ind][i]
			if all_people_judge[target] == -1:
				all_people_judge[target] = testimony
				continue
			elif all_people_judge[target] == testimony:
				continue
			else:
				
				return False
	
	for i in range(N):
		if all_people_judge[i] == 1:
			if np.any(np.array(honest_index) == i):
				continue
			else:
				return False
	return True

def doit(N, A, x, y):
	for numHonest in range(N, 0-1, -1):
		
		for honest_index in combinations(np.arange(N), numHonest):
			
			
			
			if judge_contradiction(honest_index, N, A, x, y) == True:
				return numHonest
			else:
				continue
	return "hey"

print(doit(N, A, x, y))

Solution (Python):
import itertools

N = int(input())

ans = list()

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

for i in range(N):
    for x in itertools.combinations(range(N), N-i):
        for y in x:
            for c, d in ans[y]:
                if d == 0 and c in x:
                    break
                if d == 1 and not c in x:
                    break
            else:
                continue
            break
        else:
            print(N-i)
            exit()
print(0)

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

_n = int(input())

said = []
for i in range(_n):
    ai = int(input())
    said.append([list(map(int, input().split())) for _ in range(ai)])

ans = 0
for i in range(2 ** _n):
    ynflg = 1
    flg = format(i, 'b').zfill(_n)
    for sy, tag in zip(said, flg):
        if tag == '0':
            continue

        for s in sy:
            if flg[s[0] - 1] != str(s[1]):
                ynflg = 0
                break

        if ynflg == 0:
            break

    if ynflg == 1:
        ans = max(ans, flg.count('1'))

print(ans)

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

def solve(Shogen, isHonests, manId):
  ans = True
  new_honests = []
  for x, y in Shogen[manId-1]:
    if isHonests[x-1] == -1:
      isHonests[x-1] = y
      if y == 1:
        new_honests.append(x)
    elif isHonests[x-1] != y:
      return False
  if new_honests:
    for nh in new_honests:
      ans = ans and solve(Shogen, isHonests, nh)
  return ans

N = int(input())
shogens = []
for _ in range(N):
  a = int(input())
  s = [list(map(int, input().split())) for _ in range(a)]
  shogens.append(s)
ishonests = [-1]*N
for begin in range(1, N+1):
  if ishonests[begin-1] == -1:
    tmphonests = ishonests.copy()
    tmphonests[begin-1] = 1
    if solve(shogens, tmphonests, begin):
      ishonests = tmphonests
    else:
      ishonests[begin-1] = 0
print(sum(ishonests))

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

def main():
    n=int(input())
    XY=[[] for _ in range(n)]
    for i in range(n):
        a=int(input())
        for _ in range(a):
            x,y=map(int,input().split())
            x-=1
            XY[i].append((x,y))
    ans=0
    for i in range(1<<n):
        tmp=0
        flag=True
        for j in range(n):
            if (i>>j)&1==0:
                continue
            tmp+=1
            for x,y in XY[j]:
                if (i>>x)&1!=y:
                    flag=False
        if flag:
            ans=max(ans,tmp)
    print(ans)
    
if __name__=='__main__':
    main()