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

def main():
    N = int(input())
    xy = [0] * N
    for i in range(N):
        A = int(input())
        xy_list = []
        for _ in range(A):
            x, y = map(int, input().split())
            xy_list.append((x, y))
        xy[i] = xy_list

    res = 0
    tf_gen = itertools.product([0, 1], repeat=N)
    for tf in tf_gen:
        honest = sum(tf)
        able = True
        for i, xy_l in enumerate(xy):
            for (x, y) in xy_l:
                if tf[x-1] != y and tf[i] == 1:
                    able = False
        if res < honest and able:
            res = honest
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
fo_x = '0' + str(n) + 'b'
a = [None] * n
x = [None] * n
y = [None] * n
ans = 0
flag = 0
for i in range(n):
    a[i] = int(input())
    ax = [None] * a[i]
    ay = [None] * a[i]
    for j in range(a[i]):
        ax[j],ay[j] = map(int,input().split())
    x[i] = ax
    y[i] = ay

for i in range(2 ** n):
    b = format(i,fo_x)
    for j in range(len(b)):
        if b[j] == '0':
            continue
        for z in range(a[j]):
            if str(y[j][z]) != b[x[j][z]-1]:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0:
        ans = max(ans,b.count('1'))
    flag = 0
print(ans)

Solution (Python):
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N=II()
ans=0
List=[[-1 for _ in range(N)] for _ in range(N)]
for j in range(N):
  A=II()
  for i in range(A):
    x,y=MI()
    x-=1
    List[j][x]=y
for i in range(1<<N):
  honests=[0]*N
  for j in range(N):
    if 1&(i>>j):
      honests[j]=1
  ok=True
  for j in range(N):
    if honests[j]:
      for k in range(N):
        if List[j][k]==-1:
          continue
        if List[j][k]!=honests[k]:
          ok=False
  if ok:
    ans=max(ans,honests.count(1))
print(ans)

Solution (Python):
n = int(input())
ans = [1]*n
T = [[-1]*n for _ in range(n)]
for ni in range(n):
    a = int(input())
    for ai in range(a):
        x, y = map(int,input().split())
        T[ni][x-1] = y

mx = 0
for i in range(pow(2,n)):
    tmx = -1
    B = bin(i)[2:].zfill(n)
    S = [i for i,b in enumerate(B) if b=='1']
    for s in S:
        _Ts = [i for i,t in enumerate(T[s]) if t==1]
        _Tf = [i for i,t in enumerate(T[s]) if t==0]
        if not (set(_Ts)<=set(S) and set(_Tf)&set(S)==set()):
            tmx = 0
            break
    if tmx==-1: tmx=len(S)
    mx = max(mx, tmx)
print(mx)

Solution (Python):
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
    
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1
      
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
          
  if ok:
    ans = max(ans, honests.count(1))
print(ans)
'''
・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、
その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。
ある人に対して矛盾する二つの証言があるとき、
どちらか一方の証言は必ず仮定に矛盾する。したがって、
この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、
正直者が最も多い組の正直者の人数を求めれば良い。
人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で
格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため
0から始めるものとする。
・人xが人yに対して正直者であると証言するとき、
二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき
二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、
二次元配列g[x][y]を-1にする。
・入力よりNの最大が15なので、
15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。
人iが「人xはyである」と証言しているときg[i][x]=yである。
（入力で受け取る「人の番号」は1から始まるため、
コードでは受け取った値から1引いている。）
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y
二次元配列gの作成と入力の受け取りは以上である。
次に問題を解く中心となるコードを実装していく。
まず、全ての正直者の組を表現するために二進数表記を用いることを考える。
二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
作り出した正直者の組それぞれに対して何らかの処理を行うため、
これは全bit探索である。
「正直者の組を作りだす」部分のコード。
・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。
for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
honests[j]が1であることは,人jは正直者であると仮定することに対応する。
次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち
正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。
・求める値「N人のうち正直者であり得る最大人数」を格納するための
変数ansをデフォルト値0で用意しておく。
求める値は0以上の値であり以下のループ処理によって、
より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値
Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。
honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので
変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を
数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。
'''

