문법

형식 문법(formal grammar)은 형식 언어를 기술하는 방법이다. 문법은 $\Gamma = \langle \Sigma, N, S \in N, P \subset N^{+} \times (\Sigma \cup N)^{\*}\rangle$ 로 나타내며, 여기서 $\Sigma$는 알파벳이고 그 원소를 터미널이라고 부른다. $N$은 논터미널의 집합, $S$는 시작 논터미널, $P$는 $\alpha \rightarrow \beta$ 꼴의 생성 규칙의 집합이다.

여기서 $N^{+}$는 하나 이상의 $N$ 원소로 이루어진 모든 문자열(비어 있지 않은 논터미널 문자열)이다. $(\Sigma\cup N)^{\*}$는 터미널과 논터미널로 이루어진 길이 0 이상의 모든 문자열(빈 문자열 포함)이다.

각 규칙의 왼쪽이 논터미널 하나뿐이면 그 문법은 문맥 자유 문법(context-free)이다. 즉 $P \subset N \times (\Sigma\cup N)^{\*}$ 이다.

예를 들어 알파벳 $\Sigma = \{`a`, `b`\}$, 논터미널 집합 $N = \{S, A\}$, 그리고 다음 두 규칙이 있다고 하자.

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

이 문법은 문맥 자유 문법이다.

언어를 생성하려면 $S$ 하나로 이루어진 문자열에서 출발해 생성 규칙을 한 번 이상 적용한다. 규칙을 적용한다는 것은 현재 문자열에서 규칙의 왼쪽 부분을 찾아 오른쪽 부분으로 바꾸는 것이다. 문법이 생성하는 언어는 이렇게 만들 수 있는 터미널로만 이루어진 모든 문자열의 집합이다.

위 문법에서 baa는 언어에 속한다. $S \rightarrow `b`A \rightarrow `baa`$ 순서로 규칙을 적용하면 만들 수 있기 때문이다. 이 문법이 생성하는 문자열은 이것이 전부다.

무한한 언어를 생성하는 문법도 있고, 빈 언어를 생성하는 문법도 있다.

터미널 a와 b로 이루어진 문맥 자유 문법이 주어진다. 이 문법이 생성하는 언어에 a의 개수가 b의 개수보다 더 많은 문자열이 있는지 판정하라.

논터미널은 1부터 $n$까지 번호가 매겨져 있다. 시작 논터미널의 번호는 항상 1이다.

입력은 하나 이상의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 논터미널의 개수 $n$과 생성 규칙의 개수 $m$이 주어진다 ($1 \le n \le 100$, $1 \le m \le 50\,000$).

이어지는 $m$줄 각각은 규칙 하나를 나타낸다. 먼저 왼쪽 논터미널 $A_i$ ($1 \le A_i \le n$)와 오른쪽 기호의 개수 $k_i$ ($0 \le k_i \le 100$)가 주어진다. 그다음 $k_i$개의 기호가 주어지며, 각 기호는 논터미널 $B_{i,j}$ ($1 \le B_{i,j} \le n$)이거나 터미널 a 또는 b이다. 기호 사이는 공백 한 칸으로 구분한다.

모든 테스트 케이스의 $n$ 합은 1000을 넘지 않는다. 모든 테스트 케이스의 $m$ 합은 50 000을 넘지 않는다. 입력 크기는 5MB를 넘지 않는다.

입력은 0 0 으로 끝난다.

각 테스트 케이스마다 한 줄에 답을 출력한다. 생성되는 언어에 a의 개수가 b의 개수보다 더 많은 문자열이 있으면 YES, 없으면 NO를 출력한다.