题目描述

有 $n$ 个人，每个人的编号从 $1$ 到 $n$。每个人分为两类：

• 诚实者：一定说真话
• 不诚实者：说的话真假不定。可能真也可能假。

第 $i$ 个人做了 $a_i$ 条证言。第 $i$ 个人的第 $j$ 条证言由两个整数 $x_{i,j}$、$y_{i,j}$ 表示：

• 当 $y_{i,j} = 1$ 时，表示 第 $x_{i,j}$ 个人是诚实者
• 当 $y_{i,j} = 0$ 时，表示 第 $x_{i,j}$ 个人是不诚实的。

求在这 $n$ 个人中，最多可能有多少个诚实者？

输入格式

第一行输入 $n$ 代表人的个数。

接下来若干个行：

• 首先输入一个数字 $a_i$ 代表第 $i$ 个人证言数量。
• 接下来 $a_i$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个人对于第 $x_i$ 个人的一个证言。
  • 当 $y_i=0$，第 $i$ 个人认为第 $x_i$ 个人不诚实。反之是诚实的。

输出格式

输出可能存在的诚实者的最大人数。

3
1
2 1
1
1 1
1
2 0

2

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

提示

数据范围

对于所有的数据满足：

• $1 \leq N \leq 15$
• $0 \leq A_i \leq N - 1$

样例解释 1

• 有 $3$ 个人，编号分别为 $1、2、3$。
• 第 $1$ 个人有 $1$ 条证言，内容是：“第 $2$ 个人是诚实者”。
• 第 $2$ 个人有 $1$ 条证言，内容是：“第 $1$ 个人是诚实者”。
• 第 $3$ 个人有 $1$ 条证言，内容是：“第 $2$ 个人是不诚实者”。

分析

假设第 $1$ 个人和第 $2$ 个人都是诚实者：

• 因为第 $1$ 个人诚实，他说“第 $2$ 个人是诚实者”是真的，所以第 $2$ 个人确实诚实。
• 因为第 $2$ 个人诚实，他说“第 $1$ 个人是诚实者”也是真的，所以第 $1$ 个人确实诚实。
• 第 $3$ 个人的证言不影响，因为第 $3$ 个人不诚实，他说“第 $2$ 个人不诚实”是假的，符合设定。
• 这样第 $1$ 和第 $2$ 个人是诚实者，第 $3$ 个人是不诚实者。

因此 诚实者最大数量是 $2$。

样例解释 2

• 有 $3$ 个人，编号 $1、2、3$。
• 他们的证言相互矛盾，例如：
  • $1$ 号说 $2$ 号诚实，$3$ 号不诚实；
  • $2$ 号说 $3$ 号诚实，$1$ 号不诚实；
  • $3$ 号说 $1$ 号诚实，$2$ 号不诚实。

尝试假设任何一个人是诚实者都会导致矛盾，因为他们的证言互相否定。

结论： 无法找到符合所有证言的诚实者组合，最大诚实者人数为 $0$。