#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 100001
using namespace std;

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

vector <int> vecin[nmax];
queue <int> q;
int n,m,s,a,b,i,nod[nmax];

void bfs(){

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

        q.pop();
        
        for (i=0; i<vecin[cur].size(); i++)
            if (nod[vecin[cur][i]]<0){
                nod[vecin[cur][i]]=nod[cur]+1;
                q.push(vecin[cur][i]);
            }
    }
    
}

int main(){
    
    in >> n >> m >> s;
    
    q.push(s);
    
    for (i=1; i<=n; i++)
        nod[i]=-1;
    
    nod[s]=0;
    
    for (i=1; i<=m; i++){
        in >> a >> b;
        vecin[a].push_back(b);
        
    }
    
    bfs();
    
    for (i=1; i<=n; i++)
        out << nod[i] << " ";
    
    return 0;
}