Home

Contest: Task: Related: TaskB TaskD

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

Sample Output 1

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

Sample Output 2

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3