Solution (Python):
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1
  ok = True
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))
print(ans)
'''
・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、
その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。
ある人に対して矛盾する二つの証言があるとき、
どちらか一方の証言は必ず仮定に矛盾する。したがって、
この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、
正直者が最も多い組の正直者の人数を求めれば良い。
人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で
格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため
0から始めるものとする。
・人xが人yに対して正直者であると証言するとき、
二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき
二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、
二次元配列g[x][y]を-1にする。
・入力よりNの最大が15なので、
15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。
人iが「人xはyである」と証言しているときg[i][x]=yである。
（入力で受け取る「人の番号」は1から始まるため、
コードでは受け取った値から1引いている。）
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y
二次元配列gの作成と入力の受け取りは以上である。
次に問題を解く中心となるコードを実装していく。
まず、全ての正直者の組を表現するために二進数表記を用いることを考える。
二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
作り出した正直者の組それぞれに対して何らかの処理を行うため、
これは全bit探索である。
「正直者の組を作りだす」部分のコード。
・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。
for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
honests[j]が1であることは,人jは正直者であると仮定することに対応する。
次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち
正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。
・求める値「N人のうち正直者であり得る最大人数」を格納するための
変数ansをデフォルト値0で用意しておく。
求める値は0以上の値であり以下のループ処理によって、
より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値
Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。
honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので
変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を
数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。
'''

Solution (Python):
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1     
  ok = True  
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))
print(ans)
'''
・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、
その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。
ある人に対して矛盾する二つの証言があるとき、
どちらか一方の証言は必ず仮定に矛盾する。したがって、
この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、
正直者が最も多い組の正直者の人数を求めれば良い。
人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で
格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため
0から始めるものとする。
・人xが人yに対して正直者であると証言するとき、
二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき
二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、
二次元配列g[x][y]を-1にする。
・入力よりNの最大が15なので、
15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。
人iが「人xはyである」と証言しているときg[i][x]=yである。
（入力で受け取る「人の番号」は1から始まるため、
コードでは受け取った値から1引いている。）
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y
二次元配列gの作成と入力の受け取りは以上である。
次に問題を解く中心となるコードを実装していく。
まず、全ての正直者の組を表現するために二進数表記を用いることを考える。
二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
作り出した正直者の組それぞれに対して何らかの処理を行うため、
これは全bit探索である。
「正直者の組を作りだす」部分のコード。
・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。
for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
honests[j]が1であることは,人jは正直者であると仮定することに対応する。
次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち
正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。
・求める値「N人のうち正直者であり得る最大人数」を格納するための
変数ansをデフォルト値0で用意しておく。
求める値は0以上の値であり以下のループ処理によって、
より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値
Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。
honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので
変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を
数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。
'''

Solution (Python):
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y
for i in range(1<<n):
  honests = [0 for _ in range(n)]
  for j in range(n):
    if (i>>j) &1:
      honests[j] = 1     
  ok = True  
  for j in range(n):
    if honests[j]:
      for k in range(n):
        if g[j][k] == -1: continue
        if g[j][k] != honests[k]: ok = False
  if ok:
    ans = max(ans, honests.count(1))
print(ans)

Solution (Python):
n = int(input())
evidences = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
result = 0
for i in range(1, 2**n):
    consistent = True 
    for j in range(n):
        if (i>>j) & 1 == 0:
            continue 
        for x, y in evidences[j]:
            if (i>>x)&1 != y:
                consistent = False 
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

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

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

honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: 
            for person_state in xy[j]:
                if (i >> (person_state[0]-1) & 1) != person_state[1]:
                    flag = 1 
                    break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]

print(max(honest))

Solution (Python):
N = int(input())
Z = []
max = 0
for i in range(N):
    A = int(input())
    Z.append([list(map(int, input().split())) for i in range(A)])
for a in range(2 ** N):
    flag = 1
    for i in range(N):
        if (((a >> i) + 1) & 1):
            continue
        z = Z[i]
        for x in z:
            if not (((a >> (x[0] - 1)) + 1 - x[1]) & 1):
                flag = 0
                break
        if flag == 0:
            break
    if flag == 1:
        x = bin(a).count('1')
        if x > max:
            max = x
print(max)

Solution (Python):
N = int(input())
Z, W = [], []
for i in range(N):
    A = int(input())
    Z.append([list(map(int, input().split())) for i in range(A)])
for a in range(2 ** N):
    flag = 1
    for i in range(N):
        if (((a >> i) + 1) & 1):
            continue
        z = Z[i]
        for x in z:
            if not (((a >> (x[0] - 1)) + 1 - x[1]) & 1):
                flag = 0
                break
        if flag == 0:
            break
    if flag == 1:
        W.append(a)
W = [bin(x).count("1") for x in W]
print(max(W))

Solution (Python):
n = int(input())
lists = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        lists[i].append((x-1, y))
ans = 0
for i in range(1, 2**n):
    status = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for x, y in lists[j]:
            if (i >> x) & 1 != y:
                status = False
                break
        if status == False:
            break
    if status == True:
        ans = max(ans, bin(i).count('1'))
