题目描述

奶牛们接到了寻找一种新型挤奶机的任务，为此它们准备依次经过 $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$ 颗行星为得到 $B_i$ 愿意提供 $A_i$。

输出格式

输出最小交换次数。

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

4

提示

奶牛们至少需要 $4$ 种不同标号的物品，先用 $1$ 去交换 $3$，再用 $3$ 去交换 $2$，最后用 $2$ 交换得到 $5$。

$1\le N\le 5\times 10^4$，$1\le K\le 10^3$。