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):
def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for i in range(1 << N):
    judge = True
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 != Y[j][k]:
                    judge = False
        """else:
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 == Y[j][k]:
                    judge = False"""
    if judge:
        res = max(res,digitSum(i))
print(res)

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

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

ans = 0
for i in range(2**n):
    lst = [0 for _ in range(n)]
    for j in range(n):
        if (i >> j) & 1:
            lst[j] = 1
    
    flag = True
    for j in range(n):
        if lst[j] == 1:
            for x, y in xy[j]:
                if lst[x - 1] != y:
                    flag = False
                    break
            else:
                continue
            break

    if flag:
        ans = max(ans, sum(lst))
print(ans)

Solution (Python):
n = int(input())
Dup = []

for i in range(n):
    a = int(input())
    Dup.append([])
    for j in range(a):
        x,y = map(int, input().split())
        Dup[-1].append((x-1,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 Dup[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())
all_h_or_u = []


for i in range(n) :
    x = int(input())
    h_or_u = []
    for j in range(x) :
        h_or_u.append(list(map(int, input().split())))
    
    for k in range(x) :
        h_or_u[k][0] -= 1
    
    all_h_or_u.append(h_or_u)
    

all_t_or_f = []
for a in range(2 ** n) :
    t_or_f = []
    for b in range(len(bin(2**n)) - 3) :
        if (a >> b) & 1 :
            t_or_f.append(1)
        else :
            t_or_f.append(0)
        
    all_t_or_f.append(t_or_f)


max_cnt = 0
for c in all_t_or_f :
    cnt = 0
    for d in range(n) :
        if c[d] == 1 :
            for e in all_h_or_u[d] :
                if c[e[0]] != e[1] :
                    cnt += 1
    
    if cnt == 0 :
        max_cnt = max(max_cnt, sum(c))
            
print(max_cnt)

Solution (Python):
from itertools import product

n = int(input())

test = []

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

ans = 0

for i in product(range(2), repeat=n):
  flag = True
  for j in range(n):
    if i[j] == 1:
      for s in test[j]:
        if i[s[0]-1] != s[1]:
          flag = False 
          break
  if flag == True:
    cnt = i.count(1)
    if cnt > ans:
      ans = cnt

print(ans)

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

ans = 0

for i in range(2**N):
    b = format(i, "0" + str(N) + "b")
    t = 0
    f = 0
    for j in range(N):
        if b[j] == "1":
            t += 1
            for k in xy[j]:
                if str(k[1]) != b[k[0]-1]:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, t)
        

print(ans)

Solution (Python):
N = int(input())
x = [[0] * (N-1) for _ in range(N)]
y = [[0] * (N-1) for _ in range(N)]
A = [0] * N
for i in range(N):
  A[i] = int(input())
  for j in range(A[i]):
    x[i][j], y[i][j] = list(map(int, input().split()))
n = 2 ** N
Flag = 0
ans = 0
while(n < 2 ** (N+1)):
  Flag = 0
  for i in range(N):
    if(int(bin(n)[i + 3]) == 1):
      for j in range(A[i]):
        if(y[i][j] != int(bin(n)[x[i][j] + 2])):
          Flag = 1
          break
    if(Flag == 1):
      break
  else:
    ans = max(ans, sum(list(map(int,bin(n)[3:]))))
  n += 1
print(ans)

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

for i in range(N):
  a = [-1] * N
  for j in range(int(input())):
    temp = list(map(int, input().split()))
    a[temp[0]-1] = temp[1]
  b.append(a)
  
ans = 0

for i in range(2 ** N):
  temp = list(map(int, list(str(format(i, 'b')).zfill(N))))
  num = 0
  for j, var in enumerate(temp):
    if var == 1:
      for k, var2 in enumerate(b[j]):
        if var2 == -1:
          pass
        elif var2 != temp[k]:
          num = -1
          break
      if num == -1:
        break
      else:
        num += 1
  if num > ans:
    ans = num
print(ans)

Solution (Python):
from itertools import product

n = int(input())

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

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

ans = 0
for a in product([0,1], repeat=n):
    REAL = True
    for i in range(n):
        if a[i] == 1:
            for x, y in memo[i]:
                if a[x] != y:
                    REAL = False
                    break
        if REAL == False:
            break

    if REAL:
        ans = max(ans, sum(a))

print(ans)

Solution (Python):
N=int(input())
XY=[[[]] for n in range(N+1)]
for n in range(1,N+1):
  a=int(input())
  XY[n]=[list(map(int, input().split())) for _ in range(a)]

maxH=0
for mask_i in range(1<<N):
  
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  
  
  ok=True
  for n in range(1,N+1):
    if H[n]==1:
      for x,y in XY[n]:
        if H[x]!=y:
          ok=False
          break
  if ok:
    maxH=max(maxH,sum(H))

print(maxH)

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

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

ans = 0
for i in range(2**n):
    state = [-1]*n
    is_ok = True
    ok_num = 0
    for j in range(n):
        if ((i >> j) & 1):
            if state[j] != 0:
                state[j] = 1
            else:
                is_ok = False
            remark = remark_list[j]
            ok_num += 1
            for r in remark:
                if state[r[0]-1] == -1:
                    state[r[0]-1] = r[1]
                elif state[r[0]-1] != r[1]:
                    is_ok = False
                    break
        else:
            if state[j] != 1:
                state[j] = 0
            else:
                is_ok = False
    if is_ok:
        ans = max(ans, ok_num)
print(ans)

Solution (Python):
n = int(input())
Big_lis = []
A = []

for i in range(n):
    lis = []
    a = int(input())
    A.append(a)
    for j in range(a):
        x, y = map(int, input().split())
        lis.append((x, y))
    Big_lis.append(lis)
ANS = 0

for i in range(2 ** n):
    check = bin(i)[2:]
    check = '0' * (n - len(check)) + check
    ans = check.count('1')
    for j in range(n):
        if i >> j & 1:
            for k in range(A[j]):
                if str(check[n - Big_lis[j][k][0]]) != str(Big_lis[j][k][1]):
                    ans = 0
    ANS = max(ANS, ans)
print(ANS)

Solution (Python):
import itertools

N = int(input())
As = []
xys = []
for _ in range(N):
    a = int(input())
    As.append(a)
    xys.append([tuple(map(int, input().split())) for _ in range(a)])


ans = -1
for is_shoziki in itertools.product([1, 0], repeat=N):
    n = sum(is_shoziki)
    if n <= ans:
        continue
    flg = True
    for i in range(N):
        if not flg:
            break
        if is_shoziki[i] == 0:
            continue
        for x, y in xys[i]:
            if is_shoziki[x - 1] != y:
                flg = False
                break
    if flg:
        ans = n

print(ans)

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

W = [[-1]*N for _ in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = [int(z) for z in input().split()]
        x -= 1
        W[i][x] = y

M = 0
for b in range(2**N):

    d = [0] * N
    for i in range(N):
        if (b >> i) & 1:
            d[i] = 1
    
    ok = True
    for i in range(N):
        if d[i] == 1:
            for j in range(N):
                if W[i][j] == -1:
                    continue
                if W[i][j] != d[j]:
                    ok =False

    if ok == True:
        M = max(M, sum(d))

print(M)

Solution (Python):
import itertools

n = int(input())
tes = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        tes[i].append([x - 1, y])
ans = 0 
for tf_s in itertools.product(range(2), repeat = n):
    for i in range(n):
        if tf_s[i] == 0:
            continue
        for x, y in tes[i]:
            if tf_s[x] != y:
                break
        else:
            continue
        break
    else:
        ans = max(ans, tf_s.count(1))
print(ans)

Solution (Python):


n=int(input())

class People:
    def __init__(self):
        self.type=None

peoples=[People() for i in range(n+1)]

def change_10to2(i):
    ans=format(i, '
    return ans

def set_people_type(binary_list,peoples):
    for i,people in enumerate(peoples):
        if i!=0:
            people.type=binary_list[i]

def get_statement():
    shougen={}
    for i in range(1,n+1):
        ai=int(input())
        ans=[]
        for j in range(ai):
            kumi=[int(k) for k in input().split()]
            ans.append(kumi)
        shougen[str(i)]=ans
    return shougen

shougens=get_statement()

def shougen_dicide(peoples,shougens):
    for i in range(1,n+1):
        shougen=shougens[str(i)]
        for shou in shougen:
            people,type=shou
            people=int(people)
            type=str(type)
            
            if peoples[i].type=="1":
                if peoples[people].type!=type:
                    return False

            
            
            
            
    return True



ans=0
for i in range(2**n):
    binary_list=change_10to2(i)
    set_people_type(binary_list,peoples)
    if shougen_dicide(peoples,shougens):
        ans=max(ans,binary_list.count("1"))
print(ans)

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(list(map(int, input().split())))
ans = 0
for s in range(1 << N):
  
  state = [(s >> j) & 1 for j in range(N)]
  f = 0
  for i in range(N):
    if state[i] == 0:
      continue
    for x in X[i]:
      if state[x[0]-1] != x[1]:
        f = 1
        break
    if f == 1:
      break
  if f == 0:
    ans = max(ans, sum(state))
print(ans)

Solution (Python):
n=int(input())
COM=[[] for i in range(n)]

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

ans=0
for i in range(2**n):
    sco=bin(i).count("1")
    if sco<=ans:
        continue
    end=False
    
    for q in range(n):
        if (i>>q)&1==1:
            for que in COM[q]:
                
                if (i>>que[0])&1!=que[1]:
                    end=True
                    break
            if end:
                break
    if end:
        continue
    
    ans=sco
print(ans)

Solution (Python):
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xy[i].append(list(map(int, input().split())))
ans = 0
for i in range(2**n):
    tf = [False for j in range(n)]
    for j in range(n):
        if (i>>j)&1:
            tf[j] = True
    flag = False
    for j in range(n):
        for k in range(a[j]):
            if tf[j]:
                if xy[j][k][1] != tf[xy[j][k][0]-1]:
                    flag = True
                    break
        if flag:
            break
    else:
        ans = max(ans, tf.count(True))
print(ans)

Solution (Python):
N = int(input())
shougen = [[] for _ in range(N)]
for k in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        shougen[k].append((x, y))
ans = 0
bit = 2**N-1
while bit:
    person = [-1 for _ in range(N)]
    b = bit
    count = 0
    while count < N:
        person[count] = b & 1
        b >>= 1
        count += 1
    flag = True
    for k in range(N):
        if person[k] == 1:
            for x, y in shougen[k]:
                if person[x] != y:
                    flag = False
                    break
            else:
                continue
            break
    if flag:
        ans = max(ans, sum(person))
    bit -= 1
print(ans)

Solution (Python):
n=int(input())
l=[]
lis=[]
for _ in range(n):
    a=int(input())
    l.append(a)

    li=[]
    for _ in range(a):
        c,d=map(int,input().split())
        li.append([c,d])
    lis.append(li)

ans=-1
for i in range(2**n-1,-1,-1):
    mark=bin(i)[2:]
    mark=(n-len(mark))*'0'+mark
    s=0
    record=[-1]*n
    f=1
    for j in range(n):
        for k in range(l[j]):
            number=lis[j][k][0]-1
            hou=lis[j][k][1]
            if int(mark[j])==1:
                if record[number]==-1:
                    record[number]=hou
                elif record[number]!=hou:f=0
            if f==0:break
        if f == 0: break

    if f==1:
        F=True
        for i in range(n):
            if record[i]!=-1:
                if record[i]!=int(mark[i]):
                    F=False
                    break
        if F==True:
            print(mark.count('1'))
            exit()

Solution (Python):
N=int(input())
testimony=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        testimony[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if testimony[j][k]==-1:
                    continue
                if testimony[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)

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







def F(i):
    cnt = 0
    B = [-1]*N                
    r = 0
    for j in range(N):    
        if (i>>j)&1:         
            r += 1               
            if B[j] == 0:     
                return 0
            B[j]=1              
            for p,q in A[j]: 
                if q == 0:
                    if B[p-1]==1:  
                        return 0
                    B[p-1] = 0  
                else:
                    if B[p-1]==0:  
                        return 0
                    B[p-1] = 1      
            else:
                cnt += 1          
        else:         
            if B[j]==1:       
                return 0
            B[j]=0
            
    if cnt == r:
        return cnt

ans = 0
for i in range(1<<N):
    ans = max(ans,F(i))
print(ans)

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

ans=[]
for i in range(2**N):
    Bit = [1]*N
    for j in range(N):
        if (i >> j) & 1:
            Bit[j] = 0
    i=0
    no=0
    while i<N:
        if Bit[i]==1:
            for x,y in A[i]:
                if Bit[x-1]!=y:
                    no=1
        i+=1
    if no:
        ans.append(0)
    else:
        ans.append(Bit.count(1))

print(max(ans))

Solution (Python):
def main():
	N = int(input())
	A = [[] for i in range(N)]
	
	for i in range(N):
		a = int(input())
		for j in range(a):
			x, y = [int(b) for b in input().split(" ")]
			A[i].append([x - 1, str(y)])

	cand = []
	for i in range(2 ** N):
		honest_flag = True
		bit = list(pad_zero(format(i, 'b'), N))
		honests = [int(p) for p, q in enumerate(bit) if q == "1"]
		for honest in honests:
			w = A[honest]
			for k in range(len(w)):
				if w[k][1] != bit[w[k][0]]:
					honest_flag = False
		if honest_flag:
			cand.append(len(honests))

	print(max(cand))


def pad_zero(s, n):
	s = str(s)
	return ("0" * n + s)[-n:]

main()

Solution (Python):


from itertools import product
n = int(input())
Ev = [[] for _ in range(n)]

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

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

ans = 0
for b in bit:
    for i, v in enumerate(b):  
        if v == 1:
            for x, y in Ev[i]:  
                if b[x] != y:  
                    break
            else:
                continue
            break
    else:
        ans = max(b.count(1), ans)

print(ans)

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

dic = {(i,j):set([]) for i in range(1,N+1) for j in range(2)}

for i in range(1,N+1):
  a = int(input())
  for _ in range(a):
    x,y = map(int, input().split())
    dic[(i,y)].add(x)
    
p = 2**N
rlt = 0

for b in range(p):
  s0 = set([])
  s1 = set([])
  for i in range(N):
    if b&(1<<i):
      s1.add(i+1)
    else:
      s0.add(i+1)
  f = 1
  for i in s1:
    for k in dic[(i,1)]:
      if k in s0:
        f = 0
        break
    for k in dic[(i,0)]:
      if k in s1:
        f = 0
        break
    if f == 0:
      break
  if f == 1:
    rlt = max(len(s1),rlt)
    
print(rlt)

Solution (Python):






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





ans = 0
for i in range(2**N):
    for j,a_list in enumerate(xy_list):
        if (i>>j)&1 == 1:
            for k,(x,y) in enumerate(a_list):
                if (i>>(x-1))&1 != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Solution (Python):
n = int(input())
g = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        g[i].append((x-1,y))
ans = 0
for bit in range(1<<n):
    f = True
    for i in range(n):
        if bit&(1<<i) and f:
            for x,y in g[i]:
                if y ==1 and bit&(1<<x):
                    continue
                elif y ==0 and bit&(1<<x)==0:
                    continue
                else:
                    f = False
                    break
    if f:
        ans = max(ans,bin(bit).count('1'))
print(ans)

Solution (Python):

n=int(input())
l=[]
for i in range(n):
  a=int(input())
  l_=[]
  for j in range(a):
    xy=list(map(int,input().split()))
    l_.append(xy)
  l.append(l_)
ans=0
for i in range(2**n):
  table=[0]*n
  flag=False
  for j in range(n):
    if (i>>j)&1:
      table[j]=1
  for j in range(n):
    for k in l[j]:
   
      if k[1]!=table[k[0]-1] and table[j]==1:
        flag=True
        break

        if flag:
          break

  if flag==True:
    continue


  ans = max(ans, table.count(1))


print(ans)

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

ans=0
for r in range(2**n):
  ans1=0
  za=[0 for i in range(n)]
  for w in range(n):
    if (r>>w)&1:
      ans1+=1
      za[w]+=1
  ch=0
  for h in range(n):
    if za[h]==1:
      for p in s[h]:
        A=p[0]-1
        B=p[1]
        if za[A]!=B:
          ch+=1
  if ch==0:
    ans=max(ans,ans1)
    
print(ans)

Solution (Python):

N = int(input())
A = []
X = []
Y = []
for _ in range(N):
    a = int(input())
    A.append(a)
    box_x = []
    box_y = []
    for _ in range(a):
        x,y = map(int,input().split())
        box_x.append(x)
        box_y.append(y)
    X.append(box_x)
    Y.append(box_y)

person = [2]*N

maxim = 0
for i in range(1<<N):
    c_person = person.copy()
    honest = 0
    for j in range(N):
        mask = 1<<j
        if mask&i != 0:
            c_person[j] = 1
        else:
            c_person[j] = 0
    
    for k,l in enumerate(c_person):
        
        if l == 1:
            
            for m,n in zip(X[k],Y[k]):
                
                if c_person[m-1] != n:
                    honest = 0
                    break
            else:
                honest = sum(c_person)
                continue
            break
    maxim = max(maxim,honest)
                
print(maxim)

Solution (Python):
N=int(input())
T=[[] for _ in range(N)]
for i in range(N):
  n=int(input())
  for j in range(n):
    T[i].append(tuple(map(int,input().split())))
ans=0
for i in range(2**N):
  true,t,f=set(),set(),set()
  for j in range(N):
    if i>>j&1:
      true.add(j+1)
      for a,b in T[j]:
        if b:
          t.add(a)
        else:
          f.add(a)
  if t<=true and not(f&true):
    ans=max(ans,len(true))
print(ans)

Solution (Python):
import itertools
n=int(input())
s=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=[int(x) for x in input().split()]
    x-=1
    s[i].append([x,y])

l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

ans=0
for i in range(2**n):
  c=[]
  for j in range(n):
    if l[i][j]==1:
      for k in s[j]:
        if l[i][k[0]]!=k[1]:
          c.append(False)
  if c==[]:
    ans=max(ans,sum(l[i]))
print(ans)

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

ans=0

for katei in range(2**n):
    hantei=katei
    muzyun=False
    for i in range(1,n+1):
        if hantei & 1:
            for j in range(len(syougen[i])):
                taisyou=syougen[i][j][0]
                if katei>>taisyou-1 & 1 != syougen[i][j][1]:
                    muzyun=True
                    break
        hantei>>=1
    if muzyun==False:
        ans=max(bin(katei).count("1"),ans)

print(ans)

Solution (Python):
n = int(input())
ans = 0
al = []
xy = [[] for _ in range(n)]
for k in range(n):
    a = int(input())
    al.append(a)
    for l in range(a):
        x,y = map(int,input().split())
        xy[k].append([x,y])
for i in range(2**n):
    kinds = [0]*n
    jud = 1
    for j in range(n):
        if (i >> j) & 1:
            kinds[j] = 1
    for k in range(n):
        if kinds[k] == 1:
            a = al[k]
            for l in range(a):
                x = xy[k][l][0]
                y = xy[k][l][1]
                if kinds[x-1] != y:
                    jud = 0
    if jud == 1:
        ans = max(ans,kinds.count(1))
print(ans)

Solution (Python):



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        f = True
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        f = False
                        break
        if f == True:
            ans = max(ans, bin(bit).count("1"))
    print(ans)


if __name__ == "__main__":
    
    resolve()

Solution (Python):



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    C = []
    for i in range(N):
        a = int(input())
        C.append([list(map(int, input().split())) for j in range(a)])

    ans = 0
    for bit in range(1 << N):
        t = 0
        for i in range(N):
            if bit & (1 << i):
                for c in C[i]:
                    if bit & (1 << c[0]-1) != (1 << c[0]-1)*c[1]:
                        break
                else:
                    t += 1
        if t == bin(bit).count("1"):
            ans = max(ans, t)
    print(ans)


if __name__ == "__main__":
     
     resolve()

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

ans = 0
for i in range(2 ** N):
    tf = [False] * N
    for j in range(N):
        if (i >> j) & 1:
            tf[j] = True
    flag = False
    for j in range(N):
        for k in xy[j]:
            
            if tf[j] and k[1] != tf[k[0] - 1]:
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, tf.count(True))
print(ans)

Solution (Python):
n = int(input())
a = [0] * n
xy = [[]] * n
for i in range(n):
    a[i] = int(input())
    xy[i] = [list(map(int, input().split())) for j in range(a[i])]
ans = 0
for i in range(2**n):
    tf = [False] * n
    for j in range(n):
        if (i>>j) & 1:
            tf[j] = True
    flag = False
    for j in range(n):
        for k in xy[j]:
            if tf[j] and k[1] != tf[k[0]-1]:
                flag = True
                break
        if flag:
            break
    if flag:
        continue
    ans = max(ans, tf.count(True))
print(ans)

Solution (Python):
n = int(input())
h = [[] for _ in range(n)]
u = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        if y == 1:
            h[i].append(x)
        elif y == 0:
            u[i].append(x)

ans = 0
for i in range(2**n):
    hs, us = set(), set()
    honest, unkind = set(), set()
    for j in range(n):
        if i & (1 << j):
            hs |= set(h[j])
            us |= set(u[j])
            honest.add(j+1)
        else:
            unkind.add(j+1)
    if not hs <= honest:
        continue
    if not us <= unkind:
        continue
    ans = max(ans, len(honest))

print(ans)

Solution (Python):



n=int(input())
w=[]
ans=chk=0
for i in range(n):
    a=int(input())
    t=[]
    for j in range(a):
        x,y=map(int,input().split())
        t.append((x,y))
    w.append(t)
for i in range(1,2**n):
    l=[0]*n
    for j in range(n):
        if i&1: l[j]=1
        i=i>>1
    chk=1
    for j in range(n):
        if l[j]:
            for k in w[j]:
                if l[k[0]-1]!=k[1]:
                    chk=0
                    break
    if chk: ans=max(ans,sum(l))
print(ans)

Solution (Python):
import itertools

n=int(input())

lis=[]
for i in range(n):
    ai=int(input())
    lisi=[]
    for _ in range(ai):
        xi,yi=map(int,input().split())
        lisi.append([xi-1,yi])
    lis.append(lisi)


ans=-1
for binary in itertools.product([1,0],repeat=n):
    check=0
    for i in range(n):
        if binary[i]==1:
            for j in range(len(lis[i])):
                if binary[lis[i][j][0]]!=lis[i][j][1]:
                    check+=1
    if check==0:
        ans=max(ans,sum(binary))

print(ans)

Solution (Python):
import itertools

N = int(input())

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

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

ans = 0


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

for p in perm:
    flag = True
    
    for j in range(N):
        
        if flag == False:
            break
        
        for k in range(N):
            
            if p[j] == 1:
                
                
                if l[j][k] != -1 and l[j][k] != p[k]:
                    flag = False
                    break

    
    
    if flag == True:
        ans = max(ans, sum(p))

print(ans)

Solution (Python):
from itertools import combinations
n = int(input())
state = [None] + [[set(),set()] for _ in range(n)]

for i in range(1,n+1):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        if y == 0:
            state[i][0].add(x)
        if y == 1:
            state[i][1].add(x)

ans = 0

for i in range(1,n+1):
    
    for j in combinations(list(range(1,n+1)), i):
        assum = set(j)
        state_lst = []
        
        for each_state in j:
            state_lst.append(state[each_state])
        
        for each_state in state_lst:
            crr0 = assum.isdisjoint(each_state[0])
            crr1 = assum >= each_state[1]
            crr = crr0 and crr1
            if not crr:
                break
        else:
            ans = i

print(ans)