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

"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
import re

def count1(bits):
    counter = 0
    while bits > 0:
        if bits & 1:
            counter += 1
        bits >>= 1
    return counter

def sol(N, testimonies):
    
    
    maxi = 0
    for i in range(1<<N):
        ok = True
        for j in range(N):
            for x, y in testimonies[j]:
                if i & (1 << j): 
                    if i & (1 << (x-1)) and not y: 
                        ok = False; break
                    elif not (i & (1 << (x-1))) and y: 
                        ok = False; break
            if not ok:
                break
        if ok:
            maxi = max(count1(i), maxi)
    return maxi


do_submit = True


def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    
    n = int(parsed_lines[0][0])
    k = int(parsed_lines[0][1])
    
    return n, k


if not do_submit:
    n, k = input_parse("""
    5
10 4 8 7 3
    """)
    print(sol(n, k))

    n, k = input_parse("""
    100000 5
    """)
    print(sol(n, k))


else:
    N = int(input().strip())
    testimonies = []
    for i in range(N):
        A = int(input().strip())
        XYs = []
        for j in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x, y))
        testimonies.append(XYs)
    
    print(sol(N, testimonies))

Solution (Python):
import itertools

n = int(input())

dic = {}


for val in range(n):
    a = int(input())
    h_L = []
    for _ in range(a):
        a1,a2 = list(map(int,input().split()))
        tmp = [a1-1,a2]
        h_L.append(tmp)
    dic[val] = h_L

ans = []


bit = itertools.product([0,1],repeat=n)

for val in bit:
    flag = True
    for i,katei in enumerate(val):
        if katei == 0:
            continue
        if katei == 1:
            for hatsugen in dic[i]:
                
                if hatsugen[1] != val[hatsugen[0]]:
                    flag = False
                    
    if flag is True:
        ans.append(sum(val))

print(max(ans))

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

import itertools
PRD=list(itertools.product([0,1], repeat=N))

def counter(status):
    f=1
    l=[-1]*N
    for i in range(N):
        if status[i]==0:
            continue
        else:
            for j in range(A[i]):
                if (l[XY[i][j][0]-1]!=-1 and l[XY[i][j][0]-1]!=XY[i][j][1]) or (status[XY[i][j][0]-1]!=XY[i][j][1]):
                    f=0
                    break
                else:
                    l[XY[i][j][0]-1]=XY[i][j][1]
    return([0,status.count(1)][f])

ans=0                
for i in range(2**N):
    ans=max(ans,counter(PRD[i]))
print(ans)

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

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

ans = 0
for i in range(2 ** n):
    flg = True
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in tbl[j]:
                if (i >> (k[0] - 1)) & 1 != k[1]:
                    flg = False
    if flg == True:
        ans = max(ans, str(bin(i)).count('1'))

print(ans)

Solution (Python):
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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



ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        
        if ((bits >> (i - 1)) & 1) == 0:
            continue
        for j in range(1, A[i] + 1):
            
            if ((bits >> (x[i][j] - 1)) & 1) != y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Solution (Python):
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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



ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        
        if not ((bits >> (i - 1)) & 1):
            continue
        for j in range(1, A[i] + 1):
            
            if ((bits >> (x[i][j] - 1)) & 1) ^ y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
 
N=int(input())
box = [[None]*N for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int,input().strip().split())
    box[i][x-1]=y

ans=0
for bi in range(2 ** N - 1, -1, -1):
  chk=True
  for i,A in enumerate(box):
    if (bi>>i)%2 == 0:
      continue
    for j,y in enumerate(A):
      if y is None:
        continue
      elif y == 0 and (bi>>j)%2 == 1:
        chk=False
        break
      elif y == 1 and (bi>>j)%2 == 0:
        chk=False
        break
      else:
        pass
    if not chk:
      break
  if chk:
    tmp=0
    for c in range(N):
      if (bi>>c)%2 == 1:
        tmp+=1
    ans=max(ans,tmp)
print(ans)

Solution (Python):
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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



ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        
        if not (bits & (1 << (i - 1))):
            continue
        for j in range(1, A[i] + 1):
            
            if ((bits >> (x[i][j] - 1)) & 1) ^ y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Solution (Python):
n = int(input())
dic = {i:[] for i in range(n)}

for ni in range(n):
  a = int(input())
  for ai in range(a):
    x,y = map(int,input().split())
    dic[ni].append((x-1,y))

ans = 0    
    
