#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("BFS.in");
ofstream fout("BFS.out");
vector<int>a[10000];
int n,m,i,j,x,y,z,v[100002],c[100002],t[100002],s,u,p,start,l[100002];
int main(){
    fin>>n>>m>>start;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        a[x].push_back(y);
    }
    for (i=1;i<=n;i++){
        sort( a[i].begin(), a[i].end() );
        l[i]=-1;
    }

    c[1]=start;
    v[start]=1;
    l[start]=0;
    u=1;
    p=1;
    while(p<=u){
        int nod=c[p];
        for(i=0;i<a[nod].size();i++){
            int vecin=a[nod][i];
            if( v[vecin]==0){
                u++;
                c[u]=vecin;
                l[vecin]=l[nod]+1;
                v[vecin]=1;

            }
        }
        p++;
    }
    for(i=1;i<=n;i++){

            fout<<l[i]<<" ";


    }

}