20238번 - Grammar Path 다국어

You are given a context-free formal grammar in Chomsky reduced form (see Notes section for an explanation of these terms), and a directed graph with each edge labeled with a terminal of the grammar.

Find the length of the shortest path in the graph from vertex $s$ to vertex $t$ such that concatenation of the labels on this path is in the language of the grammar, or state that there is no such path.

The first line contains the number of productions in the grammar $p$ ($1 \le p \le 100$).

Each of the next $p$ lines contains a production in the form of either 'A -> BC' or 'A -> a'. The lowercase English letters are terminals, the uppercase English letters are nonterminals, and the uppercase letter 'S' is the starting nonterminal. It's guaranteed that S appears as left hand side of at least one production. 

The next line contains four integers $n$, $m$, $s$, and $t$ ($1 \le s, t \le n \le 26$; $0 \le m \le n^2$), denoting the number of vertices in the graph, the number of edges in the graph, and indices of the start and the finish.

Each of the next $m$ lines contains a description of an edge in the form 'u v x', denoting an edge from vertex $u$ to vertex $v$ labeled with $x$ ($1 \le u, v \le n$; $x$ is a lowercase English letter). There are no multiedges in the graph, but there might be loops and different edges from $u$ to $v$ and from $v$ to $u$.

If there is no path from $s$ to $t$ with labels forming a string from the language, output 'NO'. Otherwise, output the length of the shortest such path.

Informally speaking, a context-free formal grammar is a set of terminals (lowercase English letters in this problem), a set of nonterminals (uppercase English letters in this problem), and a set of rules of how a nonterminal can be replaced with a string of nonterminals or terminals.

Chomsky reduced form is a form where each rule is a replacement with either a single terminal or exactly two nonterminals. In fact, any context-free grammar which does not generate the empty string can be converted to Chomsky reduced form.

A string of terminals is in the language of the grammar if one can use the rules to convert a string of a single starting nonterminal into the given string. You can get some formal details at https://en.wikipedia.org/wiki/Context-free_grammar. 

The formal grammar in the two last examples defines all non-empty correct bracket sequences, with opening brackets denoted with 'c' and closing brackets denoted with 'j'.