#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int n,m,s;
int vizitat[100000];
int d[1000000];
queue < int > q;
vector < vector < int > > Graf;

void citesc(){

    int x,y;
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    Graf.resize(n+1);
    for(register int i=1;i<=m;++i){

        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
    }

}

void bfs(){

    vizitat[s] = 1;
    d[s] = 0;

    q.push(s);
    int nod = 0;

        while(!q.empty()){

            nod = q.front();
            q.pop();
            for(vector < int > :: iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
                if(!vizitat[*it]){
                    q.push(*it);
                    vizitat[*it] = 1;
                    d[*it] = d[nod] + 1;
                }

        }
}

int main(){

    citesc();
    for(register int i=1;i<=n;++i)
            d[i] = -1;
    bfs();
    for(register int i=1;i<=n;++i){

        printf("%d ",d[i]);
    }
return 0;
}