#include <fstream>
#include <queue>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

int nrn, nrm, nrk, poz1, poz2, cnt = 1, sav;

queue<int> lin;

vector<int> vec[100005];
int ras[100005];


void func(){
    while(!lin.empty()){
        nrk = lin.front();
        lin.pop();
        for(int index = 0; index < vec[nrk].size(); index++) {
           sav = vec[nrk][index];
           if(!ras[sav]){
               lin.push(sav);
               ras[sav] = ras[nrk] + 1;
           }
        }

    }
}

int main()
{
    fin >> nrn >> nrm >> nrk;
    for(int index = 0; index < nrm; index++){
        fin >> poz1 >> poz2;
        vec[poz1].push_back(poz2);
    }
    ras[nrk] = 1;
    lin.push(nrk);
    func();
    for(int index = 1; index <= nrn; index++){
        fout << ras[index] - 1 << " ";
    }
    fout << endl;
    return 0;
}