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

using namespace std;

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

class Graf{
    private:
        int n;
        vector<vector<int>> muchii;
        vector<int> viz;
    public:
        int getN();
        void addMuchie(int x, int y);
        void bfs_dist(std::queue<int> &coada, int costuri[]);
        void bfs(int s);
        Graf();
        Graf(int n);
};
Graf::Graf(int n){
    this->n = n;
    vector<int> temp;
    for(int i=0;i<=n;i++){
        muchii.push_back(temp);
        viz.push_back(0);
    }
}

int Graf::getN (){
    return n;
}
void Graf::addMuchie(int x, int y){
    muchii[x].push_back(y);
}

void Graf::bfs_dist(queue<int> &coada, int costuri[]){
   int s = coada.front();
   coada.pop();//stergem elementul curent
   viz[s]=1;//e vizitat
    for(auto i:muchii[s]){
        if(!viz[i]){coada.push(i);
        costuri[i] = costuri[s] + 1;
        viz[i]=1;}
    }
    if(!coada.empty())bfs_dist(coada, costuri);
}

void Graf::bfs(int s){
    int costuri[n+1];
    queue<int> coada;
    coada.push(s);
    for(int i=1;i<=n;i++){
        costuri[i]=-1;//costul -1 la toate
    }
    costuri[s]=0;//costul primul element 0
    bfs_dist(coada, costuri);
    for(int i=1;i<=n;i++){
        out << costuri[i] << " ";
    }
}

int main(){
    int n,m,s;
    in >> n >> m >> s;
    Graf graf1(n);
    int x, y;
    for(int i=1;i<=m;i++){
        in >> x >> y;
        graf1.addMuchie(x,y);//adauga muchii
    }
    graf1.bfs(s);
    return 0;
}