Minimizing Distinct Goods in Planetary Trades

Cows have been given a mission to find a new milking machine. To achieve this, they will visit \(N\) planets sequentially. On each planet there is a fixed trading market where a specific type of good is exchanged for another. There are \(K\) types of goods labeled from \(1\) to \(K\). The cows start their journey from Earth with high‐quality feed labeled as \(1\) and they need to obtain the milking machine labeled as \(K\). They wish to complete the task while using as few distinct types of goods as possible. In other words, if the cows use a sequence of trades and the set of goods involved is \(S\), they want to minimize \(|S|\). If the task is impossible, output \(-1\>.

The trading happens over \(N\) planets in order. On the \(i\)th planet, the market offers a trade: if the cows currently have good \(u\), they can exchange it for good \(v\). They may skip planets if needed. Note that when a new good is acquired (one that has not been used before in that trade sequence), the count of distinct goods increases by one. Thus, if a valid sequence uses \(t\) trades (always exchanging one good for a different one), the total number of distinct goods used is \(t+1\>.

inputFormat

The first line contains two integers \(N\) and \(K\) (with \(1 \le N \le 5 \times 10^4\) and \(1 \le K \le 10^3\)), where \(K\) is the number of goods.

Each of the following \(N\) lines contains two integers \(u\) and \(v\), indicating that on that planet, if the cows have good \(u\), they can trade it for good \(v\>.

outputFormat

Output a single integer: the minimum number of distinct goods required (including the starting good \(1\) and the target good \(K\)). If it is impossible to obtain the target, output \(-1\>.

sample

3 3
1 2
2 3
1 3

2