Grammar

A formal grammar is a way of describing formal languages. It is written as $\Gamma = \langle \Sigma, N, S \in N, P \subset N^{+} \times (\Sigma \cup N)^{\*}\rangle$, where $\Sigma$ is an alphabet whose elements are called terminals. $N$ is the set of nonterminals, $S$ is the starting nonterminal, and $P$ is the set of production rules, each of the form $\alpha \rightarrow \beta$.

Here, $N^{+}$ is the set of all strings of one or more elements of $N$ (non-empty strings of nonterminals). $(\Sigma\cup N)^{\*}$ is the set of all strings of zero or more elements of $\Sigma\cup N$, including the empty string.

A grammar is context-free if the left side of each rule is exactly one nonterminal. In other words, $P \subset N \times (\Sigma\cup N)^{\*}$.

For example, take the alphabet $\Sigma = \{`a`, `b`\}$, the nonterminals $N = \{S, A\}$, and these two rules:

1. $S \rightarrow `b`A$
2. $A \rightarrow `aa`$

This grammar is context-free.

To generate a language, start from the string consisting of only $S$, then apply production rules one or more times. Applying a rule means finding its left side in the current string and replacing it with its right side. The language generated by the grammar is the set of all strings made only of terminals that can be produced this way.

In the example above, $baa$ belongs to the language, since $S \rightarrow `b`A \rightarrow `baa`$. No other strings are generated.

Some grammars generate infinite languages, and others generate empty languages.

You are given a context-free grammar over the terminals a and b. Determine whether the language it generates contains a string with strictly more a characters than b characters.

The nonterminals are numbered from 1 to $n$. The starting nonterminal is always 1.

The input contains one or more test cases.

The first line of each test case contains two integers $n$ and $m$, the number of nonterminals and the number of production rules ($1 \le n \le 100$, $1 \le m \le 50\,000$).

Each of the next $m$ lines describes one rule. It starts with $A_i$ and $k_i$, where $A_i$ ($1 \le A_i \le n$) is the left side nonterminal and $k_i$ ($0 \le k_i \le 100$) is the length of the right side. Then $k_i$ symbols follow. Each symbol is either a nonterminal $B_{i,j}$ ($1 \le B_{i,j} \le n$) or a terminal a or b. Symbols are separated by single spaces.

The sum of $n$ over all test cases does not exceed 1000. The sum of $m$ over all test cases does not exceed 50 000. The input size does not exceed 5 megabytes.

The input ends with a line containing two zeroes.

For each test case, print one line. Print YES if the language contains a string with strictly more a characters than b characters. Otherwise, print NO.