← 返回题目列表

AtCoder · abc147_c

C. 诚实或不友善2

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 人数 1 to N。他们每个人要么是一个 诚实 证词始终正确的人或 不友善 其证词可能正确或错误的人。

人 i 给出 A_i 证词。的 j- 个人证词 i 由两个整数表示 x_{ij} 和 y_{ij}。如果 y_{ij} = 1,证词称 Person 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 人。


示例输入 1

3
1
2 1
1
1 1
1
2 0

示例输出 1

2

如果人 1 和人 2 诚实、做人 3 不厚道,我们有两个诚实人,没有矛盾,这是最大可能的诚实人数量。


示例输入 2

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

示例输出 2

0

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


示例输入 3

2
1
2 0
1
1 0

示例输出 3

1