#P1674. [Usaco2005]Part Acquisition

[Usaco2005]Part Acquisition

[USACO05FEB] Part Acquisition S

题目描述

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

输入格式

第 11 行是两个数字 NN 和 KK。

第 22 到 N+1N+1 行,每行是两个数字 AiA_i 和 BiB_i,表示第 ii 颗行星收取货物 AiA_i 并提供货物 BiB_i,即奶牛持有 AiA_i 时可以换取 BiB_i。

输出格式

输出一行整数,表示最少经手的货物种类数,计入起始货物 11 和最终货物 KK。无法获得货物 KK 时输出 −1-1。

样例 #1

样例输入 #1

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

样例输出 #1

4

提示

奶牛们至少需要 44 种不同标号的物品,先用 11 去交换 33,再用 33 去交换 22,最后用 22 交换得到 55。

1≤N≤5×1041\le N\le 5\times 10^4,1≤K≤1031\le K\le 10^3。