print(ans)

Solution (Python):
N = int(input())
A = [0]*N
X = [0]*N
Y = [0]*N
for i in range(N):
    A[i] = int(input())
    Xsmall = [0]*A[i]
    Ysmall = [0]*A[i]
    for j in range(A[i]):
        Xsmall[j],Ysmall[j] = map(int,input().split())
    X[i] =Xsmall
    Y[i] = Ysmall

opinions = []
for i in range(N):
    opinion = [-1]*N
    for j in range(A[i]):
        if Y[i][j] == 0:
            opinion[X[i][j]-1] = 0
        elif Y[i][j] == 1:
            opinion[X[i][j]-1] = 1
    opinions.append(opinion)
answer = 0


for i in range(2**N):
    check = 0
    count = 0
    
    for j in range(N):
        if ((i >> (N-j-1)) & 1) == 1:
            count += 1
            for k in range(A[j]):
                num = X[j][k]
                if ((i >> (N-num)) & 1) == Y[j][k]:
                    
                    continue
                else:
                    check = -1
                    break
            
    
    if check == 0:
        answer = max(answer,count)
    
    
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N  = int(input())
    R = [[] for i in range(N)]
    for i in range(N):
        A = int(input())
        R[i] = [list(map(int, input().split())) for i in range(A)]
    ans = 0
    for i in range(1<<N):
        CNT = 0
        for j in range(N):
            if not (i>>j & 1):
                continue
            CNT += 1
            for x, y in R[j]:
                if y == 1 and (i>>(x-1) & 1):
                    continue
                elif y == 0 and (not (i>>(x-1) & 1)):
                    continue
                else:
                    CNT = 0
                    break
            else:
                continue
            break

        ans = max(ans, CNT)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, a, s, h = int(input()), [], [], []
for i in range(n): a.append(int(input())); s.append(list(list(map(int, input().split())) for _ in range(a[i])))
for i in range(2 ** n):
    flag = False
    for j in range(n):
        if (i >> j) & 1:
            for ps in s[j]:
                if (i >> (ps[0]-1) & 1) != ps[1]: flag = True; break
    if not flag: h.append(bin(i)[2:].count('1'))
print(max(h))

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


mx=0
for mask in range(1<<n):
    honest=[0]*n
    clear=True
    for i in range(n):
        if ((mask>>i)&1)==0:
            honest[i]+=1
    for i in range(n):
        if honest[i]==1:
            for k in range(a[i]):
                if honest[l[i][k][0]-1]!=l[i][k][1]:
                    clear=False
    if clear:
        ans=sum(honest)
        mx=max(ans,mx)

print(mx)

Solution (Python):
n= int(input())
test = [[]for _ in range(n)]
for i in range(n):
    num = int(input())
    for j in range(num):
     a, b= map(int,input().split())
     test[i].append([a-1,b])
ans = 0
for i in range(1,2**n):
    flag = 0
    for j in range(n):
        if(i>>j)&1 == 1:
            for x,y in test[j]:
                if(i>>x)&1 !=y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans,bin(i)[2:].count('1'))
print(ans)

Solution (Python):
n = int(input())
a = []
xy = []
for i in range(n):
    a += [int(input())]
    xy += [[list(map(int,input().split())) for i in range(a[i])]]
honest = []
for i in range(2 ** n):
    flag = 0
    for j in range(n):
        if (i >> j)&1 == 1: 
            for person_state in xy[j]:
              if (i >> (person_state[0]-1) & 1) != person_state[1]:
                  flag = 1 
                  break
    if flag == 0:
        honest += [bin(i)[2:].count("1")]
print(max(honest))

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

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

ok_ls = []
for i in range(2**n):
    ok = 1
    people = [0]*n
    for j in range(n):
        if i >> j & 1:
            people[j] = 1
    for j in range(n):
        if people[j] == 1:
            for xy in xy_ls[j]:
                if xy[1] != people[xy[0]-1]:
                    ok = 0
    if ok:
        ok_ls.append(len([i for i in people if i == 1]))

print(max(ok_ls))

Solution (Python):
import sys

N = int(input())
List = [[-1] * N for i in range(N)]

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

Max = 0

for i in range(2 ** N):

    flag = True
    Sum = 0
    for j in range(N):  
        if ((i >> j) & 1):  
            for k in range(N):
                if (List[j][k] != int((i >> k) & 1)) and List[j][k] != -1:
                    flag = False
            Sum += 1

    if flag:
        
        Max = max(Max, Sum)

print(Max)

