16. Shortest Path in a Graph
MediumGraphBFS
Given an undirected, unweighted graph, print the length (number of edges) of the shortest path from s to t, or -1 if t is unreachable.
Input format
Line 1: n m (vertices are numbered 1..n) Next m lines: u v Last line: s t
Output format
The shortest distance or -1.
Example 1
Input
5 5 1 2 2 3 3 4 4 5 1 5 1 4
Output
2
Example 2
Input
4 2 1 2 3 4 1 4
Output
-1
Constraints
1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2 × 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…