Graph Path Reconstruction
Given an unweighted, undirected graph with N nodes and M edges, and a designated starting node S and a target node T, find the lexicographically smallest path from S to T. A path is a sequence of nodes starting with S and ending with T, where each adjacent pair of nodes in the sequence is connected by an edge. The lexicographically smallest path is the one that comes first in dictionary order when comparing paths as sequences of node labels. If no path exists from S to T, output 'IMPOSSIBLE'.
Input
The first line contains three integers N, M, S, T (1 <= N <= 200000, 0 <= M <= 200000, 1 <= S, T <= N). Nodes are 1-indexed. The next M lines each contain two integers u, v (1 <= u, v <= N) representing an undirected edge between node u and node v. S and T might be the same.
Output
Print the nodes of the lexicographically smallest path from S to T, separated by spaces. If no path exists, print 'IMPOSSIBLE'.
Constraints
1 <= N <= 200000 0 <= M <= 200000 1 <= S, T <= N 1 <= u, v <= N
Example 1
5 5 1 5 1 2 1 3 2 4 3 4 4 5
1 2 4 5
Paths: 1-2-4-5 (len 3), 1-3-4-5 (len 3). 1-2-4-5 is lexicographically smaller.
Example 2
4 3 1 3 1 2 1 4 2 3
1 2 3
Paths: 1-2-3 (len 2), 1-4 (no path to 3). Shortest and lexicographically smallest is 1-2-3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 5 1 5 1 2 1 3 2 4 3 4 4 5
4 3 1 3 1 2 1 4 2 3