Shortest Path in a Graph

Statement

The first line contains the number of vertices n and the number of edges m. Each of the next m lines contains vertices u and v joined by an edge (the graph is undirected). Print the number of edges on the shortest path from vertex 1 to vertex n. If there is no path, print -1. For n = 1 the answer is 0.

Examples

4 4
1 2
2 4
1 3
3 4

2

3 1
2 3

-1

Constraints

• 1 ≤ n ≤ 10^5
• 0 ≤ m ≤ 2·10^5
• 1 ≤ u, v ≤ n