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



bool k[100003];
int c[100003],cc,c2[100003],cc2,r[100003];

using namespace std;

vector <int> v[100003];

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

void bfs(int d){
    cc2=0;
    if(cc==0){
        return;
    }
    for(int i=0;i<cc;i++){
        r[c[i]]=d;
    }
    for(int i=0;i<cc;i++){
        for(int ii=0;ii<v[c[i]].size();ii++){
            if(!k[v[c[i]][ii]]){
                k[v[c[i]][ii]]=true;
                c2[cc2]=v[c[i]][ii];
                cc2++;
            }

        }

    }
    for(int i=0;i<cc2;i++){
            c[i]=c2[i];
    }
    cc=cc2;
    bfs(d+1);
}

int main()
{
    int n,m,s,x,y;
    fin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        r[i]=-1;
    }
    for(int i=0;i<m;i++){
        fin>>x>>y;
        v[x].push_back(y);
    }
    c[0]=s;
    k[s]=true;
    cc=1;
    bfs(0);
    for(int i=1;i<=n;i++){
        cout<<r[i]<<" ";
    }
    return 0;
}