Shortest Path in an Undirected Graph

You are given an undirected graph with n nodes and m edges. The nodes are numbered from 1 to n. Your task is to compute the length of the shortest path from node 1 to node n.

If there is no path between node 1 and node n, output -1. The graph is defined by its edges, and each edge connects two nodes.

The problem can be formulated using the following LaTeX expression:

Find the minimum d such that there exists a sequence of nodes \(v_1, v_2, \dots, v_{d+1}\) satisfying \(v_1=1\), \(v_{d+1}=n\) and for each \(1 \leq i \leq d\), there is an edge between \(v_i\) and \(v_{i+1}\). If no such sequence exists, output \(-1\).

inputFormat

The input is given via standard input (stdin) in the following format:

n m
u1 v1
u2 v2
... 
num vm

where:

• n is the number of nodes.
• m is the number of edges.
• Each of the next m lines contains two integers u and v (1-indexed) representing an undirected edge between nodes u and v.

outputFormat

Output a single integer to standard output (stdout): the length of the shortest path from node 1 to node n. If there is no such path, output -1.

## sample

4 4
1 2
2 3
3 4
1 4

1