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

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

int n, m, s, x, y, k;

vector<int> Si;
vector<bool> V;
vector<vector<int>> G;

void Read();
void BFS( int s );
void Write();

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

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


void Read()
{
    is >> n >> m >> s;
    Si = vector<int>(n+1, -1);
    G = vector<vector<int>>(n+1);
    V = vector<bool>(n+1);
    for ( int i = 1; i <= m; i++ )
    {
        is >> x >> y;
        G[x].push_back(y);
    }
}

void BFS( int i )
{
    queue<int> Q;
    Q.push(i);
    V[i] = true;
    Si[s] = 0;
    while( !Q.empty() )
    {
        x = Q.front();
        Q.pop();
        for ( const auto& y : G[x] )
        {
            if( V[y] ) continue;
            V[y] = true;
            Q.push(y);
            Si[y] = Si[x] + 1;
        }
    }

}

void Write()
{
    for ( vector<int>::iterator it = Si.begin() + 1; it != Si.end(); ++it )
        os << *it << ' ';
}