Problem: You are given an undirected connected graph as an adjacency list. Perform a breadth-first search (BFS) from a given starting vertex and reconstruct, for every visited vertex, the path from the start.

Input format: The first line contains two numbers, n and m (1 ≤ n, m ≤ 100000) — the number of vertices and edges. The next m lines contain pairs v u denoting an edge. The last line is the starting vertex s.

Output format: In the first line print the traversal order of the vertices, separated by spaces. Then, on a separate line for each visited vertex, print the path from the starting vertex to it.

Solution: We use a queue (deque) from collections, an array used to mark visited vertices, and an array parent to reconstruct paths.

Initial structures:

used = [False] * (n + 1)

parent = [-1] * (n + 1)

The function bfs() pops a vertex from the queue, marks its neighbours, sets their parent and pushes them onto the queue.

Reconstructing the path for vertex v through the parent array: