G. Грамматический путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана контекстно-свободная формальная грамматика в сокращенной форме Хомского (см. раздел Примечания для объяснения этих терминов) и ориентированный граф, где каждое ребро помечено терминалом грамматики.

Найдите длину кратчайшего пути в графе от вершины $$$s$$$ до вершины $$$t$$$, такого что конкатенация меток на этом пути принадлежит языку грамматики, или укажите, что такого пути нет.

Входные данные

Первая строка содержит количество продукций в грамматике $$$p$$$ ($$$1 \le p \le 100$$$).

Каждая из следующих $$$p$$$ строк содержит продукцию в форме либо 'A -> BC', либо 'A -> a'. Строчные английские буквы являются терминалами, заглавные английские буквы являются нетерминалами, и заглавная буква 'S' является начальным нетерминалом. Гарантируется, что S появляется в левой части как минимум одной продукции.

Следующая строка содержит четыре целых числа $$$n$$$, $$$m$$$, $$$s$$$ и $$$t$$$ ($$$1 \le s, t \le n \le 26$$$; $$$0 \le m \le n^2$$$), обозначающих количество вершин в графе, количество ребер в графе и индексы начальной и конечной вершин.

Каждая из следующих $$$m$$$ строк содержит описание ребра в форме 'u v x', обозначающеe ребро из вершины $$$u$$$ в вершину $$$v$$$ с меткой $$$x$$$ ($$$1 \le u, v \le n$$$; $$$x$$$ - строчная английская буква). В графе нет кратных ребер, но могут быть петли и разные ребра из $$$u$$$ в $$$v$$$ и из $$$v$$$ в $$$u$$$.

Выходные данные

Если нет пути от $$$s$$$ до $$$t$$$ с метками, образующими строку из языка, выведите 'NO'. В противном случае выведите длину кратчайшего такого пути.

Примечание

Неформально говоря, контекстно-свободная формальная грамматика - это набор терминалов (строчные английские буквы в этой задаче), набор нетерминалов (заглавные английские буквы в этой задаче) и набор правил, определяющих, как нетерминал может быть заменен строкой из нетерминалов или терминалов.

Сокращенная форма Хомского - это форма, в которой каждое правило является заменой либо одного терминала, либо ровно двух нетерминалов. Фактически, любая контекстно-свободная грамматика, не генерирующая пустую строку, может быть преобразована в сокращенную форму Хомского.

Строка терминалов принадлежит языку грамматики, если можно использовать правила для преобразования строки из единственного начального нетерминала в данную строку. Некоторые формальные детали можно найти на https://en.wikipedia.org/wiki/Context-free_grammar.

Формальная грамматика в двух последних примерах определяет все непустые правильные последовательности скобок, где открывающие скобки обозначены 'c', а закрывающие скобки обозначены 'j'.

Примеры
Входные данные
5
S -> AB
A -> a
A -> AA
B -> BB
B -> b
8 8 1 4
1 2 a
2 3 b
3 4 a
1 5 a
5 6 a
6 7 a
7 8 b
8 4 b
Выходные данные
5
Входные данные
6
S -> SS
S -> LA
S -> LR
A -> SR
L -> c
R -> j
4 5 1 1
1 2 c
2 3 c
3 1 j
1 4 j
4 3 j
Выходные данные
12
Входные данные
6
S -> SS
S -> LA
S -> LR
A -> SR
L -> c
R -> j
4 5 1 4
1 2 c
2 1 c
2 3 c
3 4 j
4 3 j
Выходные данные
NO