for i in range(2**n):
  p = [0]*n
  for j in range(n):
    if i>>j & 1:
      p[j]=1  
  
  flag = True
  for j in range(n):    
    if p[j]:
      for h,tf in dic[j]:
        if (tf==1 and p[h]==1) or (tf==0 and p[h]==0):
          pass
        else:
          flag = False          
  if flag:
    ans = max(ans,sum(p))
    
print(ans)

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

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

m=0
for i in range(2**N):
  f=True
  for j in range(N):
    if (i>>j)&1==0:
      continue	
    for k in xy[j]:
      if (i>>k[0])&1!=k[1]:
        f=False
        break
    if f==False:
      break
  if f==True:
    c=0
    while i>0:
      c+= i&1
      i >>= 1
    m=max(m,c)
print(m)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
xy = [[] for i in range(n)]
for i in range(n):
    for j in range(inp()):
        a,b = inpl()
        xy[i].append([a,b])

res = 0
for flag in itertools.product([0,1],repeat=n):
    cnt = 0
    theory = [-1]*n 
    f = True
    for i,j in enumerate(flag):
        if theory[i] == -1:
            theory[i] = j
        elif theory[i] != j:
            f = False
            break
        if not j:
            continue
        cnt += 1
        for k in xy[i]:
            if theory[k[0]-1] == -1:
                theory[k[0]-1] = k[1]
            elif theory[k[0]-1] != k[1]:
                f = False
                break
        if not f:
            break
    if not f:
        continue
    res = max(res,cnt)
print(res)

Solution (Python):
N = int(input())
kind = []
unkind = []
for _ in range(N):
    a = int(input())
    k = u = 0
    for _ in range(a):
        ans, y = [int(_) for _ in input().split()]
        ans -= 1
        if y:
            k += 2**ans
        else:
            u += 2**ans
    kind += [k]
    unkind += [u]
ans = 0
for B in range(2**N - 1, -1, -1):
    k = 0
    u = 0
    for b in range(N):
        if (B >> b) & 1:
            k |= kind[b]
            u |= unkind[b]
    if (k & B) == k and (u & B) == 0:
        ans = max(ans, bin(B).count('1'))
print(ans)

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

x_list = []
y_list = []


A_list = []



for n in range(N):
    
    A = int(input())
    A_list.append(A)
    x = []
    y = []
    for a in range(A):
        x_tmp, y_tmp = map(int, input().split())
        x.append(x_tmp)
        y.append(y_tmp)
    x_list.append(x)
    y_list.append(y)




isHonest_list = [False] * N


ans_candidate = []


def dfs(i, isHonest_list, ans_candidate):
    
    
    if i >= N:
        isNotContradict = True  
        for n in range(N):
            
            if isHonest_list[n] == False:
                continue
            
            for A_list_i in range(A_list[n]):
                
                
                if (y_list[n][A_list_i] == 1 and isHonest_list[x_list[n][A_list_i]-1] == False) or\
                    (y_list[n][A_list_i] == 0 and isHonest_list[x_list[n][A_list_i]-1]):
                    isNotContradict = False
                    break
            else:
                continue
            break

        
        if isNotContradict:
            ans_candidate.append(isHonest_list.count(True))
        return

    
    isHonest_list[i] = False

    dfs(i+1, isHonest_list, ans_candidate)
    
    
    isHonest_list[i] = True
    dfs(i+1, isHonest_list, ans_candidate)

dfs(0, isHonest_list, ans_candidate)
print(max(ans_candidate))

Solution (Python):
from itertools import product
n=int(input())
m=[]
for i in range(n):
  a=int(input())
  t=[-1]*n
  for j in range(a):
    each=list(map(int,input().split()))
    t[each[0]-1]=each[1]
  m.append(t)

ans = 0
prod=list(product(range(2),repeat=n))
for i in range(len(prod)):
  flag=1
  for j in range(n):
    if prod[i][j] == 1:
      for k in range(n):
        if m[j][k] != -1 and m[j][k] != prod[i][k]:
          flag = 0
          break
      if flag == 0:
        break
  if flag:
    ans = max(ans, sum(prod[i]))
  
print(ans)

Solution (Python):






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




P = []
for i in range(2 ** N): 
    pat = [0] * N
    for j in range(N): 
        if ((i >> j) & 1) : 
            pat[N - 1 - j] = 1 
    P.append(pat)



ans = 0
flag = 'Y'
for p in P :
    for i in range(N) :
        if p[i] == 1 : 
            for x in X[i] :
                if x[1] != p[x[0]-1] :
                    flag = 'N'
    if flag == 'Y' : 
        c = sum(p)
        if c > ans :
            ans = c
    flag = 'Y' 
print(ans)

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


if N == 1:
    print(1)
    exit()



H = []
for i in range(2**N):
    S = str(bin(i))
    H.append(S[2:].zfill(N))

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

ans = 0
for h in H:
    cnt = h.count("1")
    for ixy in IXY:
        i,x,y = ixy[0],ixy[1]-1,ixy[2]
        if h[i] == "1" and h[x] != str(y):
            cnt = 0
            break
    ans = max(ans,cnt)
print(ans)

Solution (Python):
N = int(input())
A = [0] * N
X = [[0]*N for _ in range(N)]
Y = [[0]*N for _ in range(N)]

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

ans = 0
for i in range(1 << N):
    flg = True
    for j in range(N):
        if i >> j & 1 ^ 1:
            
            continue
        for k in range(A[j]):
            if i >> X[j][k] & 1 ^ Y[j][k]:
                flg = False
                break
        if not flg: break
    if flg: ans = max(ans,str(bin(i))[2:].count('1'))
print(ans)

Solution (Python):
N=int(input())
table=[[None]*N for _ 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

def is_consistent(table,hito):
    flag=True
    for i in range(len(hito)):
        if hito[i]==0:
            continue
        elif hito[i]==1:
            for j in range(len(hito)):
                if table[i][j]==None:
                    continue
                elif table[i][j]!=hito[j]:
                    flag=False
                    break
        if flag==False:
            break
    return flag
  
ans=0
for i in range(0,2**N):
    length=len(bin(i)[2:])
    hito=[]
    for j in range(length):
        hito.append(int(bin(i)[2:][-j-1]))
    for j in range(N-length):
        hito.append(0)
    hito.reverse()
    if is_consistent(table,hito):
        ans=max(ans,sum(hito))
print(ans)

Solution (Python):
n = int(input())
witness = []
 
for i in range(n):
    a = int(input())
    witness.append([])
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        witness[-1].append((x,y))
 
def is_honest(i, j):
    return (i >> j) % 2 == 1
 
def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i, j)
    return ans
 
ans = 0
 
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x, y) in witness[j]:
            if y == 0 and is_honest(i, x):
                ok = False
            if y == 1 and not is_honest(i, x):
                ok = False
    if ok:
        ans = max(ans, honest_cnt(i))
 
print(ans)

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

ans = 0
for i in range(2**n):
    
    bit = bin(i)[2:].zfill(n)[::-1]
    cnt = bit.count('1')
    b = False
    
    for i,t in zip(bit,A):
        if i == '0': continue
        for p in t:
            k,v = p 
            if bit[k-1] != str(v):
                b = True
                cnt = 0
                break
        
        if b == True: break
    
    ans = max(ans,cnt)

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

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

ans=0
for i in range(2**n):
    r=1
    ib=list(format(i,"b").zfill(n))
    for j in range(n):
        if ib[j]=="1":
            for k in range(len(a[j])):
                if int(ib[a[j][k][0]-1])!=a[j][k][1]:
                    r=0
    if r==1:
        ans=max(ans,ib.count("1"))
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools
import numpy as np

N = int(readline())
info = []
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        info.append((i,x-1,y))
        
A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Solution (Python):
def GetBitStands(val):
    i = 0
    while val > 0 :
        if (val & 1) != 0 : yield i
        i += 1
        val >>= 1

def GetBitCount(val):
    cnt = 0
    while val > 0 :
        if (val & 1) != 0 :
            cnt += 1
        val >>= 1
    return cnt

def IsAllHonest(bit_map,peaple):
    for index in GetBitStands(bit_map):
       if not peaple[index].is_honest(bit_map) :
           return False
    return True

def Honests(peaple):
    for i in range(1 << len(peaple)):
        if IsAllHonest(i,peaple):
            yield i

class UserWord:
    def __init__(self):
        self.has_word = 0
        self.word = 0
    def is_honest(self,bit):
        return (bit ^ self.word)&self.has_word == 0



num = int(input())

peaple = []


for i in range(num):
    p = UserWord()
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        
        mask = 1 << (x-1)
        p.has_word |= mask
        if y != 0:
            p.word |= mask
    peaple.append(p)

