Задача: Дан неориентированный связный граф в виде списка смежности. Нужно выполнить обход в ширину (BFS), начиная с заданной стартовой вершины, и восстановить для каждой посещённой вершины путь от старта.

Формат входных данных: В первой строке два числа n и m (1 ≤ n, m ≤ 100000) — число вершин и рёбер. В следующих m строках — пары v u, обозначающие ребро. Последняя строка — стартовая вершина s.

Формат выходных данных: В первой строке выведите порядок обхода вершин через пробел. Затем для каждой посещённой вершины в отдельной строке выведите путь от стартовой вершины до неё.

Решение: Используем очередь (deque) из collections, массив used для отметки посещённых, и массив parent для восстановления пути.

Начальные структуры:

used = [False] * (n + 1)

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

Функция bfs() извлекает вершину из очереди, помечает соседей, ставит для них parent и добавляет в очередь.

Восстановление пути для вершины v через массив parent: