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

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

vector<vector<int>> G;
int n, m, t, z,  S;
vector<int> x;
vector<bool> a;
queue<int> Q;

void BFS( int S );

int main()
{
    is >> n >> m >> S;
    G = vector<vector<int>>(n+1);
    a = vector<bool>(n+1);
    x = vector<int>(n+1);
    for ( int i = 1; i <= m; i++ )
    {
        is >> t >> z;
        G[t].push_back(z);
    }

    BFS(S);

    for ( int i = 1; i <= n; i++ )
        if ( x[i] == 0 && i != S )
            os << "-1 ";
        else
            os << x[i] << ' ';

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

void BFS( int S )
{
    Q.push(S);
    x[S] = 0;
    a[S] = true;
    int y;
    while ( !Q.empty() )
    {
        y = Q.front();
        Q.pop();
        for ( vector<int>::iterator it = G[y].begin(); it != G[y].end(); ++it )
            if ( a[*it] == false )
            {
                x[*it] = x[y] + 1;
                Q.push(*it);
                a[*it] = true;
            }
    }
}