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 determine whether there exists a path from node 1 to node \(n\). If such a path exists, output the length of the shortest path; otherwise, output \(-1\).

The graph is described by \(m\) edges. Each edge connects two nodes. You may assume that the graph does not contain any self-loops or duplicate edges.

Note: The length of a path is defined as the number of edges in that path.

inputFormat

The input is given from standard input and has the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Where:

• \(n\) is the number of nodes.
• \(m\) is the number of edges.
• Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) (\(1 \le u_i, v_i \le n\)) representing an undirected edge between nodes \(u_i\) and \(v_i\).

outputFormat

Output a single integer to the standard output: the length of the shortest path from node 1 to node \(n\) if such a path exists, or \(-1\) if no valid path exists.

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

1