#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>

using namespace std;

int nrNoduri, nrMuchii, nodStart;
int *distanta;

vector <int> *muchii, coada;
bool *vizitat;

void BFS(int nodStart){

   int inc = 0,sf = -1;

   coada.push_back(nodStart);

   ++sf;

   vizitat[nodStart] = true;

   int index;

   while( inc <= sf ) {

        index = coada[inc];

        for(int vecin = 0; vecin < muchii[index].size(); vecin++){ //cout <<"test";

            if ( !vizitat[muchii[index][vecin]] ) {
                                    coada.push_back(muchii[index][vecin]);
                                    vizitat[muchii[index][vecin]] = true;
                                    distanta[muchii[index][vecin]] = distanta[index] + 1;
                                    sf++;
            }
        }

        inc++;

    }

    //for(int k=0; k<coada.size(); k++) cout<<coada[k]<<" ";
}


int main(){

    ifstream fin;
    ofstream fout;

    fin.open("bfs.in");
    fout.open("bfs.out");

    if (!fin){
        cout << "\nNu a reusit deschiderea fisierului !\n";
        exit(-1);
    }

    fin >> nrNoduri >> nrMuchii >> nodStart;

    muchii = new vector<int>[nrNoduri+5];
    vizitat = new bool[nrNoduri+5];
    distanta = new int[nrNoduri+5];

    if (!muchii || !vizitat || !distanta) {
            cout << "eroare la alocare dinamica";
            exit(-1);
    }

     for (int i = 1; i <= nrNoduri; i++){
        distanta[i] = 0;
        vizitat[i] = false;
     }

    int x = 0, y = 0;

    for (int i = 1; i <= nrMuchii; i++){

        fin >> x >> y;

        muchii[x].push_back(y);

    }

    BFS(nodStart);

    for (int i = 1; i <= nrNoduri; i++)
        if (!vizitat[i])
                fout << -1 << " ";
        else
          fout << distanta[i] << " ";


/*
     for (int i = 1; i <= nrNoduri; i++){
        cout << i <<": ";
        for ( int j = 0; j < muchii[i].size(); j++)
                cout << muchii[i][j] << " ";
        cout <<"\n";
     }

*/




    return 0;
}