Shortest Path in Unweighted Graph

Given an undirected unweighted graph with \(N\) nodes and \(M\) edges, your task is to compute the shortest path between two specified nodes using the Breadth-First Search (BFS) algorithm. The graph is provided as an edge list. If a direct or indirect path exists between the starting node \(s\) and the target node \(t\), output the length of this path; otherwise, output \(-1\). This problem requires proper graph traversal and understanding of BFS, where the distance is incremented level-by-level.

Note: Use standard input (stdin) for reading and standard output (stdout) for writing the result.

The mathematical formulation of the shortest path problem in an unweighted graph can be expressed as finding the minimum number of edges \(d(s,t)\) connecting \(s\) and \(t\), i.e., \[ d(s,t)=\min\{k : \text{there exists a sequence } s=v_0,v_1,\ldots,v_k=t \text{ such that } \forall i, (v_i,v_{i+1})\in E\} \]

inputFormat

The first line contains four integers: \(N\), \(M\), \(s\), and \(t\), where \(N\) is the number of nodes (labeled from \(0\) to \(N-1\)), \(M\) is the number of edges, \(s\) is the starting node, and \(t\) is the target node. The following \(M\) lines each contain two space-separated integers \(u\) and \(v\) representing an undirected edge between nodes \(u\) and \(v\>.

outputFormat

Output a single integer representing the length of the shortest path from node \(s\) to node \(t\). If no path exists, output \(-1\).

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

3