#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

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

int n, s;
bitset<100001> ok;
vector<vector<int> > G;
vector<int> d;   // dist. minima
queue <int> q;


void Read();
void Bfs( int x );
void Write();

int main()
{
    Read();
    Bfs(s);
    Write();

    is.close();
    os.close();
    return 0;
}

void Read()
{
    int m, i, j;
    is >> n >> m >> s;

    G.resize(n+1);
    d.resize(n+1, -1 );
    while( m-- )
    {
        is >> i >> j;
        if ( i != j )
            G[i].push_back(j);
    }
}

void Bfs( int x )
{
    d[x] = 0;
    ok[x] = true;
    q.push(x);
    while ( !q.empty() )
    {
        x = q.front();
        q.pop();
        for ( vector<int>::iterator it = G[x].begin(); it != G[x].end(); ++it )
        {
            if ( ok[*it] ) continue;
            ok[*it] = true;
            d[*it] = d[x] + 1;
            q.push(*it);

        }

    }
}

void Write()
{
    for ( int i = 1; i <= n; ++i )
            os << d[i] << ' ';
}