题目描述
m表示变化规则的数量,n表示要生成1的数量。
对于生成规则ai,bi而言,它表示可以将原字符串中的ai个1变为bi个1。例如,ai=2,bi=3,表示原字符串中11可以变为111
现在,原字符串中只有1个1,要求你使用最少的变化次数将字符串变成n个1。
输入输出格式
输入格式
第一行,两个整数m,n;
第2~m+1行,每行两个整数ai,bi;
输出格式
如果能将字符串变成n个1,输出(变化次数+1),否则输出−1。
说明
数据范围
- 1≤m≤3002
- 1≤n≤10000
- 1≤ai,bi≤300
- 当i=j时保证ai=aj且bi=bj
样例说明
样例1
规则为:
1−>11
111−>11111
那么一个1变成11111需要经过下面这些步骤:
1->11
11->111
111->1111
变化次数为3,故答案为4。
样例2
规则为:
1−>111
11111−>111
那么一个1不可能变成111111,故答案为−1。