#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <queue>
#include <algorithm> 

using namespace std;
 int s;
/* 1) Citire și construire LISTĂ de adiacență din fișier. */
void construiesteLista(const string& numeFisier, vector<vector<int>>& lista, int& n) {
    ifstream f(numeFisier);
    if (!f) {
        cerr << "Eroare la deschiderea fișierului " << numeFisier << "!\n";
        return;
    }

    int m;  // numarul de muchii
    
    f >> n >> m>>s; 

    // Redimensionăm "lista" pentru a avea n+1 vectori (indexare de la 1)
    lista.assign(n + 1, {});

    // Citim fiecare muchie
    for (int i = 0; i < m; ++i) {
        int a, b;
        f >> a >> b;
        // Adăugăm b la lista de adiacență a nodului a
        lista[a].push_back(b);

        // Dacă graful e neorientat, decomentați linia următoare:
        // lista[b].push_back(a);
    }
    f.close();
}

/* Funcții auxiliare pentru afișare */
void afiseazaLista(const vector<vector<int>>& lista, int n, ofstream& g) {
    for (int i = 1; i <= n; ++i) {
        g << "Nodul " << i << " este adiacent cu: ";
        for (int vecin : lista[i]) {
            g << vecin << " ";
        }
        g << "\n";
    }
    g << endl;
}

// Funcție pentru parcurgerea în lățime (BFS)
void bfs(int s, const vector<vector<int>>& graf, vector<int>& parinte) {
    // n va fi (numărul de noduri + 1) dacă lista e indexată de la 1
    int n = graf.size();  
    vector<bool> vizitat(n, false);  // Vector de vizitare pentru noduri
    queue<int> q;                    // Coada pentru BFS

    // Inițializări
    q.push(s);
    vizitat[s] = true;
    parinte[s] = -1;  // Nodul sursă nu are părinte

    while (!q.empty()) {
        int nod = q.front();
        q.pop();

        // Iterăm prin vecinii nodului curent
        for (int vecin : graf[nod]) {
            // Varianta standard BFS (fără testul vecin != parinte[nod]):
            if (!vizitat[vecin]) {
                vizitat[vecin] = true;
                parinte[vecin] = nod;
                q.push(vecin);
            }
        }
    }
}
int nr;
// Funcție pentru a afișa drumul minim de la nodul de start s la nodul x
void afiseazaDrum(int x, const vector<int>& parinte, ofstream& g) {
    vector<int> drum;
     if (parinte[x] == -1 && x != s) { // Dacă x nu a fost vizitat și nu este sursa aici e cazul in care nu exista drum de la sursa la x
        cout << "Nu exista drum de la sursa la " << x << "\n";
        g << "Nu exista drum de la sursa la " << x << "\n";
        return;
    }
    // Urmărim părinții pentru a reconstrui drumul
    for (int i = x; i != -1; i = parinte[i]) {
        drum.push_back(i);
    }
    // Reversăm drumul pentru a-l afișa de la sursă la destinație
    reverse(drum.begin(), drum.end());

   // g << "Drumul minim de la sursa la " << x << " este: ";
    nr=0;
    
    for (int nod : drum) {
        nr++; //aici e numarul de noduri din drum,pentru cerinta asta:Fiind dat un nod S, sa se determine, pentru fiecare nod X, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X.
        //cout << nod << " ";
    }
    g<<nr-1<<" ";
   // g << endl;
}

int main() {
    ofstream g("bfs.out");
   // g << "=== Construire LISTA de adiacenta din fisier ===\n";
    vector<vector<int>> lista;
    int nLista;
    
    if (!g) {
        cerr << "Eroare la deschiderea fișierului output.out!\n";
        return 1;
    }

    // Citiți din fișierul "lista.in"
    construiesteLista("bfs.in", lista, nLista);

    // Afisam lista citită
   // cout << "Lista de adiacenta citita:\n";
    //afiseazaLista(lista, nLista,g);

    // Testăm BFS
  //  int s, x;
    //cout << "Introduceti nodul de start s si nodul destinatie x pentru BFS (indexare de la 1): ";
   // cin >> s >> x;

    // Aici trebuie să folosim nLista pentru crearea vectorului parinte
    vector<int> parinte(nLista + 1, -1);


    // Apel BFS
    
    for(int i=1;i<=nLista;i++)
    {
        bfs(s, lista, parinte);
        if (i == s || parinte[i] != -1) 
        {
            afiseazaDrum(i, parinte,g);
        } 
        else 
        //co << "Nu exista drum de la " << s << " la " << i << endl;
          g<<-1<<" ";
    }
    

    // Verificăm dacă am ajuns la x (dacă are părinte setat, altul decât -1, cu excepția cazului s = x)
    // Atenție, dacă x == s, parinte[x] = -1 e normal, dar există drum trivial (s la s).
    // Ca idee, dacă BFS a vizitat x, atunci parinte[x] != -1 sau x == s.
   /// if (x == s || parinte[x] != -1) {
      ///  afiseazaDrum(x, parinte);
   // } else {
      //  cout << "Nu exista drum de la " << s << " la " << x << endl;
  //  }


  // drum minim
  /*
        int x;
        cin>>s>>x;
        bfs(s, lista, parinte);
        afiseazaDrum(x, parinte,g);
        */
       
    return 0;
}