Problem statement
Given an undirected graph with vertices numbered from 1 to N and two vertices S and T, find any path from S to T. A path must not repeat a vertex. It does not have to be the shortest path. Self-loops and repeated edges may appear in the input. If S equals T, the one-vertex path is valid.
Input format
The first line contains N and M. The next M lines contain the endpoints U and V of each edge. The last line contains S and T.
Output format
If no path exists, print IMPOSSIBLE on its own line. Otherwise, print the number K of vertices on the first line and the K vertex numbers in order on the second line. Different valid paths are accepted.
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ U, V, S, T ≤ N
- 1 ≤ K ≤ N; no repeated vertices in the output path
Sample input
5 4 1 2 2 3 3 4 2 5 1 4
Sample output
4 1 2 3 4
Sample explanation
The edges 1–2, 2–3 and 3–4 form a path from 1 to 4. Store each vertex's parent when it is first discovered, then reconstruct the path backwards from T.
Need a hint?
Mark vertices when discovering them, record their parents, and follow the parent chain from T back to S. Reverse that chain before printing.