Problem:
 Score : 300 points    Problem Statement There are N people numbered 1 to N . Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.  Person i gives A_i testimonies. The j -th testimony by Person i is represented by two integers x_{ij} and y_{ij} . If y_{ij} = 1 , the testimony says Person x_{ij} is honest; if y_{ij} = 0 , it says Person x_{ij} is unkind.  How many honest persons can be among those N people at most?      Constraints  All values in input are integers.  1 \leq N \leq 15  0 \leq A_i \leq N - 1  1 \leq x_{ij} \leq N  x_{ij} \neq i  x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)  y_{ij} = 0, 1         Input Input is given from Standard Input in the following format:  N  A_1  x_{11}  y_{11}  x_{12}  y_{12}  :  x_{1A_1}  y_{1A_1}  A_2  x_{21}  y_{21}  x_{22}  y_{22}  :  x_{2A_2}  y_{2A_2}  :  A_N  x_{N1}  y_{N1}  x_{N2}  y_{N2}  :  x_{NA_N}  y_{NA_N}       Output Print the maximum possible number of honest persons among the N people.        Sample Input 1 3
1
2 1
1
1 1
1
2 0      Sample Output 1 2  If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.       Sample Input 2 3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0      Sample Output 2 0  Assuming that one or more of them are honest immediately leads to a contradiction.       Sample Input 3 2
1
2 0
1
1 0      Sample Output 3 1

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

ans = 0

for i in range(2 ** N):
    h = [0] * N

    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
    
    flag = False
    for i in range(N):
        if h[i] == 1:
            for x, y in xy[i]:
                if h[x-1] != y:
                    flag = True
                    break
            if flag:
                break
    
    if not flag:
        ans = max(ans, sum(h))

print(ans)

Solution (Python):
N = int(input())
Xs = []
Ys = []
A = []
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-1)
        Y.append(y)
    Xs.append(X)
    Ys.append(Y)
ans = 0

for i in range(2 ** N):
    flag = True
    l = 0
    for j in range(N):
        if i >> j & 1 == 1:
            l += 1
            for k in range(A[j]):
                if Ys[j][k] + (i >> Xs[j][k] & 1) == 1:
                    flag = False
    if flag:
        ans = max(ans, l)

print(ans)

Solution (Python):
from collections import defaultdict


def is_testimony_correct(hypothesis, testimony):
    
    for target, is_honest in testimony.items():
        if int(hypothesis[target]) == is_honest:
            continue
        return False
    return True


def is_hypothesis_correct(hypothesis, testimony_dict):
    for witness_num, testimony in testimony_dict.items():
        
        if hypothesis[witness_num] == "1":
            
            if is_testimony_correct(hypothesis, testimony):
                continue
            else:
                
                return False
    return True


def main():
    N = int(input())
    testimony_dict = defaultdict(dict)

    
    for witness_num in range(N):
        for _ in range(int(input())):
            target, is_honest = list(map(int, input().split()))
            testimony_dict[witness_num][target - 1] = is_honest

    
    max_count = 0
    for i in range(1, 2**N):
        
        hypothesis = format(i, 'b').zfill(N)
        
        if is_hypothesis_correct(hypothesis, testimony_dict):
            max_count = max(max_count, hypothesis.count(str("1")))
    print(max_count)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
l = []
for i in range(n):
    a = int(input())
    for j in range(a):
        a1, a2 = map(int, input().split())
        l.append([i, a1-1, a2])
ans = 0
for i in range(1 << n):
    uso = False
    
    for ll in l:
        
        
        if i >> ll[0] & 1:  
            if ((i >> ll[1]) & 1) == ll[2]:
                pass
            else:
                uso = True
                break
        
        
        
        
    if uso == False:
        
        ans = max(ans, len(str(bin(i)).replace('0b', "").replace('0', "")))
print(ans)

Solution (Python):
n = int(input())
A = [[] for _ in range(n)]
for i in range(n):
    m = int(input())
    for j in range(m):
        A[i].append(tuple(map(int, input().split())))
ans = 0

for bits in range(2 ** n):
    l = [0] * n
    for i in range(n):
        l[i] = (bits >> i) % 2

    fail = False
    for i in range(n):
        if fail: break
        if l[i] == 0: continue
        for x, y in A[i]:
            if y != l[x-1]:
                fail = True
                break
    else:
        if not fail:
            ans = max(ans, sum(l))

print(ans)

Solution (Python):
import sys
N = int(input())
A = []
x = []
y = []

for i in range(N):
    a1 = int(input())
    A.append(a1)
    x1 = []
    y1 = []
    for j in range(a1):        
        x2, y2 = map(int,input().split())
        x1.append(x2)
        y1.append(y2)
    x.append(x1)
    y.append(y1)

ans = []
c = 0
for i in range(1 << N):
    c = 0
    s = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            for k in range(A[j]):
                if (i >> (x[j][k] - 1)) & 1 != y[j][k]:
                    s = 1
                    break
        if s == 1:
            break
    if s != 1:
        for j in range(N):
            if (i >> j) & 1 == 1:
                c += 1
        ans.append(c)
        
print(max(ans))

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


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h = set()
        u = set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for j in range(N):
            if (i >> j) & 1:
                h |= A[j][1]
                u |= A[j][0]
                if u & A[j][1] or h & A[j][0]:
                    b = False
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict


def is_testimony_correct(hypothesis, testimony):
    
    for target, is_honest in testimony.items():
        if int(hypothesis[target]) == is_honest:
            continue
        return False
    return True


def is_hypothesis_correct(hypothesis, testimony_dict):
    for witness_num, testimony in testimony_dict.items():
        
        if hypothesis[witness_num] == "1":
            
            if is_testimony_correct(hypothesis, testimony):
                continue
            else:
                
                return False
    return True


def main():
    N = int(input())
    testimony_dict = defaultdict(dict)

    
    for witness_num in range(N):
        for j in range(int(input())):
            target, is_honest = list(map(int, input().split()))
            testimony_dict[witness_num][target - 1] = is_honest

    
    max_count = 0
    for i in range(1, 2**N):
        
        hypothesis = format(i, 'b').zfill(N)
        
        if is_hypothesis_correct(hypothesis, testimony_dict):
            max_count = max(max_count, hypothesis.count(str("1")))
    print(max_count)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
xys = [[tuple(map(int, input().split())) for j in range(int(input()))] \
       for i in range(n)]

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in xys[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  
        for i in range(N):
            if bit & (1 << i):
                
                
                
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
        
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = [0]*n
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmp1,tmp2 = list(map(int,input().split()))
        x[i].append(tmp1-1)
        y[i].append(tmp2)

ans = 0
honest = [0]*n
cnt=0
for i in range(2**n): 
    for j in range(n):
        if((i>>j)&1):
            honest[j] = 1
            cnt+=1
        else:
            honest[j] = 0
            
    f = True
    for k in range(n):
        if honest[k]!=1:
            continue
        for l in range(a[k]):
            if y[k][l]!=honest[x[k][l]]:
                f = False
                break
    if f:
        ans = max(ans,cnt)
    cnt=0

print(ans)

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

def get_sgs(an):
    sgs = [list(map(int, input().split())) for i in range(an)]
    return sgs


for i in range(n):
    an = int(input())
    Asgs.append(get_sgs(an))

bits = list()
for i in range(2**n):
    bits.append(list(map(int, list(bin(i)[2::].zfill(n)))))


cnt = 0
ps = list()
is_break = False



for i in range(2**n):
    for j in range(n):
        
        
        for k in range(len(Asgs[j])):
            
            if bits[i][j] == 1 and Asgs[j][k][1] == 1 and bits[i][Asgs[j][k][0]-1] == 0:
                
                bits[i] = [0]*n
            elif bits[i][j] == 1 and Asgs[j][k][1] == 0 and bits[i][Asgs[j][k][0]-1] == 1:
                bits[i] = [0]*n
                
    if bits[i] == [1,1,1]:
        print(i,j,k)
        print('ghogegegaega')
    ps.append(sum(bits[i]))
    

print(max(ps))

Solution (Python):
from itertools import product
N=int(input())
XYs = []
for i in range(N):
    A = int(input())
    XYs.append([tuple(map(int, input().split())) for _ in range(A)])

n=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 XYs[i]):
                break
    else:
        n=max(n,sum(ts))