Solution (Python):
n = int(input())
evidences = [[] for _ in range(n)]
for i in range(n):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x-1, y))
result = 0
for i in range(1, 2**n):
    consistent = True 
    for j in range(n):
        if (i>>j) & 1 == 0:
            continue 
        for x, y in evidences[j]:
            if (i>>x)&1 != y:
                consistent = False 
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Solution (Python):
from itertools import product 
n=int(input())
x=[]
ans=0
for _ in range(n):
    temp=[]
    A=int(input())
    for _ in range(A):
        temp.append(list(map(int,input().split())))
    x.append(temp)
for i in product([0,1],repeat=n):
    for j in range(n):
            for k in x[j]:
                if i[k[0]-1]!=k[1] and i[j]==1:
                    break
            else:
                continue
            break
    else:
      ans=(max(ans,list(i).count(1))) 
print(ans)

Solution (Python):
import os, sys, re, math

N = int(input())
honest = []
liar = []

for i in range(N):
    a = int(input())
    h = []
    l = []
    for j in range(a):
        (x, y) = [int(n) for n in input().split()]
        if y == 1:
            h.append(x)
        else:
            l.append(x)
    honest.append(h)
    liar.append(l)

answer = 0
for i in range(2 ** N - 1, -1, -1):
    b = ('{:0%db}' % N).format(i)
    truth = True
    for j in range(N):
        if b[j] == '1':
            for h in honest[j]:
                if b[h - 1] != '1':
                    truth = False
                    break
            if not truth:
                break
            for l in liar[j]:
                if b[l - 1] != '0':
                    truth = False
                    break
        if not truth:
            break
    if truth:
        answer = max(answer, len(b.replace('0', '')))

print(answer)

Solution (Python):
N = int(input())
A = {}

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

ans = 0

for bit in range(2**N):
    tmp = bit
    flag = True
    
    for i in range(N):
        if not (bit >> i & 1):  
            continue
        
        for x, y in A[i]:
            if (bit >> (x - 1) & 1) != y:   
                flag = False
                break
    if flag:
        ans = max(ans, bin(bit).count("1"))
print(ans)

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

for i in range(2**n):
    honest = []
    contradiction_f = False

    for j in range(n):
        if i>>j & 1:
            honest.append(j)

    for j in honest:
        judge = lst[j]
        for k in judge:
            if k[1] == 1:
                if not k[0] in honest:
                    contradiction_f = True
                    break
            else:
                if k[0] in honest:
                    contradiction_f = True
                    break

    if not contradiction_f:
        ans = max(ans, len(honest))

print(ans)

Solution (Python):
import sys
import math
n=int(input())
A=[]
xy=[[]]*n
for i in range(n):
    a=int(input())
    A.append(a)
    xy[i]=[list(map(int,input().split())) for _ in range(a)]

ans=0

for bit in range(1<<n):
    tmp=0
    for i in range(n):
        if bit>>i & 1:
            cnt=0
            for elem in xy[i]:
                if elem[1]==1:
                    if bit>>(elem[0]-1) & 1:
                        cnt+=1
                else:
                    if not (bit>>(elem[0]-1) & 1):
                        cnt+=1
            if cnt==A[i]:
                tmp+=1
            else:
                continue
    
    if tmp==bin(bit).count("1"):
        ans=max(bin(bit).count("1"),ans)
print(ans)

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

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

lst = []
combi_lst = [i for i in range(n)]
for i in range(n, -1, -1):
	for balls in itertools.combinations(combi_lst, i):
		lst = [True if j in balls else False for j in range(n)]
		success = True
		for i, ans in enumerate(answers):
			if lst[i] == False:
				continue
			for x, y in ans[1]:
				if y == 1 and lst[x - 1] == False:
					success = False
				if y == 0 and lst[x - 1] == True:
					success = False
		if success:
			print(sum(lst))
			exit()

Solution (Python):

import sys
sys.setrecursionlimit(2000)

N = int(input())
syogen = []
for i in range(N):
    N_a = int(input())
    syogen_a = []
    for _ in range(N_a):
        x, y = input().split()
        syogen_a.append([int(x) - 1, int(y)])
    syogen.append(syogen_a)


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if s in syojikitati:
            d[s] = 1
        else:
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Solution (Python):
import os, sys, re, math

N = int(input())
honest = []
liar = []

for i in range(N):
    a = int(input())
    h = []
    l = []
    for j in range(a):
        (x, y) = [int(n) for n in input().split()]
        if y == 1:
            h.append(x)
        else:
            l.append(x)
    honest.append(h)
    liar.append(l)

