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 itertools import product


def main():
    
    N = int(input())
    grid = [[None for _ in range(N)] for i in range(N)]
    for i in range(N):
        a = int(input())
        for _ in range(a):
            x, y = list(map(int, input().split()))
            grid[i][x-1] = y
    res = 0
    for p in product([0, 1], repeat=N):
        flag = True
        p = list(p)
        for i in range(N):
            if p[i] == 0:
                continue
            for j in range(N):
                if grid[i][j] is None:
                    continue
                if grid[i][j] == p[j]:
                    continue
                flag = False
                break
            if flag:
                continue
            break
        if flag:
            res = max(res, sum(p))
    print(res)
    pass

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

def acinput():
    return list(map(int, input().split(" ")))


def chk(x,d):
    for l,xx in enumerate(x):
        if xx==1:
            for dd in d[l]:
                
                
                if dd[1]==1 and x[dd[0]-1]==0:
                    return False
                if dd[1]==0 and x[dd[0]-1]==1:
                    return False
    return True


N=int(input())

d=[]
for k in range(N):
    aa=int(input())
    
    d.append([])
    for j in range(aa):
        d[-1].append(acinput())



res=0

for x in range(2**N):
    x=list(map(int,list(bin(x)[2:].zfill(N))))
    
    if chk(x,d):
        res=sum(x)
    
print(res)

Solution (Python):
N = int(input())
ans = []
A = [0 for i in range(N)]
Axy = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
    Axy[i] = [[int(i) for i in input().split()] for j in range(A[i])]

for i in range(1<<N):
    Truth = []
    maru = 0
    for j in range(N):
        Truth.append(((i>>j)&1)==1)
        maru += ((i>>j)&1)
    syogen = [0 for i in range(N)]
    for k in range(N):
        if Truth[k]:
            syogen[k] = 1
    isMujun = True
    for k in range(N):
        if Truth[k] and isMujun:
            for x,y in Axy[k]:
                if syogen[x-1]==y:
                    pass
                else:
                    ans.append(0)
                    isMujun = False
                    break
    if isMujun:
        ans.append(maru)
print(max(ans))

Solution (Python):

n = int(input())
people = {}

for i in range(n):
    sentenses = int(input())
    if sentenses > 0:
        for j in range(sentenses):
            v = list(map(int, input().split()))
            if i in people.keys():
                people[i].append(v)
            else:
                people[i] = [v]
            
ans = 0

for i in range(2**n):
    speaker = []
    p_list = [0] * n
    for j in range(n):
        if ((i >> j) % 2) == 1:
            speaker.append(j)
            p_list[j] = 1

    continue_flag = True
    for s in speaker:
        if continue_flag:
            if s in people.keys():
                sentenses = people[s]
            else:
                continue
            for sent in sentenses:
                if p_list[sent[0]-1] == sent[1]:
                    p_list[sent[0]-1] = sent[1]
                else:
                    continue_flag = False
                    break
        else:
            break
        
    if continue_flag:
        temp_ans = len(speaker)
        ans = max(temp_ans, ans)

print(ans)

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())
arr=[]
for i in range(n):
    ansnum=int(input())
    for j in range(ansnum):
        a,b = map(int,input().split())
        arr.append((i,a,b))

if len(arr)==0:
    print(n)
else:
    
    maxcount=0
    for k in range(2**n):
        A=list(bin(k))[2:]
        
        while len(A)<n:
            A.insert(0,0)
        A=[int(i) for i in A]

        
        
        for num,j in enumerate(arr):
            if A[j[0]]==0:
                pass
            
            
            
            elif A[j[1]-1]!=j[2]:
                break
            """
            if j[1] not in d:
                d[j[1]]=j[2]
            elif d[j[1]]!=j[2]:
                break
            """
            
            if num==len(arr)-1: 
                maxcount=max(maxcount,sum(A))
    print(maxcount)

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

NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        if y == 1:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    
    
    group = set()
    newmember = set()
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.add(h)
            newmember.add(h)
        num //= 2

    while (len(newmember) != 0):
        for s in list(newmember):
            for p in range(N):
                if grouplist[s][p] == 1 and p not in group:
                    group.add(p)
                    newmember.add(p)
                newmember.discard(s)

    len_group = len(group)
        
    flag = 0
    if ans >= len_group:
       flag = 1
    
    
    for m in group:
        for t in group:
            if NGlist[m][t] == 1:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)

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

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

ans = 0
for i in range(2 ** N):
    check = [-1] * N 
    count = 0 
    flag = True
    for j in range(N):
        if (i >> j) & 1: 
            if check[j] == 0: 
                flag = False
                break
            else:
                check[j] = 1

            

            for x, y in lst[j]:
                if y == 1: 
                    if check[x] != 0:
                        check[x] = 1
                    else: 
                        flag = False
                        break
                else: 
                    if check[x] != 1:
                        check[x] = 0
                    else:
                        flag = False
                        break
        else: 
            if check[j] == 1:
                flag = False
                break
            else:
                check[j] = 0

        if flag == False:
            break
    if flag:
        tmp = 0
        for j in range(N):
            if (i >> j) & 1:
                tmp += 1
        
        
        ans = max(ans, tmp)

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())
xs = []
hs = [1] * n

for _ in range(0, n):
	xs.append([None] * n)

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

def solve(hs, i):
	if i == n:
		for j in range(0, n):
			if hs[j] != 0:
				for k in range(0, n):
					if j != k and xs[j][k] != None and hs[k] != xs[j][k]:
						return 0
		return sum(hs)
	
	hs[i] = 1
	x     = solve(hs, i + 1)
	hs[i] = 0
	y     = solve(hs, i + 1)
	
	return max(x, y)

print(solve(hs, 0))

Solution (Python):

import copy
import itertools

N=input()

L=[ [ None for j in range(N)] for i in range(N)]

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

CC=list(itertools.product((0,1),repeat=N))

ans=0


for C in CC:
    flag=True
    for i,c in enumerate(C):
        if flag==False: break
        if c==1:
            for x,y in zip(C,L[i]):
                if (x==1 and y==0) or (x==0 and y==1):
                    flag=False
                    break
    else:
        if flag==True:
            ans=max(ans,sum(C))
print ans

Solution (Python):


import itertools

def main():
    N = int(input())
    XY = []

    for _ in range(N):
        a = int(input())
        if a == 0:
            XY.append([])
            continue
        xy = []
        for _ in range(a):
            xy.append(list(map(int,input().split())))
        XY.append(xy)

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

    answer = 0
    for b in bit_list:
        for i in range(N):
            for x,y in XY[i]:
                if b[i] == 1:
                    if b[x-1] == y:
                        continue
                    else:
                        break
                
                
                
                
                
            else:
                continue
            break
        else:
            answer = max(sum(b),answer)
    print(answer)

if __name__ == '__main__':
    main()

Solution (Python):
def Jud(S,n,k):
  ans=True
  k2d=format(k,'b').zfill(n)
  people=[]
  for i in range(n):
    if k2d[i]=='1':
      people.append(i)
  for j in people:
        for k in range(len(S[j])):
          if S[j][k][1]==1:
            if S[j][k][0]-1 not in people:
              ans=False
              break
          elif S[j][k][1]==0:
            if S[j][k][0]-1 in people:
              ans=False
              break
  return ans
                
n=int(input())
S=[[] for i in range(n)]
for i in range(n):
  s=int(input())
  for j in range(s):
    S[i].append(list(map(int,input().split())))

honests=[]

for i in range(2**n):
  if Jud(S,n,i)==True:
    i2d=format(i,'b')
    honests.append(i2d.count('1'))

print(max(honests))

Solution (Python):
import itertools

N = int(input())
d = [0]*N
for i in range(N):
    A = int(input())
    d[i] = [list(map(int,input().split())) for _ in range(A)]
ans = 0
l = [0,1]
for s in itertools.product(l, repeat = N):
    flag = 0
    for i in range(N):
        if s[i] == 1:
            for a in d[i]:
                if a[1] == 1:
                    if s[a[0]-1] == 1:
                        pass
                    else:
                        flag = -1
                else:
                    if s[a[0]-1] == 0:
                        pass
                    else:
                        flag = -1
    if flag == 0:
        ans = max(ans, s.count(1))
print(ans)

Solution (Python):
from itertools import product, groupby

N = int(input())

testimony = []
for n in range(1, N + 1):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        testimony.append((n, x, y))

ans = []
for pattern in product((1, 0), repeat=N):
    choice_index = tuple(idx + 1 for idx, value in enumerate(pattern) if value == 1)
    choice_answers = [t for t in testimony if t[0] in choice_index]
    groups = []
    for choice_answer in choice_answers:
        person, target, honest_or_kind = choice_answer
        if pattern[target-1] != honest_or_kind:
            break
    else:

        data = sorted(choice_answers, key=lambda z: z[1])
        for k, g in groupby(data, lambda z: z[1]):
            groups.append(list(g))

        for group in groups:
            all_ans = set(tuple(ans[2] for ans in group))
            if len(all_ans) == 2:
                break
        else:
            ans.append(sum(pattern))
print(max(ans))

Solution (Python):
N = int(input())
import itertools
TF = [0,1]
All = list(itertools.product(TF, repeat=N))
lis_A = [0]
lis_x = []
lis_y = []
ans = 0
for i in range(N):
  A = int(input())
  lis_A.append(A)
  for j in range(A):
    x,y = map(int,input().split())
    lis_x.append(x-1)
    lis_y.append(y)
for p in range(1,N+1):
  lis_A[p] = lis_A[p-1]+lis_A[p]
for k in range(len(All)):
  L = All[k]
  jud = True
  for g in range(N):
    if L[g] == 1:
      for q in range(lis_A[g],lis_A[g+1]):
        if L[lis_x[q]] != lis_y[q]:
          jud = False
          break
  if jud:
    ans = max(sum(L),ans)
print(ans)

Solution (Python):

















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



ans=0
for i in range(2**n):
    pat=[]
    kanou=True
    kazu=0
    for j in range(n):
        if((i>>j) & 1):
            pat.append(1)
            kazu+=1
        else:
            pat.append(0)
    
    for j in range(n):      
        if(pat[j]==0):
            continue
        for k in range(a[j]):   
            hatu=sinrai[j][k]
            if(pat[hatu[0]-1] != hatu[1]):
                kanou=False
    if(kanou):
        ans=max(ans,kazu)

print(ans)

Solution (Python):
import itertools
import math

people = int(input())
data = []
truthfulness = [None]*people
i = 0

def contradiction(t,data):
    for i in range(len(t)):
        if t[i] == True:
            for q in data[i]:
                if q[1] == 0:
                    a = False
                else:
                    a = True
                if not t[q[0]-1] == a:
                    return False
    return True

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

num = 0
for v in itertools.product([True,False], repeat=people):
    if(v.count(True) > num):
        if contradiction(v,data):
            num = max(v.count(True),num)
print(num)

Solution (Python):
def p_c():
    from itertools import combinations
    n = int(input())
    d = [[set() for _ in range(2)] for _ in range(n)]
    for i in range(n):
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            d[i][y].add(x-1)
    ans = []
    for i in reversed(range(1, n + 1)):
        for cmb in combinations(range(n), i):
            true_set = set()
            false_set = set()
            for j in range(n):
                if j in cmb:
                    true_set = true_set | d[j][1]
                    false_set = false_set | d[j][0]
                else:
                    false_set.add(j)
            if not true_set & false_set:
                ans.append(n - len(false_set))
    if ans:
        print(max(ans))
    else:
        print(0)
        
p_c()

Solution (Python):
import sys
import collections
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    dl = []
    for i in range(n):
        a = int(readline())
        d = collections.defaultdict(list)
        for j in range(a):
            x, y = list(map(int, readline().split()))
            d[x-1] += [y]
        dl.append(d)
    mt = 0
    for v in itertools.product([True, False], repeat=n):
        b = True
        for i, vv in enumerate(v):
            if vv:
                for kkk, vvv in dl[i].items():
                    if vvv[0] != v[kkk] :
                        b = False
        if b:
            mt = max(mt, v.count(True))
    print(mt)


if __name__ == '__main__':
    solve()

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

mem = []
for i in range(2 ** N):
  mem.append(("{:0=15}".format(int(bin(i)[2:])))[15-N:])

ans = 0
for m in mem:
  f = True
  for i in range(N):
    if m[i] == "1":
      for li in l[i]:
        if str(li[1]) != m[li[0]]:
          f = False
          break
  if f:
    ans = max(ans, m.count("1"))
print(ans)

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

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

for i in range(2 ** n):
    b=[]
    for j in range(n):
      if i>>j & 1:
        b.append(j)
    summ=0
    jdg=[-1]*n
    flgg=0
    for j in range(len(b)):
      if jdg[b[j]]==-1:
        jdg[b[j]]=1
      elif jdg[b[j]]!=1:
        flgg=1
        break
      dic=a[b[j]]
      key=list(dic.keys())
      flg=0
      for k in range(len(key)):
        if jdg[key[k]-1]==-1:
          jdg[key[k]-1]=dic[key[k]]
        elif jdg[key[k]-1]==dic[key[k]]:
          jdg[key[k]-1]=dic[key[k]]
        else:
          flg=1
          flgg=1
          break
      if flg==1:
        flgg=1
        jdg=[-2]*n
        break
    
    sumi=0
    if flgg==0:
      for j in range(len(jdg)):
        if jdg[j]==1:
          sumi+=1
    if sumi==len(b):
      summ=sumi
    ans=max(ans,summ)
print(ans)

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

n = int(input())

comment_list = [ [] for i in range(n) ]
for i in range(n):
    m = int (input())
    for j in range(m):
        a, b = [ int(v) for v in input().split() ]
        comment_list[i].append([a-1,b])

ans = 0
for i in range(2**n):
    s = bin(i)[2:].zfill(n)
    status = 1
    for j, v in enumerate(s):
        for x, y in comment_list[j]:
            if v == "1":
                if s[x] != str(y):
                    status = 0
    if status == 1:
        ans = max(ans, s.count("1"))
print(ans)

Solution (Python):
n = int(input())
testimony = [[[], []] for _ in range(n)]
honest_a = []
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        testimony[x - 1][y].append(i)
max_honest = 0


def honest(unkind: set, stack: list, s: int, max_num: int,testimony):
    if s < n:
        unkind0 = unkind.copy()
        unkind1 = unkind.copy()
        stack.append(0)
        for i in testimony[s][1]:
            unkind0.add(i)
        max_num = honest(unkind0, stack, s + 1, max_num,testimony)
        stack.pop()

        stack.append(1)
        for i in testimony[s][0]:
            unkind1.add(i)
        max_num = honest(unkind1, stack, s + 1, max_num,testimony)
        stack.pop()
        return max_num
    else:
        count = 0
        for i in range(n):
            if stack[i]:
                count += 1
                if i in unkind:
                    return max_num
        return max(count, max_num)


print(honest(set(), [], 0, 0,testimony))

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

c = 0
ans = 0
while c < 2 ** (n):
    q = format(c,'b').zfill(n)
    q = list(str(q))
    q = [int(m) for m in q]
    
    
    
    p = [0] * n
    count = 0
    ans_tmp = 0
    for i in range(len(q)):
        if q[i] == 1:
            count += 1
            for j in range(len(A[i][1])):
                x,y = A[i][1][j]
                if y == 1:
                    if not int(q[x-1]) == 1:
                        ans_tmp = -1
                else:
                    if not int(q[x-1]) == 0:
                        ans_tmp = -1
    if ans_tmp == 0:
        ans_tmp = count

    if ans_tmp > ans:
        ans = ans_tmp
    c += 1
print(ans)

Solution (Python):
import itertools

N = int(input())

say = {i:[] for i in range(1, N+1)}
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        say[i+1].append([x, y])

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

max_count = 0
for ans in ans_list:
    flag = 0
    for i, an in enumerate(ans):
        if an == 1:
            for s in say[i+1]:
                
                if ans[s[0]-1] == s[1]:
                    continue
                else:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        max_count = max(sum(ans), max_count)


print(max_count)

Solution (Python):
import itertools

n = int(input())

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


for i in range(n):
    s = int(input())
    for j in range(s):
        a,b = map(int,input().split())
        tal = (a-1,b)
        speak[i].append(tal)

check = 0

b = [i for i in range(n)]
c = len(b)

b_pairs = []
for i in range(1,n+1):
    b_pairs += list(itertools.combinations(b,i))

for i in b_pairs:
    tru = []
    for j in i:
        tru.append(j)
    
    leng = len(tru)
    if leng <= check:
        continue
    
    for k in tru:
        z = 1
        for d,e in speak[k]:
            if d in tru:
                if e == 1:
                    continue
                else:
                    z = 0
            else:
                if e == 0:
                    continue
                else:
                    z = 0
        if z == 0:
            break
    else:
        check = leng
            
print(check)

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

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

result = 0
for i in range(1, 2 ** N):
  t = [-1] * N
  for j in range(N):
    t[j] = (i >> j) & 1
  m = False
  for j in range(N):
    if (i >> j) & 1 == 0:
      continue
    for x, y in s[j]:
      if t[x] != y:
        m = True
        break
  if not m:
    result = max(result, bin(i)[2:].count('1'))
print(result)

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

xys = []

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



status = [0 for _ in range(N)]

ans = 0

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)

    
    for j in range(N):
        status[j] = int(tmp[-j-1])
    
    tmp_ans = 0
    isCorrect = True
    for j in range(N):
        if(status[j] == 1):
            for xy in xys[j]:

                if(status[xy[0]-1] != xy[1]):
                    isCorrect = False
                    break
            tmp_ans += 1
        if(not isCorrect):
            tmp_ans = 0
            break

    ans = max(ans, tmp_ans)

print(ans)

Solution (Python):
import sys


def main():
    n = int(sys.stdin.readline().strip())
    a = []
    xy = [[] for _ in range(n)]
    for i in range(n):
        ai = (int(sys.stdin.readline().strip()))
        a.append(ai)
        for j in range(ai):
            xij, yij = [int(s) for s in sys.stdin.readline().strip().split()]
            xy[i].append((xij-1, yij))

    
    
    

    
    
    

    def is_possible2(state):
        honests = set()
        unkinds = set()

        for i in range(n):
            if state[i]:
                honests.add(i)
            else:
                unkinds.add(i)

        for i in range(n):
            if state[i]:
                for j in range(len(xy[i])):
                    person, is_honest = xy[i][j]
                    if is_honest:
                        if person in unkinds:
                            return False
                        honests.add(person)
                    else:
                        if person in honests:
                            return False
                        unkinds.add(person)
        return True

    state = [0] * n

    def gen_and_calc(state, pos):
        if pos == n:
            if is_possible2(state):
                return sum(state)
            return 0
        cand = gen_and_calc(state, pos+1)
        state[pos] = 1
        cand2 = gen_and_calc(state, pos+1)
        state[pos] = 0
        return max(cand, cand2)

    print(gen_and_calc(state, 0))


main()

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

    lis.append(copy.deepcopy(li))

mtrue = 0
def mjyun(a):
    flag = 0
    
    for i in range(len(a)):
        if flag == 1:
            break
        b = a[i]
        
        for j in range(len(lis[b])):
            
            if (lis[b][j][1]  == 1 and lis[b][j][0] - 1 not in a) or (lis[b][j][1] == 0 and lis[b][j][0] -1 in a):
                flag = 1
                break

    if flag == 0:
        return len(a)
    else:
        return 0
for i in range(2 ** N):
    
    count = 0
    a = []
    for j in range(N):
        if i & (1 << j) != 0:
            a.append(int(math.log2(i & (1 << j))))

    num = mjyun(a)
    
    if mtrue < num:
        mtrue = num
print(mtrue)

Solution (Python):
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())))
        
ans=0
for i in range(2**n):
    flg=0
    bin_i=format(i, '0{}b'.format(n))
    zero_one=list(bin_i)
    for j in range(n):
        if zero_one[j]=="1":
            for k in xy[j]:
                x,y=k
                if zero_one[x-1]=="1" and y==0:
                    flg=1
                if zero_one[x-1]=="0" and y==1:
                    flg=1

    if flg==0:
        tmp=0
        for w in zero_one:
            if w=="1":
                tmp+=1
        ans=max(ans,tmp)

print(ans)

Solution (Python):
from itertools import combinations

N = int(input())
xys = [
    [tuple(map(int, input().split())) for _ in range(int(input()))] for A in range(N)
]


for ans in range(N, -1, -1):
    
    for c in combinations(range(1, 1 + N), ans):
        honest = [False] * N
        for ci in c:
            honest[ci - 1] = True

        for i, xy in zip(range(1, 1 + N), xys):
            for x, y in xy:
                if y:
                    if honest[i - 1] and not honest[x - 1]:
                        break
                else:
                    if honest[i - 1] and honest[x - 1]:
                        break
            else:
                continue
            break
        else:
            break
        continue
    else:
        continue
    break

print(ans)

Solution (Python):
N = int(input())
A = []
XY = []
for i in range(N):
    a = int(input())
    A.append(a)

    xy = [list(map(int, input().split())) for _ in range(a)]
    XY.append(xy)

V = [False] * N
ans = 0
for i in range(1, 2**N):
    tmp_i = i
    isOK = True
    cnt = 0
    H = [False] * N
    for j in range(N):
        if tmp_i & 1 == 1:
            cnt += 1
            H[j] = True
        tmp_i = tmp_i >> 1
    for j in range(N):
        if H[j] == True:
            for k in range(A[j]):
                status = XY[j][k][1]
                if status != H[XY[j][k][0]-1]:
                    isOK = False
                    break
        if isOK == False:
            break
    if isOK == True:
        ans = max(cnt, ans)
print(ans)

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


q_li = []
for i in range(N):
    q = []
    for _ in range(int(input())):
        a, b = map(int,input().split())
        q.append((a,b)) 
    q_li.append(q)

def f(q_li, i):
    for n, q in enumerate(q_li):
        for a, b in q:
            a = a-1
            if (i >> n) & 1:
                if (i >> a) & 1 != b:
                    return 0
            
            
    return str(bin(i)).count('1')

s_max = 0
for i in range(2 ** N):
    res = f(q_li, i)
    if res > s_max:
        s_max = res 
        
print(s_max)

Solution (Python):
import itertools
import copy
N = int(input())
dic = {}
ans = [1 for _ in range(N)]
trueans = 0
for i in range(N):
  a = int(input())
  dic[i] = []
  for _ in range(a):
    x, y = input().split()
    dic[i].append((int(x),int(y)))
 
def check(dic, ans):
  for k, v in dic.items():
    for x, y in v:
      if ans[k] == 1:
        if ans[x-1] != y:
          return False
  return True
 
slist = []
for i in range(1, N+1):
  slist.append(i)
if check(dic, ans):
  print(N)
else:
  while(True):
    for i in range(1, N+1):
      tmp = list(itertools.combinations(slist,i))
      for t in tmp:
        anstmp = copy.deepcopy(ans)
        for t in t:
          anstmp[t-1] = 0
          flag = check(dic, anstmp)
          if flag:
            break
        if flag:
          break
      if flag:
        trueans = N - i
        break
    if flag:
      break
    break
  print(trueans)