← 返回题目列表

AtCoder · hbpc_1

A. 一到一

中文机器翻译题面 查看原题

形式语法用于描述语言。
这里的语言是一组终结符号序列。
一组产生式规则被定义为形成形式语法。
然后,可以将语言定义为一组终结符号序列,可以通过应用产生式规则从起始符号创建这些序列。
作为应用产生式规则的示例,通过应用产生式规则 A → ab 一次, AAB 可以变成 AabB。
众所周知的包括正则语法和上下文无关语法。
这个问题涉及不受限制的语法。

入力

输入遵循以下格式。所有给出的数字都是整数。
m n
a_1 b_1
a_2 b_2
:
a_m b_m
m 表示作为输入给出的产生式规则的数量。 我想做 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

出力

開始記号 S 从 n 的 代表 1 需要应用产生式规则的最小次数。 如果不可能的话 -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\} 。