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

#define VMAX 100005

using namespace std;

void read();
void bfs();
void write();

int n, m, s;
vector<bool> state(VMAX);
vector<vector<int> > graph(VMAX);
vector<int> road(VMAX);
queue<int> q;

int main()
{
    read();
    bfs();
    write();

    return 0;
}

void read()
{
    ifstream fin( "bfs.in"  );

    fin >> n >> m >> s;
    for ( int i = 0; i < m; ++i )
    {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
    }

    fin.close();
}

void bfs()
{
    //initial se insereaza nodul S intr-o coada vida, cu costul 0
    q.push(s);
    int act = s;

    road[act] = 0;

    while ( !q.empty() )
    {
        //la fiecare pas se ia nodul de la inceputul cozii
        act = q.front();
        state[act] = true;

        for ( vector<int> :: iterator i = graph[act].begin(); i < graph[act].end(); ++i )
            if( !state[*i])
            {
                state[*i] = true;
                // costul unui nod nou adaugat va fi costul nodului care l-a adaugat + 1.
                road[*i] = road[act] + 1;
                //se adauga vecinii nevizitati la finalul cozii
                q.push( *i );
            }

        // apoi se elimina nodul de la inceputul cozii
        q.pop();
    }
}

void write()
{
    ofstream fout( "bfs.out" );

    for ( int i = 1; i < 1 + n; ++i)
    {
        if ( state[i] || i == s)
            //al i-lea numar reprezinta numarul minim de arce ce trebuie parcurse de la nodul S la nodul i.
            fout << road[i] << " ";
        else
            //daca nu se poate ajunge din nodul S la nodul i, atunci numarul corespunzator numarului i va fi -1.
            fout << -1 << " ";
    }

    fout.close();
}