形式文法是一种描述形式语言的方式，定义为 $\Gamma = (\Sigma, N, S \in N, P \subset N^+ \times (\Sigma \cup N)^*)$，其中 $\Sigma$ 称为字母表，其元素称为终结符，$N$ 是非终结符集合，$S$ 是起始非终结符，$P$ 是一组形如 $\alpha \to \beta$ 的产生式规则。

在此，$N^+$ 包含所有由 $N$ 中一个或多个元素组成的字符串（非空非终结符串），$(\Sigma \cup N)^*$ 由所有由零个、一个或多个 $(\Sigma \cup N)$ 元素组成的字符串（包括终结符和非终结符的字符串，包含空串）组成。

如果产生式规则的左侧恰好由一个非终结符组成，则称该文法为上下文无关文法，更正式地，$P \subset N \times (\Sigma \cup N)^*$。

例如，考虑第二个样例测试用例中的文法，其字母表 $\Sigma = \{\text{a}, \text{b}\}$，非终结符集合 $N = \{S, A\}$，以及两条产生式规则：

1. $S \to \text{b}A$
2. $A \to \text{aa}$

可以很容易看出这是一个上下文无关文法。

要创建由文法生成的语言，需要从仅包含起始非终结符 $S$ 的字符串开始，然后应用一次或多次产生式规则。应用产生式规则的过程是在当前字符串中找到该规则的左侧，并将其替换为该规则右侧的字符串。由 $\Gamma$ 生成的语言是所有仅由终结符组成的、可以通过应用一次或多次产生式规则生成的字符串集合。

例如，上述文法生成的语言中包含字符串 $\text{baa}$。为了生成它，可以应用产生式 $S \to \text{b}A \to \text{baa}$。该文法生成的语言中没有其他字符串。

有些文法甚至可能生成无限语言，而另一些可能生成空语言。

给定一个上下文无关文法，其字母表由两个终结符 “a” 和 “b” 组成。你的任务是检查该文法生成的语言中是否包含长度为奇数的字符串。

本题中的非终结符编号从 $1$ 到 $n$。起始非终结符的编号始终为 $1$。

输入格式

输入包含一个或多个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$：非终结符的数量和产生式规则的数量 ($1 \le n \le 50000, 1 \le m \le 200\,000$)。

接下来的 $m$ 行，每行描述一条产生式规则。首先给出 $A_i$ 和 $k_i$：左侧非终结符的编号 ($1 \le A_i \le n$) 以及产生式规则右侧字符的数量 ($0 \le k_i \le 5000$)。随后是 $k_i$ 个对象，每个对象要么是一个非终结符 $B_{i,j}$ ($1 \le B_{i,j} \le n$)，要么是一个终结符 “a” 或 “b”。连续的字符由空格分隔。

所有测试用例中 $n$ 的总和不超过 $50\,000$。所有测试用例中 $m$ 的总和不超过 $200\,000$。输入文件大小不超过 $5$ 兆字节。

输入以一行两个零结束。

输出格式

对于每个测试用例，输出一行。如果给定文法生成的语言包含长度为奇数的字符串，则输出 “YES”，否则输出 “NO”。

样例

输入 1

2 2
1 2 a 2
2 1 b
2 2
1 2 b 2
2 2 a a
2 2
1 2 b 2
2 3 a a 1
0 0

输出 1

NO
YES
NO