UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3392. [Usaco2005 Feb]Part Acquisition 交易

统计 下载数据

Description

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

Input

    第1行是两个数字N和K.
    第2到N+1行,每行是两个数字Ai和Bi,表示第i颗行星愿意提供Ai为得到Bi.

Output

    第1行输出最小交换次数

Sample Input

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

Sample Output

4

奶牛们至少要交换4次,先用1去交换3,再用3去交换2,最后用2交换得到5.

Hint

Source

Silver