beecrowd | 1826
# Is The Language Infinite?

**Timelimit: 2**

By Matheus Pimenta, UNB Brazil

Context-free grammar – CFG – is a mathematical structure used to generate strings, which are finite sequences of terminal symbols. The set of all strings that can be generated by CFG *G* is the language of *G*, written *L(G)*. In this problem, given a CFG *G*, you must tell if *L(G)* is an empty set, finite, or infinite.

A CFG is a 4-tuple *(V, Σ, R, S)*, where

*V*is a finite and non-empty set whose elements are called variables.*Σ*is a finite and non-empty set, disjoint of*V*, whose elements are called terminal symbols.*R*is a set of rules. A rule has the form

where*A → U*_{1}U_{2}...U_{k}*A ∈ V*,*k ≥ 0*and*U*for_{i}∈ V ∪ Σ*i = 1,2,...,k*.*S ∈ V*is the start variable.

To generate a string using a CFG, we run the following procedure.

First, write the start variable *S*. Next, choose a rule to substitute *S*, say, *S → U _{1}U_{2}...U_{k}*. After this choice, erase the

For example, let be the CFG below, where *S* is the start variable.

*S → *a*S*a

*S → *b*S*b

*S → *a

*S → *b

*S → *

Using the CFG above, we can generate any palindrome made of a's and b's. For example:

*S → *a*S*a* → *ab*S*ba* → *abba

Observe that the empty string is a valid string. So, if a CFG *G* generates, for example, only the empty string, *L(G)* is finite, but not empty.

In this problem, the variables will be words made only of uppercase letters, that is, characters between A and Z. The terminal symbols will be lowercase letters, that is, characters between a and z. The rules will be in the format described in the next section. The start variable will always be the first variable of the test case.

The input contains many test cases. Each test case describes a context-free grammar.

The first line of a test case contains two integers **v** and **r**, where **v** is the amount of variables of the CFG, **r** is the amount of rules, 1 ≤ **v** ≤ 10^{2} and 0 ≤ **r** ≤ 2·10^{2}.

Each one of the next **v** lines contains a word made of uppercase letters, a variable of the CFG. The variable in the first line is the start variable.

Each one of the next **r** lines describes a rule of the CFG. A word of uppercase letters is given, an integer 0 ≤ **k** ≤ 10^{2} and a sequence of **k** elements, where each element is a variable, or a terminal symbol.

For each test case, print a line with the word "vazia" if the CFG generates no strings of terminals, or the word "finita" if the CFG generates some, but not infinite strings of terminals, or the word "infinita" if the CFG generates infinite strings of terminals.

Input Sample | Output Sample |

1 0 |
vazia |