#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100000;

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


int S;
vector <int> g[NMAX+1];
queue <int> Q;

int d[NMAX+1];

void init(int N)
{
    for( int i= 1; i <=N; ++i )
        d[i]= -1;
}

void bfs()
{
    int x;
    Q.push(S);
    d[S]= 0;
    while( Q.empty()==0 )
    {
        x= Q.front();
        for( int i= 0; i<(int)g[ x ].size(); ++i )
        {
            if( d[ g[x][i] ]== -1 )
            {
                Q.push( g[x][i] );
                d[ g[x][i] ]= d[x]+1;
            }
        }
        Q.pop();
    }

}

int main(  )
{
    int N, M;

    in >> N >> M >>S;

    init(N);

    int x, y;

    for( int i= 1; i<=M; ++i )
    {
        in >> x >> y;
        g[x].push_back(y);
    }

    bfs();

    for( int i= 1; i<=N; ++i )
    {
        out << d[i] << " ";
    }

    out << '\n';

    return 0;
}