Lesson27

#include <iostream>
#include <queue>
#include <vector>

#define all(x) x.begin(), x.end()
using namespace std;

void BFS(int s, vector<vector<int>>& g, vector<int>& r, vector<int>& pi) {
  int n = r.size();
  queue<int> q;
  q.push(s);
  r[s] = 0;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) {
      if (r[v] == INT_MAX) {
        r[v] = r[u] + 1;
        pi[v] = u;
        q.push(v);
      }
    }
  }
}

int main() {
  int n, m; cin >> n >> m;
  vector<vector<int>> g(n);
//  for (int i = 0; i < m; ++i)
  while (m--) {
    int u, v; cin >> u >> v;  --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int s; cin >> s; --s;
  vector<int> r(n, INT_MAX), pi(n, -1);
  BFS(s, g, r, pi);

  for (int u = 0; u < n; ++u) {
    cout << "Vertex " << u + 1 << ": dist = " << r[u] << ", path = [";
    vector<int> path;
    for (int v = u; v != -1; v = pi[v]) path.push_back(v);
    reverse(all(path));
    for (int v : path) cout << v + 1 << (v == u ? "]\n" : ", ");
  }
  return 0;
}