#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;
vector<int> V[100000];
vector< int >::iterator it;
queue<  pair<int,int> > Q;
int h=0;


int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    int N,M,s;
    scanf("%d%d%d",&N,&M,&s);
    int x,y, p[100005];
    memset( p , -1 ,sizeof(p)  );
    while(  M-- ){
        scanf("%d%d",&x,&y);
        V[x].push_back(y); }
    p[s]=0;
    Q.push( make_pair(s,0) );
    pair<int,int> k;
    for( ; !Q.empty() ; Q.pop()  ){
        k=Q.front();
        ++h;
        it=V[k.first].begin();
        for( ; it != V[k.first].end(); ++it ){
            if( p[ *it ]==-1 ){
                p[ *it ]= k.second+1;
                Q.push(  make_pair(*it,k.second+1) );}}}
    for(register int i=1;i<=N;++i)
        printf("%d ",p[i]);
    return 0;
}