BFS: Shortest Unweighted Distance

BFS: shortest number of edges between two vertices

Read an undirected graph and two vertices s, t, and print the shortest path length from s to t (fewest edges). Print -1 if unreachable; 0 if s == t.

This is BFS's signature use: in an unweighted graph, BFS reaches a vertex for the first time via a shortest path. Complete shortestDist.

Pitfalls: (1) use a dist[] array (init -1) doubling as visited: dist[w] < 0 means unvisited. (2) On first assignment, dist[w] = dist[v] + 1, and never change it afterwards (first arrival is shortest). (3) Use a queue (FIFO); a stack turns it into DFS and breaks the shortest-path guarantee.

Input

• Line 1: V E.
• Next E lines: u v, an undirected edge.
• Last line: s t (start, target).

Output

• One line: shortest edge count from s to t; -1 if unreachable.

Example: input 4 3 / 0 1 / 1 2 / 2 3 / 0 3 -> 3 (0→1→2→3).