Background

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$.

Output Format

Output the minimum number of distinct item types.

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

4

Hint

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