for i in range(2 ** N - 1, -1, -1):
    b = ('{:0%db}' % N).format(i)
    truth = True
    for j in range(N):
        if b[j] == '1':
            for h in honest[j]:
                if b[h - 1] != '1':
                    truth = False
                    break
            if not truth:
                break
            for l in liar[j]:
                if b[l - 1] != '0':
                    truth = False
                    break
        if not truth:
            break
    if truth:
        break

if truth:
    print(len(b.replace('0', '')))

Solution (Python):
n = int(input())
d = dict()
for i in range(n):
    a = int(input())
    for j in range(a):
        l = d.get(i, [])
        p, t = list(map(int, input().split(' ')))
        l.append((p-1, t))
        d[i] = l

def get_bit_array(num):
    res = []
    while num > 0:
        res.append(num%2)
        num //= 2
    while len(res) < n:
        res = res + [0]
    return res[::-1]

def valid(tfs):
    for i in range(len(tfs)):
        honest = tfs[i]
        if not honest:  
            continue
        for (person, tf) in d.get(i, []):  
            if tfs[person] != tf:
                return False
    return True

ans = 0
def f(num):
    global ans
    if num >= 2**n:
        return
    tfs = get_bit_array(num)  
    total = sum(tfs)
    if valid(tfs):
        ans = max(ans, total)

for i in range(int(2**n)):
    f(i)

print(ans)

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

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

ans = 0
for i in range(1 << n):
    flag = 0
    s = str(bin(i))
    cnt = s.count("1")
    

    for j in range(n):
        if (i >> j) & 1:
            for x, y in dic[j + 1]:
                if str(bin((i>>(x-1))))[-1] == str(y):
                    continue
                else:
                    flag = 1
                    break
            
            
            
    if flag != 1:
        ans = max(ans, cnt)

print(ans)

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
shogens = []

for i in range(n):
    a = I()
    shogens.append([])
    for j in range(a):
        x,y = LI()
        x -= 1
        shogens[-1].append((x,y))

def is_honest(i,j):
    return (i >> j) % 2 == 1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i,j)
    return ans 

ans = 0
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x,y) in shogens[j]:
            if y == 0 and is_honest(i,x):ok = False
            if y == 1 and not is_honest(i,x):ok = False
    if ok:
        ans = max(ans, honest_cnt(i))
print(ans)

Solution (Python):
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
  num = int(input())
  for j in range(num):
    person, state = map(int, input().split())
    a[i].append([person-1, state])
honest = 0
for i in range(1, 2**n):
  flag = True
  for j in range(n):
    if (i>>j)&1 == 1:
      for x, y in a[j]:
        if (i>>x)&1 != y:
          flag = False
          break
  if flag:
    honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Solution (Python):
from itertools import product 

n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())          
        XY[i].append((x-1,y))
ans = 0
bits = list(product([0,1],repeat=n))
for bit in bits:
    honest_tes = []
    honest_idx = []
    honest_list = [0 for _ in range(n)]
    flag = True
    for who, h in enumerate(bit):
        if h == 1:
            honest_tes.append(XY[who])
            honest_idx.append(who)
            honest_list[who] = 1
    for idx in honest_idx:
        for x, y in XY[idx]:
            if honest_list[x] != y:
                flag = False
                break
    if flag:
        ans = max(ans, len(honest_idx))
print(ans)

Solution (Python):
import itertools

def main():
    N = int(input())
    BIT = list(itertools.product([True,False], repeat=N))
    P = [[(0,0)]]
    for i in range(1,N+1):
        A =  int(input())
        L = []
        for _ in range(A):
            x,y = map(int,input().split())
            L.append((x,y))
        P.append(L)

    ans = 0

    for b in BIT:
        cnt = 0
        flag = True
        HU = [-1]*(N+1)
        for i in range(1,N+1):
            if b[i-1]:
                cnt += 1
                for hu in P[i]:
                    if b[hu[0]-1] != (hu[1]==1):
                        flag = False
                        break
        if flag:
            ans = max(ans,cnt) 


    print(ans)


if __name__ == '__main__':
    main()

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

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


def judge(mask):
    for i in range(N):
        if (mask>>i & 1)==0:
            continue
        for xy in A_list[i]:
            x = xy[0]-1
            y = xy[1]
            if y==0 and (mask>>x & 1):
                return False
            if y==1 and (mask>>x & 1)==0:
                return False
    return True


num_max = 0
for mask in range(1<<N):
    if judge(mask):
        num = 0
        for i in range(N):
            num += mask>>i & 1
        num_max = max(num, num_max)

print(num_max)