#hbpc1. [hbpc_1]1→1

[hbpc_1]1→1

题目描述

mm表示变化规则的数量,nn表示要生成11的数量。

对于生成规则ai,bia_{i},b_{i}而言,它表示可以将原字符串中的aia_{i}11变为bib_{i}11。例如,ai=2,bi=3a_{i}=2,b_{i}=3,表示原字符串中1111可以变为111111

现在,原字符串中只有1111,要求你使用最少的变化次数将字符串变成nn11

输入输出格式

输入格式

第一行,两个整数m,nm,n

22~m+1m+1行,每行两个整数ai,bia_{i},b_{i}

输出格式

如果能将字符串变成nn11,输出((变化次数+1)+1),否则输出1-1

说明

数据范围

  • 1m30021≤m≤300^{2}
  • 1n100001≤n≤10000
  • 1ai,bi3001≤a_{i},b_{i}≤300
  • iji≠j时保证aiaja_{i}≠a_{j}bibjb_{i}≠b_{j}

样例说明

样例11

规则为:

1>111->11

111>11111111->11111

那么一个11变成1111111111需要经过下面这些步骤:

1->11

11->111

111->1111

变化次数为33,故答案为44

样例22

规则为:

1>1111->111

11111>11111111->111

那么一个11不可能变成111111111111,故答案为1-1