print(n)

Solution (Python):
def main():
    N = int(input())
    S = [[] * N for i in range(N)]
    ans = 0

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

    P = [0]*N
    
    for i in range(2**N):
        for j in range(N):
            if P[j] == 0:
                P[j] = 1
                break
            else:
                P[j] = 0
        
        if sum(P) <= ans:
            continue
        flag = 0
        for p in range(len(P)):
            if P[p] == 1:
                for s in S[p]:
                    if s[1]!= P[s[0]]:
                        flag = 1
        if flag == 1:
            continue
        else:
            ans = sum(P)
        
    print(ans)


 
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
wi = [[] for i in range(N)]
for i in range(N):
    wi[i].append([i,1])
    for j in range(int(input())):
        x,y = map(int,input().split())
        wi[i].append([x-1,y])
ans = 0
for i in range(2**N):
    flag = False
    hoge = 0
    witnes = [0]*N
    for j in range(N):
        if i>>j & 1 == 1:
            hoge += 1
            for x,y in wi[j]:
                if i >> x & 1 != y:
                    flag = True
                    break
        if flag:
            break
    if not flag:
        ans = max(ans,hoge)
print(ans)

Solution (Python):

def main():
    N = int(input())
    S = [[] * N for i in range(N)]
    ans = 0

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

    P = [0]*N
    
    for i in range(2**N):
        for j in range(N):
            if P[j] == 0:
                P[j] = 1
                break
            else:
                P[j] = 0
        
        if sum(P) <= ans:
            continue
        flag = 0
        for p in range(len(P)):
            if P[p] == 1:
                for s in S[p]:
                    if s[1]!= P[s[0]]:
                        flag = 1
        if flag == 1:
            continue
        else:
            ans = sum(P)
        
    print(ans)


 
if __name__ == '__main__':
    main()

Solution (Python):
import collections
import itertools

n = int(input())

per_dict = collections.defaultdict(list)
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    per_dict[i + 1].append([x,y]) 

for i in range(n, -1, -1):
  flag = True
  for honests in itertools.combinations(range(1, n + 1), i):
    flag = True
    for h in honests:
      for x, y in per_dict[h]:
        if y == 1 and x not in honests:
          flag = False 
        if y == 0 and x in honests:
          flag = False
    if flag == True:
      break
  if flag == True:
    break
print(i)

Solution (Python):
N = int(input())
list = [list() for _ in range(N)]
if N == 1:
  print(1)
  exit()

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

ans = 0
for i in range(2**N):
    flg = False
    do = [0] * N
    for j in range(N):
      if ((i >> j) & 1):
        do[j] = 1
    P = [-1] * N
    for n in range(N):
      if flg:break
      for p in list[n]:
        if P[p[0]-1] == -1:
          if do[n] == 1:
            P[p[0]-1] = p[1]
            if P[p[0]-1] != do[p[0]-1]:
              flg = True
          
          
          
          
          
        else:
          if do[n] == 1 and P[p[0]-1] != p[1]:
            flg = True
    if flg:
      continue
    ans = max(ans,sum(do))
print(ans)

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  
        for i in range(N):
            if bit & (1 << i):
                
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        good = False
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
        
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = [0 for i in range(N)]
xy = [[] for i in range(N)]
value = [[] for i in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = LI()
        x -= 1
        xy[i].append([x,y])

def make2digits(n):
    digits = [0 for i in range(N)]
    i = 0
    while n > 0:
        digits[i] = n % 2
        n = n // 2
        i += 1
    return digits

def check(digits, xy):
    for i in range(N):
        if digits[i] == 1:
            for signal in xy[i]:
                if digits[signal[0]] == signal[1]:
                    pass
                else:
                    return False
    return True
ans = -1
for i in range(2**N):
    digits = make2digits(i)
    if check(digits, xy):
        ans = max(ans, sum(digits))

print(ans)

Solution (Python):
N = int(input())
B = [[] for i in range(N)]
C = []
for i in range(N):
  M = int(input())
  C.append(M)
  for j in range(M):
    B[i].append([int(s) for s in input().split()])
    
ans = 0
for i in range(2**N):
    array = bin(i)[2:]
    n = len(array)
    array = "0"*(N-n) + array  
    array = [int(k) for k in list(array)]
    
    
    flag = True
    for j in range(N):
        a = array[j]
        if a==1:
            for e,f in B[j]:
                if f != array[e-1]:
                    flag = False
    if flag==True:
        ans = max(ans, sum(array))
print(ans)

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

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

def solve(state):
    memo = {i: (state >> i & 1) for i in range(N)}
    for i, a in enumerate(A):
        for x, y in a.items():
            if state >> i & 1:
                if x in memo and memo[x] != y:
                    return False
                memo[x] = y
    return True

ans = 0
for i in range(2 ** N):
    if solve(i):
        ans = max(ans, bin(i).count("1"))

print(ans)

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


def countBit(x):
    if x == 0:
        return 0
    else:
        return countBit(x >> 1) + (x & 1)


res = 0
for bits in range(2 ** N):
    bits_ = bin(bits)
    consistency = True
    for i, testimony in enumerate(A):
        if not ((bits >> i) & 1):
            continue
        for t in testimony:
            if ((bits >> t[0]) & 1) ^ t[1]:
                consistency = False

    if consistency:
        res = max(res, countBit(bits))

print(res)

Solution (Python):
import itertools

N = int(input())

xy_list = [{} for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = list(map(int, input().split()))
        xy_list[x-1][str(i)] = y

max_n_honest = 0
for n_honest in range(1, N + 1):
    for is_honest in itertools.combinations(range(N), n_honest):
        aaa = True
        for h_idx in range(N):
            target_is_honest = int(h_idx in is_honest)
            testimony = xy_list[h_idx]
            for honest_idx in is_honest:
                if str(honest_idx) in testimony:
                    if testimony[str(honest_idx)] != target_is_honest:
                        aaa = False
                        break
        if not aaa:
            continue
        n_honest = len(is_honest)

        if n_honest > max_n_honest:
            max_n_honest = n_honest

print(max_n_honest)

Solution (Python):
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n_a = I()
As = [0]
for i in range(n_a):
    n_t = I()
    Ts = []
    for j in range(n_t):
        Ts.append(Is())
    As.append(Ts)

cand = []
def dfs(i,st):
    if i < n_a:
        dfs(i+1,st+[i+1])
        dfs(i+1,st)
    elif i == n_a:
        flag = True
        tf = [None] * (n_a + 1)
        for j in range(1,n_a+1):
            if j in st:
                tf[j] = 1
            else:
                tf[j] = 0
        for j in range(1,n_a+1):
            if j not in st:
                continue
            for e in As[j]:
                x,y = e
                if tf[x] != y:
                    
                    flag = False
        if flag:
            
            cand.append(tf)
dfs(0,[])
ans = 0
for e in cand:
    ans = max(ans,e.count(1))
print(ans)

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

testimony_dict = {}
for i in range(n):
    a = int(input())
    testimony_dict[i + 1] = []
    for j in range(a):
        xy = input().split(' ')
        testimony_dict[i + 1].append(xy)

max_valid_bin = ''
for i in range(2 ** n - 1, 0, -1):
    is_valid = True
    bin_i = format(i, '0{}b'.format(n))
    for j in range(1, len(bin_i) + 1):
        if bin_i[j - 1] == '1':
            for xy_list in testimony_dict[j]:
                if bin_i[int(xy_list[0]) - 1] != xy_list[1]:
                    is_valid = False
    if is_valid:
        max_valid_bin = bin_i
        break

print(len([i for i in max_valid_bin if i == '1']))

Solution (Python):



N = int(input())
M = []
for i in range(N):
    A = int(input())
    XY = []
    for j in range(A):
        X, Y = map(int, input().split())
        XY.append([X, Y])
    M.append(XY)


def check(n, l):
    
    if n == 0:
        l += [1] * (N - len(l))
        return judge(l)
    
    if n == N - len(l):
        l += [0] * (N - len(l))
        return judge(l)

    
    if check(n, l + [1]):
        return True
    
    if check(n - 1, l + [0]):
        return True

    return False


def judge(l):
    for i in range(len(M)):
        
        if l[i] == 0:
            continue
        
        ii = M[i]
        for j in range(len(ii)):
            jj = ii[j]
            if l[jj[0] - 1] != jj[1]:
                return False
    return True


for i in range(N + 1):
    if check(i, []):
        print(N - i)
        break;

Solution (Python):
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = []
B = []

i = 1
for _ in range(n):
    a = int(inputs[i])
    i += 1
    A.append(a)
    B.append([tuple(map(int, inputs[j].split())) for j in range(i, i+a)])
    i += a

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in B[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Solution (Python):
n = int(input())
xy=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xy[i].append(list(map(int,input().split())))
len_xy=len(xy)
ans=0
for i in range(2**n):
    num=str(bin(i))[2:]
    num=list(num.zfill(n))
    flag=True
    for j in range(n):
        if num[j]=='1':
            for x,y in xy[j]:
                if num[x-1]!=str(y):
                    flag=False
    if flag:
        ans=max(ans,num.count('1'))
print(ans)

Solution (Python):
ans=0
n=int(input())
comments={}
for i in range(n):
    num=int(input())
    comment=[]
    for j in range(num):
        comment.append(list(map(int,input().split(" "))))
    comments[i]=comment

for i in range(2**n):
    evidences={}
    people=list(str(format(i,'b').zfill(n)))
    conflict=False
    for idx,person in enumerate(people):
        if person=='1':
            for comment in comments[idx]:
                evidences.setdefault(comment[0],[]).append(comment[1])
    for key,value in evidences.items():
        personality = int(people[key-1])
        if value.count(personality) != len(value):
            conflict=True
            break
    if not conflict:
        ans=people.count('1')
print(ans)

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

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def countHonest(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if honest[x] == 0:
				continue
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		sayArray = sayTable[i]
		for x, y in sayArray:
			if y != honest[x]:
				return False
	return True

def setHonest(sayArray, honest):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n:
		if checkHonestAll(sayTable, honest):
			return countHonest(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	sayArray = sayTable[i]
	if (h == 0 or h == 2) and checkHonest(sayArray, honest):
		copyHonest = honest[:]
		setHonest(sayArray, copyHonest)
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i+1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
	if count < c:
		count = c
	return count

print(search(sayTable, [0] * n, 0))

Solution (Python):
import itertools

def check(honest_people):
	ans = True
	for i in honest_people:
		for x, y in shogen[i]:
			if (y == 1 and x not in honest_people) or (y == 0 and x in honest_people):
				ans = False
	return ans

if __name__ == "__main__":
	N = int(input())
	shogen = []
	for i in range(N):
		A = int(input())
		shogen_i = []
		for i in range(A):
			x, y = map(int, input().split())
			shogen_i.append((x - 1, y))
		shogen.append(shogen_i)

	seq = [i for i in range(N)]
	for i in range(0, N + 1):
		comb = list(itertools.combinations(seq, i))
		for honest_people in comb:
			if check(list(honest_people)):
				ans = i
	print(ans)

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

def count_ones_by_minus(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count

ans=0
for k in range(2**N):
    ok=True
    for i in range(N): 
        
        if k>>i & 1: 
            for j in range(A[i]): 
                if xy[i][j][1] != k >> (xy[i][j][0]-1) &1:
                    ok=False
    
    if ok:
        ans=max(ans,count_ones_by_minus(k))
    

print(ans)

Solution (Python):
A = [0 for _ in range(20)]
X = [[0 for _ in range(20)] for _ in range(20)]
Y = [[0 for _ in range(20)] for _ in range(20)]

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

n = int(input())

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] = 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):
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]




ans = 0
for i in itertools.product([0, 1], repeat=n):
    ok = True
    cnt = sum(i)
    for j in range(n):
        xyj = xy[j]
        if i[j] == 1:
            for xyk in xyj:
                if xyk[1] == 1:
                    if i[xyk[0]-1] == 0:
                        ok = False
                elif xyk[1] == 0:
                    if i[xyk[0]-1] == 1:
                        ok = False
    
    if ok:
        ans = max(ans, cnt)

print(ans)

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

res = 0
for i in range(1<<n):
    flg = True
    cnt = 0
    for j in range(n):
        if ( i >>j & 1 ) == 1:
            cnt += 1
    for j in range(n):
        if ( i >>j & 1 ) == 1:
            for x,y in prf[j]:
                if y == 0 and ( i >> x & 1 ) == 1:
                    flg = False
                if y == 1 and ( i >> x & 1 ) == 0:
                    flg = False
    if flg:
        res = max(res, cnt)
print(res)

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

A = []

x = []
y = []

for i in range(N):
    temp = int(input())
    A.append(temp)
    temp3 = []
    temp4 = []
    for j in range(temp):
        temp1,temp2 = map(int,input().split())
        temp3.append(temp1)
        temp4.append(temp2)
    x.append(temp3)
    y.append(temp4)

res = 0

for i in range(2 ** N):
    isOK = True
    honest = 0
    for j in range(N):
        if ((i >> j) & 1):
            honest += 1
            for k in range(A[j]):
                if (((i >> (x[j][k]-1)) & 1) ^ y[j][k]):
                    isOK = False
    if isOK:
        res = max(res,honest)

print(res)

Solution (Python):
from itertools import combinations
import numpy as np
n = int(input())

testimonies = []

for i in range(n):
    A_i = int(input())
    testimonies.append([])
    for j in range(A_i):
        x_ij, y_ij = map(int, input().split())
        testimonies[i].append([x_ij-1, y_ij])

ans = 0
for i in range(n):
    i = n - i
    contradiction = True
    for honests in combinations(range(n), i):
        contradiction = False
        for testimony in [testimonies[i] for i in honests]:
            for x, y in testimony:
                if (y == 1 and x not in honests) or (y == 0 and x in honests):
                    contradiction = True
                    break
        if not contradiction:
            print(i)
            exit()

print(0)

Solution (Python):
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

N = ri()
A = [[] for _ in range(N)]
for i in range(N):
    a = ri()
    l = []
    for j in range(a):
        x, y = rl()
        l.append((x, y))
    A[i] = l

answer = 0

for i in range(2 ** N):
    honest = [False] * (N+1)
    bool = True
    for j in range(N):
        if ((i >> j) & 1):
            honest[N - j] = True
    for k in range(1, N+1):
        if honest[k] == True:
            
            for x, y in A[k-1]:
                if y == 1 and honest[x] == False:
                    bool = False
                    break
                if y == 0 and honest[x] == True:
                    bool = False
                    break
    if bool and sum(honest) > answer:
        answer = max(answer, sum(honest))

print(answer)

Solution (Python):
n=int(input())
w=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        w[i].append((x,y))
ans=0
for i in range(1<<n):
    x="0"*15+bin(i)[2:]
    z=[int(i) for i in x[-n:]]
    f=1
    for p,q in enumerate(w):
        if z[p]==1:
            for r in q:
                if (z[r[0]-1]!=r[1]):
                    f=0
    if f:
        ans=max(ans,z.count(1))
print(ans)