Problem: You are given an undirected connected graph represented by an adjacency list. Perform a depth-first search (DFS) starting from a given vertex.

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

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

Solution: The problem is solved with the DFS algorithm. A list used marks visited vertices, and an array parent is kept to reconstruct the path from the current vertex back to the start.

Initial condition:

used = [False] * n

parent = [-1] * n

The recursive function dfs visits a vertex, marks it as visited, appends it to the traversal list, and then, for every unvisited neighbour, updates the parent array and calls itself recursively.

Once the traversal is complete, the path from the starting vertex to any other vertex can be reconstructed by walking the parent array: