1→1
题意翻译
## 题目描述
$m$表示变化规则的数量,$n$表示要生成$1$的数量。
对于生成规则$a_{i},b_{i}$而言,它表示可以将原字符串中的$a_{i}$个$1$变为$b_{i}$个$1$。例如,$a_{i}=2,b_{i}=3$,表示原字符串中$11$可以变为$111$
现在,原字符串中只有$1$个$1$,要求你使用最少的变化次数将字符串变成$n$个$1$。
## 输入输出格式
### 输入格式
第一行,两个整数$m,n$;
第$2$~$m+1$行,每行两个整数$a_{i},b_{i}$;
### 输出格式
如果能将字符串变成$n$个$1$,输出$($变化次数$+1)$,否则输出$-1$。
## 说明
### 数据范围
- $1≤m≤300^{2}$
- $1≤n≤10000$
- $1≤a_{i},b_{i}≤300$
- 当$i≠j$时保证$a_{i}≠a_{j}$且$b_{i}≠b_{j}$
## 样例说明
### 样例$1$
规则为:
$1->11$
$111->11111$
那么一个$1$变成$11111$需要经过下面这些步骤:
1->11
11->111
111->1111
变化次数为$3$,故答案为$4$。
### 样例$2$
规则为:
$1->111$
$11111->111$
那么一个$1$不可能变成$111111$,故答案为$-1$。
题目描述
[problemUrl]: https://atcoder.jp/contests/hbpc2012/tasks/hbpc_1
言語を記述するものとして形式文法があります。
ここでいう言語とは終端記号の列の集合です。
形式文法を構成するものとして生成規則の集合が定義されます。
そして、開始記号から生成規則を適用して作ることのできる終端記号の列の集合、として言語を定義することができます。
生成規則の適用の例としては、生成規則 A → ab を1回適用することで 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` を出力せよ。 ```
<pre class="prettyprint linenums">
2 5
1 2
3 5
```
```
<pre class="prettyprint linenums">
4
```
- 生成規則は、$ \{S\ →\ 1,\ 1\ →\ 11,\ 111\ →\ 11111\} $ である。
- $ S\ →\ 1\ →\ 11\ →\ 111\ →\ 11111 $ で $ 4 $ 回となる。
```
<pre class="prettyprint linenums">
2 6
1 3
5 3
```
```
<pre class="prettyprint linenums">
-1
```
- 生成規則は、$ \{S\ →\ 1,\ 1\ →\ 111,\ 11111\ →\ 111\} $ である。