P1673 [USACO05FEB] Part Acquisition S

# Description The cows have been tasked with finding a new milking machine. To do so, they plan to pass through $N(1\le N\le 5\times 10^4)$ planets in sequence and trade on them. For convenience, the $K(1\le K\le 10^3)$ possible kinds of goods have been labeled from $1$ to $K$. Since these planets are not very developed and there is no circulating currency, in each market you can only exchange one fixed item for another fixed item. The cows depart Earth carrying a premium feed and hope to obtain the required machine while minimizing the number of distinct item types used. The feed is labeled $1$, and the required machine is labeled $K$. If the task cannot be completed, output $-1$.

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

第 $1$ 行是两个数字 $N$ 和 $K$。 第 $2$ 到 $N+1$ 行，每行是两个数字 $A_i$ 和 $B_i$，表示第 $i$ 颗行星为得到 $A_i$ 愿意提供 $B_i$。

Output the minimum number of distinct item types.

The cows need at least $4$ different labels: first exchange $1$ for $3$, then $3$ for $2$, and finally $2$ for $5$. $1\le N\le 5\times 10^4$, $1\le K\le 10^3$. Translated by ChatGPT 5