max = 0
for kouho in Honests(peaple):
    temp = GetBitCount(kouho)
    if max < temp:
        max = temp

print(max)

Solution (Python):
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())
        xy[i].append([x-1,y])

answer = 0

for n in range(2 ** N):
    
    true_person = []
    index = 0
    copy_n = n
    while copy_n:
        if copy_n & 1:
            true_person.append(index)
        index += 1
        copy_n >>= 1

    
    flag = False

    
    for i in true_person:
        
        for x,y in xy[i]:
            
            if (x in true_person and y == 0) or (not(x in true_person) and y == 1):
                flag = True
        if flag:
            break
    if flag:
        continue
    else:
        answer = max(answer, len(true_person))
    
print(answer)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
ans = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
           if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(ans)

Solution (Python):
from itertools import product

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)

ans = 0
for ts in product([1,0], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in xy[i]):
                break

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

print(ans)

Solution (Python):
from itertools import product

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)

ans = 0
for ts in product([1,0], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in xy[i]):
                break

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

print(ans)

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

flag = True
ans = []
for i in range(2 ** N):
	l = list(format(i, 'b').zfill(N))
	k = [int(s) for s in l]
	for j in range(N):
		if k[j] == 1:
			for l in range(len(A[j])):
				if A[j][l][1] != k[A[j][l][0] - 1]:
					flag = False
					break
	if flag == True:
		ans.append(k.count(1))
	else:
		flag = True

print(max(ans))

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in combinations(r, i)
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in combinations(r, i)
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Solution (Python):
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Solution (Python):
from itertools import product

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

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

ans = 0

for ts in product([1,0], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(ts))

print(ans)

Solution (Python):
def popcount(x):
  r, q = 0, x
  while x:
    r += 1
    x &= x - 1
  return r, q
 
n = int(input())
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << (x - 1)
l = (1 << n) - 1 
b = sorted(map(popcount, range(1, l + 1)))
ans = next((i for i, x in reversed(b)
           if all(a[j][0] & x == a[j][1] & l - x == 0 for j in r if x >> j & 1)), 0)
print(ans)

Solution (Python):
n=int(input())
ansli=[0]

import itertools


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

for i in itertools.product((0,1),repeat=n): 
  temp=[-1]*n 
  flag=1
  for j in range(n): 
    for k in a[j]: 
      x=k[0]-1
      y=k[1]

      
      if i[j]==1: 

        
        if temp[x]==-1:
          temp[x]=y 
        
        
        else:
          if temp[x]!=y: 
            flag=0
            break

      

      
      
      
      
      
      
      
      
      
      
      

  
  for j in range(n):
    if temp[j]!=-1:
      if i[j]!=temp[j]: 
        flag=0
        break
  if flag==1: 
    ansli.append(sum(i))
    

print(max(ansli))

Solution (Python):
n = int(input())
x = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x[i].append(tuple(map(int,input().split())))
m = 0
for i in range(1,2**n):
  c = bin(i)[2:]
  c = '0'*(n-len(c)) + c
  f = 1
  co = 0
  for j in range(n):
    if c[j] == '1':
      co += 1
      for k,l in x[j]:
        if int(c[k-1]) != l:
          f = 0
          break
    if f == 0:
      break
  if f:
    m = max(m,co)
print(m)

Solution (Python):
def popcount(x):
  r = 0
  while x:
    r += 1
    x &= x - 1
  return r
 
n = int(input())
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << (x - 1)
 
m = 0
l = (1 << n) - 1
for x in range(1, l + 1):
  if all(a[i][0] & x == a[i][1] & l - x == 0 for i in r if x >> i & 1):
    m = max(m, popcount(x))
print(m)

Solution (Python):
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for _ in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x - 1, y))

def main():
    comb = (np.arange(2 ** n).reshape(-1, 1) >> np.arange(n) & 1).astype(np.bool)
    for i in range(n):
        for x, y in xy[i]:
            bl = ~comb[:, i] | (comb[:, x] == np.bool(y))
            comb = comb[bl] 
    '''
    ~comb[:, i]:= (i番目がUnkindと仮定したとき、)i番目をUnkind(False)としている組み合わせを残す
    (comb[:, x] == np.bool(y)):= (i番目がHonestと仮定したとき、)i番目の証言が矛盾しない組み合わせを残す
    '''
    
    ans = np.amax(np.sum(comb, axis=1))
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

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

ans = 0
for i in range(2**n):
    pat = []
    for j in range(n):
        pat.append((i>>j)%2)
    check = True
    for j in range(n):
        if pat[j]:
            for z in xy[j]:
                if pat[z[0]-1] != z[1]:
                    check = False
    if check:
        ans = max(ans, sum(pat))
print(ans)

Solution (Python):
import itertools


n = int(input())

all = list(itertools.product([0,1], repeat=n))
xy,xyz = [],[]
for _ in range(n):
    a = int(input())
    for i in range(a):
        x,y = map(lambda x: int(x),input().split())
        xy.append([x,y])
    xyz.append(xy)
    xy = []


test = ['None']*n
ans = []
ans_list = []
j_list = []
bool = True
hoge = 0
for i in range(len(all)):
    for j,k in enumerate(all[len(all) - 1 - i]):
        if k == 1:
            ans.append(xyz[j])
            j_list.append(j)
    ans = list(itertools.chain.from_iterable(ans))

    test = all[len(all) - 1 - i]
    for x in range(len(ans)):
        if test[ans[x][0]-1] != ans[x][1]:
            bool = False
            break

    if bool :
        hoge = all[len(all) - 1 - i]
        break
    bool = True
    test = ['None']*n
    ans = []
    j_list = []
print(sum(hoge))

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

class human:
    def __init__(self, a):
        self.a = a
        self.x = [None for i in range(a)]
        self.y = [None for i in range(a)]

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

loop_n = 2**n


def solve(bit_true):
    for i, bit in enumerate(bit_true):
        if bit == '1':
            for j, x in enumerate(humans[i].x):
                if int(bit_true[x-1]) == int(humans[i].y[j]):
                    pass
                elif int(bit_true[x-1]) != int(humans[i].y[j]):
                    return 0
    return sum(map(int, list(bit_true)))


i = 0
true_n = 0
while i < loop_n:
    bit_true = format(i, 'b').zfill(n)
    true_n = max(true_n, solve(bit_true))
    i += 1

print(true_n)

Solution (Python):
n = int(input())
a = list()
x = []
y = []
for i in range(n):
    A = int(input())
    a.append(A)
    x_ = []
    y_ = []
    for j in range(A):
        X,Y = map(int,input().split())
        x_.append(X)
        y_.append(Y)
    x.append(x_)
    y.append(y_)
mat = [0 for i in range(2**n)]
for i in range(2**n): 
    flag = True
    binary = format(i,"b")
    binary = (n-len(binary))*"0"+binary
    for j in range(n):
        if flag and  len(binary) > j and binary[j] =="1":
            for k in range(a[j]):
                if flag and len(binary) > x[j][k]-1 and binary[x[j][k]-1] != str(y[j][k]):
                    flag = False
                    break
    if flag:
        mat[i] = 1
ans = 0
for i in range(2**n):
    if mat[i] == 1:
        binary =format(i,"b")
        count = 0
        for j in range(len(binary)):
            count += int(binary[j])
        ans = max(ans,count)
print(ans)

Solution (Python):
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
xy = [[] for _ in range(n)]
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    for _ in range(a):
        x, y = map(int, sys.stdin.readline().split())
        xy[i].append((x - 1, y))

def main():
    comb = (np.arange(2 ** n).reshape(-1, 1) >> np.arange(n) & 1).astype(np.bool)
    for i in range(n):
        for x, y in xy[i]:
            bl = ~comb[:, i] | (comb[:, x] == np.bool(y))
            comb = comb[bl]
    
    ans = np.amax(np.sum(comb, axis=1))
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
n = int(input())
l = [] 
for i in range(n):
	list = [" "] * n
	a = int(input())
	for j in range(a):
		data = input().split(" ")
		x = int(data[0])
		y = data[1]
		list[x-1] = y
	l.append(list)
m = 0
for i in range(2**n):
	s = bin(i)
	s = s[2:]
	s = s.zfill(n)
	ll = []
	th = [" "] * n
	for j in range(n):
		if int(s[j]) == 1:
			ll.append(l[j])
			th[j] = "1"
		elif int(s[j]) == 0:
			th[j] = "0" 
	te = 0
	for j in range(n):
		for k in range(len(ll)):
			if ll[k][j] == "1" or ll[k][j] == "0":
				if ll[k][j] != th[j]:
					te = 1
	if te == 0:
		f = len(ll)
		if f > m:
			m = f
print(m)