#P3392. [Usaco2005 Feb]Part Acquisition 交易

[Usaco2005 Feb]Part Acquisition 交易

题目描述

    奶牛们接到了寻找一种新型挤奶机的任务,为此它们可以访问 N(1≤N≤50000)N(1\le N\le 50000) 颗行星,交易顺序由奶牛自行选择。为了方便,奶牛们已经给可能出现的K(1≤K≤1000)种货物进行了由1到K的标号.由于这些行星都不是十分发达.没有流通的货币,所以在每个市场里都只能用固定的一种货物去换取另一种货物.    奶牛们带着一种上好的饲料从地球出发,希望进行最少的交易,最终得到所需要的机器.饲料的标号为1,所需要的机器的标号为K.如果任务无法完成,输出-1.

输入格式

第1行是两个数字N和K.

第2到N+1行,每行是两个数字Ai和Bi,表示第 ii 颗行星收取 AiA_i 并提供 BiB_i,即奶牛可以用 AiA_i 换取 BiB_i。

输出格式

输出一行整数,表示最少交换次数加一,即计入初始货物后所经手的物品数。若无法获得货物 KK,输出 −1-1。

6 5
1 3
3 2
2 3
3 1
2 5
5 4
4

提示

奶牛依次持有货物 1,3,2,51,3,2,5,共交换三次、经手四种货物,因此输出 44。

题目来源

Silver