题目描述

有 $N$ 个人，编号从$1$到 $N$。

他们中的每个人都可能是一个诚实的人，他们的证词总是正确的，也可能是一个不友善的人，他们的证词可能是正确的，也可能不正确。

第$i$个人提供 $A_i$ 个证词。

第$i$个人的第$j$个证词由两个整数 $x_{ij}$和 $y_{ij}$表示。

如果 $y_{ij}= 1$，那么证词表示第 $x_{ij}$个人是诚实的;

如果 $y_{ij} = 0$，那么证词表示第 $x_{ij}$个人是不友善的。

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

输入

第一行一个整数$N$ 接下来第$A_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\ <\ =\ N\ <\ =\ 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$

Sample Explanation 1

人 $1$ と人 $2$ が正直者であり、人 $3$ が不親切な人であると仮定すると、正直者は $2$ 人であり、矛盾が生じません。これが存在し得る正直者の最大人数です。

Sample Explanation 2

$1$ 人でも正直者が存在すると仮定すると、直ちに矛盾します。