Problem statement
You are given an undirected, unweighted graph and two vertices S and T. Find a path from S to T that uses the minimum possible number of edges. If no path exists, print IMPOSSIBLE. Self-loops and repeated edges are allowed.
Input format
First line: N M. Next M lines: U V. Last line: S T.
Output format
If no path exists, print IMPOSSIBLE. Otherwise: First line: the number K of vertices in the shortest path. Second line: K integers representing the vertices of the path, from S to T. If multiple shortest paths exist, any of them is accepted.
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ U, V, S, T ≤ N
Sample input
6 6 1 2 1 3 2 4 3 4 4 5 5 6 1 5
Sample output
4 1 2 4 5
Sample explanation
Both 1 → 2 → 4 → 5 and 1 → 3 → 4 → 5 use three edges. The printed count is four vertices. Either path is accepted.
Need a hint?
BFS with parent tracking and path reconstruction. Expected complexity: O(N + M).