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

using namespace std;

vector <int> *muchii;
queue <int> coada;

int nrNoduri, nrMuchii, nodStart, *distanta;
bool *vizitat;

void BFS(int nodStart){

   coada.push(nodStart);

   vizitat[nodStart] = true;

   int index;

   while( !coada.empty() ) {

        index = coada.front();

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

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

            }
        }

        coada.pop();

    }

}


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 << "\nEroare la alocare dinamica !\n";
            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] << " ";


    return 0;
}