#P3392. [Usaco2005 Feb]Part Acquisition 交易
[Usaco2005 Feb]Part Acquisition 交易
题目描述
奶牛们接到了寻找一种新型挤奶机的任务,为此它们可以访问 颗行星,交易顺序由奶牛自行选择。为了方便,奶牛们已经给可能出现的K(1≤K≤1000)种货物进行了由1到K的标号.由于这些行星都不是十分发达.没有流通的货币,所以在每个市场里都只能用固定的一种货物去换取另一种货物. 奶牛们带着一种上好的饲料从地球出发,希望进行最少的交易,最终得到所需要的机器.饲料的标号为1,所需要的机器的标号为K.如果任务无法完成,输出-1.
输入格式
第1行是两个数字N和K.
第2到N+1行,每行是两个数字Ai和Bi,表示第 颗行星收取 并提供 ,即奶牛可以用 换取 。
输出格式
输出一行整数,表示最少交换次数加一,即计入初始货物后所经手的物品数。若无法获得货物 ,输出 。
6 5
1 3
3 2
2 3
3 1
2 5
5 4
4
提示
奶牛依次持有货物 ,共交换三次、经手四种货物,因此输出 。
题目来源
Silver