该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

证词筛选

题目描述

调查员收集了 $N$ 个人的证词，这些人的编号依次为 $1$ 到 $N$。每个人要么是诚实者，要么是不诚实者。诚实者的每条证词都正确；不诚实者的证词可以正确，也可以错误。

第 $i$ 个人给出了 $A_i$ 条证词。他的第 $j$ 条证词用两个整数 $x_{ij}$ 和 $y_{ij}$ 表示：当 $y_{ij}=1$ 时，他声称第 $x_{ij}$ 个人是诚实者；当 $y_{ij}=0$ 时，他声称第 $x_{ij}$ 个人是不诚实者。

调查员还掌握了一条可靠信息：第 $S$ 个人一定是不诚实者。

请确定每个人的身份，使所有诚实者的证词都正确，并满足这条可靠信息。在所有可能的身份安排中，最多有多少个诚实者？

输入格式

第一行输入两个整数 $N$ 和 $S$，满足 $1\le N\le15$、$1\le S\le N$。

接下来依次输入第 $1$ 到第 $N$ 个人的证词。对于每个 $i$，先用一行输入整数 $A_i$，满足 $0\le A_i\le N-1$；随后输入 $A_i$ 行，第 $j$ 行包含两个整数 $x_{ij}$ 和 $y_{ij}$。

对于所有 $1\le i\le N$、$1\le j\le A_i$，保证 $1\le x_{ij}\le N$、$x_{ij}\ne i$，且 $y_{ij}$ 为 $0$ 或 $1$。同一个人不会对同一对象重复作证，即对于固定的 $i$ 和任意 $1\le j_1<j_2\le A_i$，均有 $x_{ij_1}\ne x_{ij_2}$。

输入中的所有数均为整数。若 $A_i=0$，该人的证词部分只有一行 $0$。

输出格式

输出一个整数，表示最多可能有多少个诚实者。允许所有人都不诚实，此时诚实者人数为 $0$。

输入输出样例

输入 #1

4 4
1
2 1
2
1 1
4 0
1
2 0
1
1 1

输出 #1

2

样例解释 #1

可以让 $1$、$2$ 号人成为诚实者，$3$、$4$ 号人成为不诚实者。$1$ 号人说 $2$ 号人诚实；$2$ 号人说 $1$ 号人诚实、$4$ 号人不诚实，这些证词都成立。

$4$ 号人虽然不诚实，他所说的“$1$ 号人诚实”仍然可以是真的。$3$ 号人不能与 $2$ 号人同时诚实，因为他声称 $2$ 号人不诚实。因此，除去必须不诚实的 $4$ 号人，剩下三个人也不能全部诚实，答案为 $2$。

输入 #2

3 2
1
2 1
1
3 0
1
1 1

输出 #2

0

样例解释 #2

$2$ 号人必须不诚实。$1$ 号人声称 $2$ 号人诚实，所以 $1$ 号人也不能诚实。接着，$3$ 号人声称 $1$ 号人诚实，因此 $3$ 号人同样不能诚实。三个人都不诚实时满足要求，答案为 $0$。