题目描述

给定一个处于 Chomsky 简化形式（Chomsky reduced form）的上下文无关文法，以及一个有向图。图中每条边都标有该文法的一个终结符。

请找出从顶点 $s$ 到顶点 $t$ 的最短路径长度，使得沿这条路径依次经过的边标签连接起来后，得到的字符串属于该文法所描述的语言。

如果不存在这样的路径，请输出 NO。

输入格式

第一行包含一个整数 $p$，表示文法产生式的数量：

接下来 $p$ 行，每行给出一条产生式，格式为以下两种之一：

A -> BC

或

A -> a

其中：

• 小写英文字母表示终结符；
• 大写英文字母表示非终结符；
• 大写字母 S 是开始非终结符。

保证 S 至少作为一条产生式的左部出现一次。

接下来一行包含四个整数 $n,m,s,t$：

分别表示图的顶点数、边数、起点编号和终点编号。

接下来 $m$ 行，每行格式为：

u v x

表示存在一条从顶点 $u$ 指向顶点 $v$、标签为小写字母 $x$ 的有向边，其中

图中没有重边，但允许自环，也可能同时存在 $u\to v$ 和 $v\to u$ 两条方向相反的边。

输出格式

如果不存在从 $s$ 到 $t$ 的路径，使得路径上的标签串属于该文法的语言，输出：

NO

否则输出满足条件的最短路径长度。

说明

非正式地说，上下文无关文法由以下内容构成：

• 一组终结符（本题中为小写英文字母）；
• 一组非终结符（本题中为大写英文字母）；
• 若干产生式，用于将一个非终结符替换为一串非终结符或终结符。

Chomsky 简化形式要求每条产生式的右部只能是：

• 一个终结符；或
• 恰好两个非终结符。

事实上，任何不生成空串的上下文无关文法都可以转化为这种形式。

如果从单独的开始非终结符 S 出发，通过若干次使用产生式能够得到某个终结符字符串，那么该字符串就属于这个文法的语言。

后两个样例中的文法描述了所有非空合法括号序列，其中字符 c 表示左括号，字符 j 表示右括号。

样例 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

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

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

NO