#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
struct ad{
    int nda,vl;
};
int vad[100001];
queue<ad>q;
vector<int>ma[100001];
int main(){
    int n,m,s,i,a,b;
    ad aux,nd;
    fin>>n>>m>>s;
    for(i=1;i<=n;i++)vad[i]=-1;
    vad[s]=0;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        if(a!=b)ma[a].push_back(b);
    }
    vector<int>::iterator it;
    aux.nda=s;
    aux.vl=0;
    q.push(aux);
    while(!q.empty()){
        nd=q.front();
        q.pop();
        for(it=ma[nd.nda].begin();it!=ma[nd.nda].end();it++)
            if(nd.vl+1<vad[*it]||vad[*it]==-1){
                    vad[*it]=nd.vl+1;
                    aux.nda=*it;
                    aux.vl=vad[*it];
                    q.push(aux);
            }
    }
    for(i=1;i<=n;i++)
        fout<<vad[i]<<" ";
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}