C - HonestOrUnkind2

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.

3
1
2 1
1
1 1
1
2 0

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.

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

0

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

2
1
2 0
1
1 0

1