101472: [AtCoder]ABC147 C - HonestOrUnkind2

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