364. Fewest Edges Between Two Vertices
Print the smallest number of edges on a path from vertex s to vertex t.
Print -1 if there is no path at all.
Every edge counts the same here, and that is exactly when breadth-first search
answers the question directly: it visits vertices in order of distance, so the
first time it reaches t it has arrived by a shortest route.
Depth-first search does NOT answer this. It commits to one route and may reach
t the long way round, and it has no way to know that a shorter path existed.
Record each vertex's distance as you enqueue it, one more than the vertex it came
from. The distance from s to itself is 0.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ s, t ≤ n` - There are no self-loops and no repeated edges.
Input
The first line contains four integers n, m, s and t.
Each of the next m lines contains an undirected edge u v.
Vertices are numbered 1 to n.
Output
Print the number of edges on a shortest path from s to t, or -1 if none exists.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.