这里的语言是一组终结符号序列。
一组产生式规则被定义为形成形式语法。
然后,可以将语言定义为一组终结符号序列,可以通过应用产生式规则从起始符号创建这些序列。
作为应用产生式规则的示例,通过应用产生式规则 A → ab 一次, AAB 可以变成 AabB。
众所周知的包括正则语法和上下文无关语法。
这个问题涉及不受限制的语法。
入力
m n a_1 b_1 a_2 b_2 : a_m b_mm 表示作为输入给出的产生式规则的数量。 我想做 n 代表 1 的数量。
a_i, b_i 是一条产生式规则 a_i 的 代表 1 → b_i 的 代表 1 。 例如, 代表a_i = 2, b_i = 3 为 11→111 。 这使得正式语言 表示为 G = (V, Σ, P, S) 。 非终结符 V = \{S\}、 終端記号 Σ = \{1\},起始符号为 S 。 生产规则 P 为 S→1 是作为输入给出的产生式规则。
制約
- 1 ≦ m ≦ 300^2
- 1 ≦ n ≦ 10000
- 1 ≦ a_i ≦ 300
- 1 ≦ b_i ≦ 300
- i ≠ j 然后, 求创建 a_i ≠ a_j 或 b_i ≠ b_j
出力
-1 。
输入 1
2 5 1 2 3 5
输出 1
4
- 产生式规则是 在\{S → 1,\ 1 → 11,\ 111 → 11111\} 。
- S → 1 → 11 → 111 → 11111 在 4 次。
输入 2
2 6 1 3 5 3
输出 2
-1
- 产生式规则是 在\{S → 1,\ 1 → 111,\ 11111 → 111\} 。