There are $$$N$$$ towns connected by $$$M$$$ roads. Travelling any road takes half a day. Hence, for two towns $$$X$$$ and $$$Y$$$ connected directly by a road, if you start from $$$X$$$ during the day, you will reach $$$Y$$$ at night, and vice versa.
Pirates start from town $$$1$$$ during the night and wish to reach town $$$N$$$ during the night. They cannot halt at any town during the journey, but they may visit the same town multiple times.
Your task is to find the minimum number of roads they need to travel to reach town $$$N$$$ during the night. If it is not possible to make such a journey, print -1.
The first line contains two integers $$$N$$$ and $$$M$$$ $$$(2 \le N \le 10^5, 1 \le M \le 2 \times 10^5)$$$ — the number of towns and the number of roads.
Each of the following $$$M$$$ lines contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le N, a \ne b)$$$, indicating that there is a bidirectional road between town $$$a$$$ and town $$$b$$$.
Print a single integer — the minimum number of roads the pirates must travel to reach town $$$N$$$ during the night.
If such a journey is not possible, print -1.
Input:
4 4 1 2 2 3 3 4 1 4
Output:
-1
Input:
3 2 1 2 2 3
Output:
2
In the first example:
There is no path from town $$$1$$$ to town $$$4$$$ that takes an even number of roads; hence it's impossible to reach town $$$4$$$ during the night.
In the second example:
Path $$$1 \rightarrow 2 \rightarrow 3$$$ takes $$$2$$$ roads. Since the pirates start at night, after $$$2$$$ roads they will arrive at night, which is valid.