给你一个乔姆斯基简化范式（Chomsky reduced form）的上下文无关文法（参见“说明”部分对这些术语的解释），以及一个有向图，图中的每条边都标记有该文法的一个终结符。

请找出图中从顶点 $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，表示一条从顶点 $u$ 到顶点 $v$ 且标记为 $x$ 的有向边（$1 \le u, v \le n$；$x$ 是一个小写英文字母）。图中没有重边，但可能存在自环，也可能同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的不同有向边。

输出格式

如果不存在一条从 $s$ 到 $t$ 的路径，其边上的标记拼接成的字符串属于该文法的语言，则输出 NO。否则，输出满足条件的最短路径的长度。

样例

输入样例 1

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

输出样例 1

5

输入样例 2

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

输出样例 2

12

输入样例 3

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

输出样例 3

NO

说明

通俗地说，上下文无关文法是一组终结符（在本题中为小写英文字母）、一组非终结符（在本题中为大写英文字母）以及一组关于如何将非终结符替换为非终结符或终结符组成的字符串的规则。

乔姆斯基简化范式是指每条规则要么替换为一个单一的终结符，要么恰好替换为两个非终结符。事实上，任何不产生空串的上下文无关文法都可以转换为乔姆斯基简化范式。

如果可以通过规则将单个起始非终结符转换为给定的终结符字符串，则称该终结符字符串属于该文法的语言。您可以在 https://en.wikipedia.org/wiki/Context-free_grammar 获取一些正式的详细信息。

最后两个样例中的文法定义了所有非空合法括号序列，其中开括号用 'c' 表示，闭括号用 'j' 表示。