C - 诚实还是不友善 2

得分：300分

题目描述

有 $N$ 个人，编号从 $1$ 到 $N$。他们中的每个人都可能是一个诚实的人，他们的证词总是正确的，也可能是一个不友善的人，他们的证词可能是正确的，也可能不正确。

第 $i$ 个人提供 $A_i$ 个证词。第 $i$ 个人的第 $j$ 个证词由两个整数 $x_{ij}$ 和 $y_{ij}$ 表示。如果 $y_{ij} = 1$，那么证词表示第 $x_{ij}$ 个人是诚实的；如果 $y_{ij} = 0$，那么证词表示第 $x_{ij}$ 个人是不友善的。

最多有多少个诚实的人在这 $N$ 个人中？

约束条件

• 所有输入的值都是整数。
• $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$

输入

输入以以下格式给出：

$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}$

输出

输出一个整数，表示这 $N$ 个人中诚实人的最大可能数量。

3
1
2 1
1
1 1
1
2 0

2

如果第 $1$ 个人和第 $2$ 个人是诚实的，而第 $3$ 个人是不友善的，那么最多有两个诚实的人而没有矛盾，这是诚实人的最大可能数量。

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

0

假设其中一个或多个人是诚实的就会立即导致矛盾。

2
1
2 0
1
1 0

1